Случайная сортировка массива на JavaScript -19



Для случайной сортировки массива можно использовать стандартную конструкцию

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):

  1. AxisPod
    /#20500417 / +3

    Это называется не сортировка, а хотя бы перемешивание. И по фразе «js shuffle array» есть неимоверное кол-во результатов.

  2. e_fail
    /#20500479 / +1

    Сортировка — это же O(n * log n).
    Обычно используют что-то на основе Fisher-Yates shuffle, который работает за O(n).

  3. Static_electro
    /#20500593 / +1

    Вот эту статью надо показывать, когда в очередной раз начнется холивар "зачем программистам знание алгоритмов".

    • eavprog
      /#20500899

      К сожалению не знаю перевод этого слова. Поможете?

      • Gibboustooth
        /#20501649

        Алгори?тм (лат. al­go­rithmi — от арабского имени математика Аль-Хорезми[1]) — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.


        https://ru.m.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC

        • eavprog
          /#20502129 / -1

          Очень смешно… И все же я попрошу вас перевести употребление слово неизвестного языка

          • Gibboustooth
            /#20502203

            А, т.е. с арабским языком вы знакомы? Простите, я не в курсе ваших лингвистических познаний.

  4. berez
    /#20500617 / +1

    Случайная сортировка массива на JavaScript

    «Случайная сортировка» — это когда шел с корзиной яблок, споткнулся, упал, глядишь — батюшки! Яблоки-то лежат отсортированные!
    А то, что вы имели в виду, называется случайная перестановка. И, как правильно вам тут уже заметили, для нее не нужно генерить никакие случайные массивы, выжирающие память.

    • eavprog
      /#20500937

      Ошибки эти ловил в Google Script. Подгружать лишние библиотеки желания не было из соображений сдирания памяти. Да и лишних вычислений не хотелось делать. Итак на пределе свободной квоты. А это решение как раз устранило все проблемы.


      Кстати по-видимому эта ошибка и машинное время тоже ощутимо расходовала. У меня прекратилась выдаваться ошибка о перерасходе времени выполнения скрипта.

      • eandr_67
        /#20503401 / +1

        Как раз описанный в статье вариант и занимается бессмысленным расходом памяти для совершения бессмысленных вычислений.

        Перемешивание массива реализуется безо всяких библиотек — простейшим циклом, который работает быстрее и требует меньше памяти, чем предложенная сортировка.

        Очередное «изобретение» очередного низкокачественного велосипеда для задачи, решённой 81 год назад (в современном виде — 55 лет назад).

  5. Sirion
    /#20500881

    Простите за саморекламу, но сдержаться было превыше человеческих сил.
    Тык.

    • eavprog
      /#20500965

      Зачёт.
      Читал эту статью, но мне казалось что ей намного больше чем год.

      • mikaakim
        /#20501447

        Если вы читали ту статью, то в чем отличия между ними? Допустим, они будут, но насколько больший вклад вносит ваша статья или какую она имеет значимость для сообщества?

        • eavprog
          /#20501519

          Быстрое, краткое решение. В сети сразу на глаза не попалось. Но в одной из статей упоминался подход через map. Самого решения не было. Вот его собрал. Теперь и другие могут пользоваться.

          • Gibboustooth
            /#20501729

            Быстрое, краткое, понятное, неправильное решение?

            • eavprog
              /#20502141

              Чем же оно неправильно. Прекрасно перемешивает. В моей задаче необходимо обрабатывать записи из списка случайно. Никаких нареканий. Равномерно обрабатывает.

              • Gibboustooth
                /#20504369

                Тем, что алгоритм перестановки должен работать за O(n) время, а ваш работает за O(n*log(n)). Значит, алгоритм перестановки реализован неправильно.

          • igormich88
            /#20501737

            Но ведь оно медленное.

            • eavprog
              /#20502153 / -3

              Медленное решение — это решение в цикле и большим количеством строк. Здесь по одной строке и цикл вшит внутри скомпилированных функций.

              • Sirion
                /#20502189 / +1

                Батенька, ну вы до такой степени не понимаете, о чём говорите, что смотреть страшно(

              • igormich88
                /#20502199

                По пунктам:

                • map порождает новый список, той же длины что и исходный
                • sort имеет сложность больше линейной, полагаю что O(N*log(N))
                • ну и создание N массивов из двух элементов мне кажется тоже на самая дешевая операция

                «Вшитые» функции это не панацея, вычислительная сложность алгоритма важнее (за исключением редких случаев).

                • eavprog
                  /#20503011 / -1

                  У меня пропали ошибки чрезмерного использования времени. Писем с ошибками уже два дня нет. Полагаю этот довод в пользу правильности моего решения.

                  • Alternator
                    /#20505579

                    Потому что ваше предыдущее решение
                    а) еще более медленное. В нем N*log(N) генераций рандомных чисел
                    В новом вашем варианте только N генераций рандомных чисел
                    Но у вас все еще N*log(N) операций сравнения(в виде вызова колбека), о чем вам все и говорят
                    б) совершенно некорректное. Массив получается не по-честному рандомно сортированный. Распределение вероятностей неравномерно

        • eavprog
          /#20501569

          К сожалению не смог взять код решения из этой статьи. Нужно бороться за скорость выполнения. JavaScript — интерпретатор.

          • Zenitchik
            /#20502357

            Нужно бороться за скорость выполнения.

            Вы это серьёзно? На каком примере код из статьи дал неприемлемо большое время?

            • eavprog
              /#20503027

              К сожалению у меня каждый день приходили ошибки чрезмерного использования времени работы скрипта. Т.е мой скрипт работает на грани свободной квоты. Ваш код не пробовал. Ведь он весь получается должен выполняться в интерпретаторе. В моем решении нет циклов. Они внутри функций map и sort. А там они уже должны быть скомпилированными. И лишь немного работы интерпретатора требуется на выполнение передаваемых однострочных функций генерации случайного числа, сравнения и конкатенации элемента списка и случайного числа внутри функции sort. Полагаю это решение быстрее.

              • Sirion
                /#20503119

                Вы сами себе создаёте проблемы на ровном месте. С одной стороны, мне больно на это смотреть. С другой — вы это заслужили. Хороший программист не может быть железобетонно уверен в неверных утверждениях. Если ему хором объясняют, что он неправ, он по крайней мере попытается это проверить.

                Я в последний раз просуммирую, где вы неправы.

                1. Ошибка «нарушены условия контракта» означает, что функция, передаваемая в sort, должна удовлетворять некоторым требованиям. Если она им не удовлетворяет, sort может работать некорректно. Это не обязательно связано со временем выполнения, там может какой-нибудь index out of bounds происходить, да хоть вообще rm -rf.
                2. Нативный код совершенно не обязательно будет работать быстрее JS (погуглите fast.js). А если и будет, то в конечное число раз. В два, в три, в шесть. Давайте назовём это число K.
                3. У случайной сортировки хуже асимптотика. Она требует в log(n) раз больше операций, чем Фишер-Йетс. А log(n) растёт неограниченно, и рано или поздно он превысит K и сожрёт всё преимущество нативного кода (если оно вообще было).
                4. Если функция однострочная, это совершенно не значит, что она быстрая. Особенно если она вызывается много раз. Допустим, у вас там для каждого элемента конструируется ещё дополнительный маленький массив. На самом деле это не сильно повлияет на скорость, но вы этого не знаете, это знаю я. Что приводит нас к следующему пункту:
                5. Профилирование и бенчмарки — наше всё. Представьте на секунду, что на хабре сидят не сплошные идиоты. Допустите крупицу сомнения. А потом просто, чёрт побери, возьмите и сравните свой подход с предложенным. Проведите тесты и выясните истину лично, не полагаясь на всякие мутные рассуждения про «нет циклов» и «должны быть скомпилированными».
                6. Если вы успешно проигнорировали предыдущие пять пунктов — наслаждайтесь страданием. На этом, пожалуй, закончу.

                • eavprog
                  /#20503451 / -1

                  Сожалею, что эта статья вызвала у вас волну гнева. Мне нужно было сразу описать ограничения — применение в облаке Google. Хотелось поделиться удачным решением. Ошибки то больше не приходят. И система перестала останавливать скрипты из-за перерасхода времени выполнения.


                  Когда достигну следующего потолка, обязательно обращусь сюда за дальнейшими совершенствованиями кода.


                  Профилирования там нет. Но можно выводить время в лог. Но результат достигнут. А лучшее — враг хорошего.


                  Подключать библиотечные модули себе дороже. Об этом они сами пишут в помощи. Это только тормозит систему. А то давно бы уже туда свои нейросети всунул.


                  Боюсь мне все же придется в ближайшее время наращивать производительность. И тогда наверняка придется пробовать и предлагаемую сортировку. Но боюсь Google Script — это обычный интерпретатор и у него шаги между строк на порядок медленнее чем в скомпилированном варианте.


                  Но это уже тема для следующей статьи. И естественно жду очередную волну вашего гнева. И естественно я только "ЗА".

                  • Sirion
                    /#20503707

                    Да какой, к чёрту, гнев? У меня испанский стыд)

                    Лучше не пишите следующую статью. Писать надо о том, в чём разбираешься. Даже если предположить, что вы нашли удачное решение (а это не так, но я математик, я умею делать выводы из абсурдных предположений) — у вас материала максимум для ответа на тостере. Если на хабр начнут постить каждое найденное решение каждой встреченной проблемы, тут будет ещё большая помойка, чем сейчас.

              • Zenitchik
                /#20505253

                К сожалению у меня каждый день приходили ошибки чрезмерного использования времени работы скрипта.

                Иными словами, Вам не составит труда, описать что Вы сортировали, и сколько времени это заняло? Прошу!

            • eavprog
              /#20503033

              Но на си конечно ваше решение будет быстрее. У меня интерпретатор.

              • greg123
                /#20506059

                Я, конечно, всегда скептически относился к утверждениям о том, что javascript, java и прочее, выполняется так же быстро, как код, скомпилированный под целевую платформу, но не до такой же степени. Я честно, ни малейшег опредставления не имею о том, что происходит в вашем облаке, но я могу предположить, что с большой долей вероятности ваш код на js компилируется в некий промежуточный код, который и исполняется. Поверьте, никто не будет парсить тело цикла на каждой итерации. Вы просто ударяетесь в крайности. Я как-то встретил человека, который полагал, что чем меньше размер инструкции (в байтах), тем быстрее она выполняется процессором. У вас очень похожее заблуждение — вы пытаетесь написать не эффективный, а компактный код.

  6. 4eyes
    /#20501655

    Ёлки-палки, чем вам Knuth shuffle не угодил? У вас выше сложность (n log n, если я не ошибаюсь), и скорее всего, распределение далеко от случайного.

  7. igormich88
    /#20501671

    Я попробовал сравнить ваш метод и первый попавшийся пример со Stack Overflow с перемещением элементов внутри for — тест
    Результаты в моём браузере:

    • Пример со SO 972 ops/s ±0.62%
    • Ваш код 6 ops/s ±8.98%

    • JekaMas
      /#20502097

      Правильный подход. Автору статьи, вероятно, стоило начать с точного описания задачи: какие наборы данных, какие требования к ресурсам, к вычислительной сложности алгоритма. И потом сразу написать бенчмарки.