array.sort(function() { return Math.random() - 0.5 })Вроде бы все правильно. Массив должен сортироваться случайным образом. Но это не совсем так. Иногда такой способ вызывает исключение «нарушены условия контракта».
Разбираемся в причинах
Оказывается сортировка вызывается неоднократно и для одних и тех же пар элементов будут разные значения сортировки. Это может привести к повторным перемещениям элементов в списке сортировки. Естественно это сделает сортировку более длительной. Скорее всего внутри сортировщика находится защита от длительной сортировки. Вот мы и получаем такое исключение.
Как стоит производить сортировку?
Метод следующий. Сразу генерим массив случайных чисел рядом и сортируем свой массив как этот сгенерированый. Код реализации такой.
array
.map(function(elem,index) { return [elem, Math.random()]})
.sort(function(a,b){ return a[1] - b[1]})
.map(function(elem){return elem[0]})Комментарии (38)
e_fail
13.08.2019 15:19+1Сортировка — это же O(n * log n).
Обычно используют что-то на основе Fisher-Yates shuffle, который работает за O(n).
Static_electro
13.08.2019 15:39+1Вот эту статью надо показывать, когда в очередной раз начнется холивар "зачем программистам знание алгоритмов".
eavprog Автор
13.08.2019 16:28К сожалению не знаю перевод этого слова. Поможете?
Gibboustooth
13.08.2019 18:51Алгори?тм (лат. algorithmi — от арабского имени математика Аль-Хорезми[1]) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
eavprog Автор
13.08.2019 21:44-1Очень смешно… И все же я попрошу вас перевести употребление слово неизвестного языка
Gibboustooth
13.08.2019 22:06А, т.е. с арабским языком вы знакомы? Простите, я не в курсе ваших лингвистических познаний.
berez
13.08.2019 15:44+1Случайная сортировка массива на JavaScript
«Случайная сортировка» — это когда шел с корзиной яблок, споткнулся, упал, глядишь — батюшки! Яблоки-то лежат отсортированные!
А то, что вы имели в виду, называется случайная перестановка. И, как правильно вам тут уже заметили, для нее не нужно генерить никакие случайные массивы, выжирающие память.eavprog Автор
13.08.2019 16:35Ошибки эти ловил в Google Script. Подгружать лишние библиотеки желания не было из соображений сдирания памяти. Да и лишних вычислений не хотелось делать. Итак на пределе свободной квоты. А это решение как раз устранило все проблемы.
Кстати по-видимому эта ошибка и машинное время тоже ощутимо расходовала. У меня прекратилась выдаваться ошибка о перерасходе времени выполнения скрипта.
eandr_67
14.08.2019 10:06+1Как раз описанный в статье вариант и занимается бессмысленным расходом памяти для совершения бессмысленных вычислений.
Перемешивание массива реализуется безо всяких библиотек — простейшим циклом, который работает быстрее и требует меньше памяти, чем предложенная сортировка.
Очередное «изобретение» очередного низкокачественного велосипеда для задачи, решённой 81 год назад (в современном виде — 55 лет назад).
Sirion
13.08.2019 16:26Простите за саморекламу, но сдержаться было превыше человеческих сил.
Тык.eavprog Автор
13.08.2019 16:39Зачёт.
Читал эту статью, но мне казалось что ей намного больше чем год.mikaakim
13.08.2019 18:03Если вы читали ту статью, то в чем отличия между ними? Допустим, они будут, но насколько больший вклад вносит ваша статья или какую она имеет значимость для сообщества?
eavprog Автор
13.08.2019 18:24Быстрое, краткое решение. В сети сразу на глаза не попалось. Но в одной из статей упоминался подход через map. Самого решения не было. Вот его собрал. Теперь и другие могут пользоваться.
Gibboustooth
13.08.2019 19:10Быстрое, краткое, понятное, неправильное решение?
eavprog Автор
13.08.2019 21:47Чем же оно неправильно. Прекрасно перемешивает. В моей задаче необходимо обрабатывать записи из списка случайно. Никаких нареканий. Равномерно обрабатывает.
Gibboustooth
14.08.2019 12:37Тем, что алгоритм перестановки должен работать за O(n) время, а ваш работает за O(n*log(n)). Значит, алгоритм перестановки реализован неправильно.
igormich88
13.08.2019 19:14Но ведь оно медленное.
eavprog Автор
13.08.2019 21:51-3Медленное решение — это решение в цикле и большим количеством строк. Здесь по одной строке и цикл вшит внутри скомпилированных функций.
Sirion
13.08.2019 22:01+1Батенька, ну вы до такой степени не понимаете, о чём говорите, что смотреть страшно(
igormich88
13.08.2019 22:05По пунктам:
- map порождает новый список, той же длины что и исходный
- sort имеет сложность больше линейной, полагаю что O(N*log(N))
- ну и создание N массивов из двух элементов мне кажется тоже на самая дешевая операция
«Вшитые» функции это не панацея, вычислительная сложность алгоритма важнее (за исключением редких случаев).eavprog Автор
14.08.2019 08:05-1У меня пропали ошибки чрезмерного использования времени. Писем с ошибками уже два дня нет. Полагаю этот довод в пользу правильности моего решения.
Alternator
14.08.2019 16:32Потому что ваше предыдущее решение
а) еще более медленное. В нем N*log(N) генераций рандомных чисел
В новом вашем варианте только N генераций рандомных чисел
Но у вас все еще N*log(N) операций сравнения(в виде вызова колбека), о чем вам все и говорят
б) совершенно некорректное. Массив получается не по-честному рандомно сортированный. Распределение вероятностей неравномерно
eavprog Автор
13.08.2019 18:38К сожалению не смог взять код решения из этой статьи. Нужно бороться за скорость выполнения. JavaScript — интерпретатор.
Zenitchik
13.08.2019 23:08Нужно бороться за скорость выполнения.
Вы это серьёзно? На каком примере код из статьи дал неприемлемо большое время?eavprog Автор
14.08.2019 08:14К сожалению у меня каждый день приходили ошибки чрезмерного использования времени работы скрипта. Т.е мой скрипт работает на грани свободной квоты. Ваш код не пробовал. Ведь он весь получается должен выполняться в интерпретаторе. В моем решении нет циклов. Они внутри функций map и sort. А там они уже должны быть скомпилированными. И лишь немного работы интерпретатора требуется на выполнение передаваемых однострочных функций генерации случайного числа, сравнения и конкатенации элемента списка и случайного числа внутри функции sort. Полагаю это решение быстрее.
Sirion
14.08.2019 08:49Вы сами себе создаёте проблемы на ровном месте. С одной стороны, мне больно на это смотреть. С другой — вы это заслужили. Хороший программист не может быть железобетонно уверен в неверных утверждениях. Если ему хором объясняют, что он неправ, он по крайней мере попытается это проверить.
Я в последний раз просуммирую, где вы неправы.
1. Ошибка «нарушены условия контракта» означает, что функция, передаваемая в sort, должна удовлетворять некоторым требованиям. Если она им не удовлетворяет, sort может работать некорректно. Это не обязательно связано со временем выполнения, там может какой-нибудь index out of bounds происходить, да хоть вообще rm -rf.
2. Нативный код совершенно не обязательно будет работать быстрее JS (погуглите fast.js). А если и будет, то в конечное число раз. В два, в три, в шесть. Давайте назовём это число K.
3. У случайной сортировки хуже асимптотика. Она требует в log(n) раз больше операций, чем Фишер-Йетс. А log(n) растёт неограниченно, и рано или поздно он превысит K и сожрёт всё преимущество нативного кода (если оно вообще было).
4. Если функция однострочная, это совершенно не значит, что она быстрая. Особенно если она вызывается много раз. Допустим, у вас там для каждого элемента конструируется ещё дополнительный маленький массив. На самом деле это не сильно повлияет на скорость, но вы этого не знаете, это знаю я. Что приводит нас к следующему пункту:
5. Профилирование и бенчмарки — наше всё. Представьте на секунду, что на хабре сидят не сплошные идиоты. Допустите крупицу сомнения. А потом просто, чёрт побери, возьмите и сравните свой подход с предложенным. Проведите тесты и выясните истину лично, не полагаясь на всякие мутные рассуждения про «нет циклов» и «должны быть скомпилированными».
6. Если вы успешно проигнорировали предыдущие пять пунктов — наслаждайтесь страданием. На этом, пожалуй, закончу.eavprog Автор
14.08.2019 10:16-1Сожалею, что эта статья вызвала у вас волну гнева. Мне нужно было сразу описать ограничения — применение в облаке Google. Хотелось поделиться удачным решением. Ошибки то больше не приходят. И система перестала останавливать скрипты из-за перерасхода времени выполнения.
Когда достигну следующего потолка, обязательно обращусь сюда за дальнейшими совершенствованиями кода.
Профилирования там нет. Но можно выводить время в лог. Но результат достигнут. А лучшее — враг хорошего.
Подключать библиотечные модули себе дороже. Об этом они сами пишут в помощи. Это только тормозит систему. А то давно бы уже туда свои нейросети всунул.
Боюсь мне все же придется в ближайшее время наращивать производительность. И тогда наверняка придется пробовать и предлагаемую сортировку. Но боюсь Google Script — это обычный интерпретатор и у него шаги между строк на порядок медленнее чем в скомпилированном варианте.
Но это уже тема для следующей статьи. И естественно жду очередную волну вашего гнева. И естественно я только "ЗА".
Sirion
14.08.2019 10:54Да какой, к чёрту, гнев? У меня испанский стыд)
Лучше не пишите следующую статью. Писать надо о том, в чём разбираешься. Даже если предположить, что вы нашли удачное решение (а это не так, но я математик, я умею делать выводы из абсурдных предположений) — у вас материала максимум для ответа на тостере. Если на хабр начнут постить каждое найденное решение каждой встреченной проблемы, тут будет ещё большая помойка, чем сейчас.
Zenitchik
14.08.2019 15:23К сожалению у меня каждый день приходили ошибки чрезмерного использования времени работы скрипта.
Иными словами, Вам не составит труда, описать что Вы сортировали, и сколько времени это заняло? Прошу!
eavprog Автор
14.08.2019 08:15Но на си конечно ваше решение будет быстрее. У меня интерпретатор.
greg123
14.08.2019 18:11Я, конечно, всегда скептически относился к утверждениям о том, что javascript, java и прочее, выполняется так же быстро, как код, скомпилированный под целевую платформу, но не до такой же степени. Я честно, ни малейшег опредставления не имею о том, что происходит в вашем облаке, но я могу предположить, что с большой долей вероятности ваш код на js компилируется в некий промежуточный код, который и исполняется. Поверьте, никто не будет парсить тело цикла на каждой итерации. Вы просто ударяетесь в крайности. Я как-то встретил человека, который полагал, что чем меньше размер инструкции (в байтах), тем быстрее она выполняется процессором. У вас очень похожее заблуждение — вы пытаетесь написать не эффективный, а компактный код.
4eyes
13.08.2019 18:52Ёлки-палки, чем вам Knuth shuffle не угодил? У вас выше сложность (n log n, если я не ошибаюсь), и скорее всего, распределение далеко от случайного.
igormich88
13.08.2019 18:56Я попробовал сравнить ваш метод и первый попавшийся пример со Stack Overflow с перемещением элементов внутри for — тест
Результаты в моём браузере:
- Пример со SO 972 ops/s ±0.62%
- Ваш код 6 ops/s ±8.98%
JekaMas
13.08.2019 21:33Правильный подход. Автору статьи, вероятно, стоило начать с точного описания задачи: какие наборы данных, какие требования к ресурсам, к вычислительной сложности алгоритма. И потом сразу написать бенчмарки.
AxisPod
Это называется не сортировка, а хотя бы перемешивание. И по фразе «js shuffle array» есть неимоверное кол-во результатов.
eavprog Автор
Немецкий в школе учил… Ищу в сети как есть по-русски.
justboris
Все для вас, пожалуйста: http://www.brain4.de/programmierecke/js/arrayShuffle.php