Статьи

JavaScript: тасование по сортировке

Октябрь 26, 2017

Я признаю, что это действительно дурацкий, так что садитесь и читайте это медленно. Это нормально, если вам нужно сделать передышку и очистить свой разум. Я впервые столкнулся с этим маленьким взломом .

Ситуация такова: у вас есть массив, и вам нужно перемешать элементы в массиве. Теперь, будучи фанатом Кнута , я сразу же полезу в 3-й том «Искусства компьютерного программирования» , проверим, что Кнут говорит об этом, и напишу его:

var shuffle = function (a) {
  var randomIndex, temp, i = a.length;
  while (--i) {
    randomIndex = Math.floor(i * Math.random());
    if (randomIndex !== i) {
      temp = a[i];
      a[i] = a[randomIndex];
      a[randomIndex] = temp;
    }
  }
};

По сути (и игнорируя некоторую проверку ошибок): отсчитывая от вершины массива, выберите случайный элемент в том, что осталось от массива, и поменяйте местами элементы. Кнут говорит и доказывает, почему это лучший способ перестановки массива.

Представьте мое удивление, когда однажды во время серфинга я наткнулся на эту версию шаффла:

var shuffle = function (a) {
  a.sort(function () {
    return Math.random() - 0.5;
  });
};

Используя функцию сортировки, чтобы перемешать? Стреляй в меня сейчас.

Давайте посмотрим на это внимательно. Функция сортировки может принимать функцию в качестве первого параметра. Эта функция должна принимать два параметра, a и b, и возвращать числовое значение. Если это меньше нуля, то a сортируется по более низкому индексу, чем b (если вам нравится, в некотором смысле, a <b). Если он возвращает число больше нуля, происходит обратное, и b сортируется по индексу ниже, чем a. Если они равны, элементы не перемещаются относительно друг друга (теоретически, но на практике этого не происходит; по сути, соблюдение этого правила является различием между стабильным и нестабильным типом). Если эта функция сравнения отсутствует, функция сортировки преобразует каждую пару элементов в строки и выполняет лексическое сравнение между ними. Это приводит к странным эффектам как это:

var a = [1, 2, 4, 3, 7, 8, 60, 5];
a.sort();
console.log(a) // prints [1, 2, 3, 4, 5, 60, 7, 8]

… Потому что строка «60» лексически меньше строки «7». Уч. BEWARE!

В любом случае, наша функция сравнения в стиле фанк возвращает случайное число от –0,5 до 0,5. Половина времени возвращает число меньше нуля (поэтому пара элементов сортируется в смысле «меньше чем»), а половину — число больше нуля (поэтому пара элементов сортируется «больше чем») , И я должен был бы сказать, что это похоже на работу, хотя это пугает меня до чертиков.

Зачем? Ну, для начала реализация сортировки в браузере, по всей вероятности, делается с помощью быстрой сортировки. Какой конкретный вкус быстрой сортировки неизвестен (разные вкусы будут зависеть от того, какой элемент будет выбран). Независимо от того, как именно это делается, одно из главных допущений, которое делается в реализации, заключается в том, что функция сравнения не является ложью . Если a меньше b, сравнение будет возвращать меньше нуля, каждый раз . Если это врет, ни ты, ни я не имеем ни малейшего представления, как это будет вести себя.

Краткая история, чтобы проиллюстрировать мои опасения. Около 15 лет назад, возможно, даже больше, я отвечал за поддержку библиотеки Delphi под названием B-Tree Filer. У него была процедура, которая сортировала виртуальный массив с использованием реализации сортировки слиянием. Один из параметров назывался LessThan , и предполагалось, что это функция, принимающая два параметра и возвращающая true, если первый был меньше второго, в противном случае — false. Все мои проблемы поддержки, связанные с этой процедурой («Эй, это неправильно сортирует. Ваш код — отстой!») Были легко решены, когда я объяснил, что «меньше чем» не означает «меньше или равно ». С тех пор я был очень осторожен, когда имел дело с сортировками, и быстрая сортировка — лишь один из тех темпераментных алгоритмов, с которыми вы работаете в детских перчатках.

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

Второе замечание, которое нужно сделать, — это быстрые сортировки O ( n × log n ), поэтому перетасовка через сортировку также будет иметь эту характеристику производительности. Звучит достаточно быстро, но правильный алгоритм тасования, который я представил выше, это O ( n ). Это быстрее для больших массивов (маленькие массивы слишком малы, чтобы иметь значение). Зачем использовать более медленный алгоритм, если правильный алгоритм быстрее?

35
Share: