Как рандомно расставить ключи массива?

Question

[Игорь]

Допустим есть массив ,который содержит элементы хтмл.

Как в массиве рандомно их переставить.

www.itsmycodeblog.com/shuffling-a-javascript-array

есть такое но оч большая функция.

может у джс есть метод такой?

хотелось бы в 1 макс 2 строки,а лучше метод)))

Желательно натив джс,но если на джиквери есть метод такой то ок.

Answer 1

[Вячеслав Лебедев]

В предоставленной ссылки функция на 3 строки :)
Почему не понравилось?

[12,4,16,3].sort(function() {
  return 0.5 - Math.random();
}); // [12, 16, 3, 4]

А вот все о сортировке.

Comments

[Игорь]

Близко к самому лучшему ответу.

[Игорь]

но я бы хотел что то такое arr.sort(-a,+b*v); и шобы рандом был)))

Answer 2

[GreatRash]

function shuffle(array) {	
	// original by: Jonas Raoni Soares Silva (http://www.jsfromhell.com)

	for (var j, x, i = array.length; i; j = parseInt(Math.random() * i), x = array[--i], array[i] = array[j], array[j] = x);
	return true;
}

Тасование Фишера-Йетса

Comments

[Вячеслав Лебедев]

Начинает очень быстро, а потом скорость падает.
(shuffle) 280,907 ops/sec vs (sort) 566,628 ops/sec

[GreatRash]

Вячеслав Лебедев: Вот тут в обсуждении пишут, что sort неравномерно перемешивает, видимо из-за особенностей Math.random.

[Вячеслав Лебедев]

GreatRash: значит тасование, что выше. он используется в underscore

Answer 3

[Mikhail Osher]

stackoverflow.com/a/6274381/790304

Answer 4

[Ainur Shakirov]

var arr = [1, 2, 3, 4, 5];

function compareRandom(a, b) {
  return Math.random() - 0.5;
}

arr.sort(compareRandom);

alert( arr ); // элементы в случайном порядке, например [3,5,1,2,4]

Comments

[Николай]

а какая сложность у вашего метода ? : ))))

[Вячеслав Лебедев]

Николай: в смысле на сколько это быстро? примерно 491,778 ops/sec вот тут можно тесты погонять: jsbench.github.io
А если сложность по читаемости, то более простого варианта никогда не встречал :)

[Николай]

Вячеслав Лебедев: всмысле какая алгоритмическая сложность вашей функции. Т.е. сколько операций потребуется чтобы сделать?

[Вячеслав Лебедев]

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

[Николай]

Вячеслав Лебедев: дело в том, что ваш метод теоретически может никогда не завершиться.

[Милок Мурлыка]

Николай: В методе sort, внутри самого интерпретатора JavaScript, реализован универсальный алгоритм сортировки. Как правило, это ««быстрая сортировка»», дополнительно оптимизированная для небольших массивов.

Он решает, какие пары элементов и когда сравнивать, чтобы отсортировать побыстрее. Мы даём ему функцию – способ сравнения, дальше он вызывает её сам.

[Вячеслав Лебедев]

Николай: как интересно, массив из миллиарда позиций? в каких случаях он не завершится?

[Николай]

Вячеслав Лебедев: проблема в том что для двух элементов а и b довольно вероятна ситуация когда сначала a > b, а затем a < b. Конечно с незавершиться я немного погорячился, но лишних перестановок явно будет много. При этом существует простой алгоритм, который за O(n) делает желаемое. Он кстати чуть ниже описан.

[Aves]

Вячеслав Лебедев: теоретически, даже на массиве из двух элементов он может бесконечно менять их местами, если функция сравнения будет по очереди возвращать результат разных знаков. На практике, конечно, рано или поздно происходят два одинаковых сравнения подряд, и перестановки кончаются. Проверил на простеньком примере - при количестве элементов 100 происходит примерно 500 перестановок, при 1000 - 8000, при 10000 - 115000.

jsbin.com/kovipuy/1/embed?js,console

В общем, это самый медленный способ из всех, которые можно придумать.

[Вячеслав Лебедев]

Николай: тогда нужно брать тасование, он не зря в underscore попал :)

[Милок Мурлыка]

Aves:
>> теоретически, даже на массиве из двух элементов он может бесконечно менять их местами
Глупость. Такого никогда не произойдет, два элемента между собой будут сравниваться только 1 раз.
>> В общем, это самый медленный способ из всех, которые можно придумать.
А сколько по вашему должно быть перестановок?

[Николай]

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

[Aves]

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

Перестановок не должно быть в 10 раз больше количества элементов.

[Николай]

Милок Мурлыка: не очень понятно, откуда взялась цифра 500 : ) Худший случай (очевидно возможный для любой входной последовательности ) для 100 элементов выполнит 10000 (!) перестановок. Разговор был начат о том, что использование сортировок для "несортировки" - это плохо.

[Милок Мурлыка]

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

[Aves]

Николай: это эмпирическая цифра. Худший вариант вряд ли достижим, в движках всё-таки куча оптимизаций, и в целом нативная сортировка очень эффективна.

Милок Мурлыка: у нас с Николай похоже в принципе одинаковое мнение. Для демонстрации сделал еще пример - jsbench.github.io/#91eb28ae31e9aafc2abb0c1fc223157f
на 1000 элементах разница больше чем в 10 раз.

[Вячеслав Лебедев]

Aves: а вот этот код я утащу к себе, итерирует быстрее чем в 15 раз, с ума сойти, спасибо))
а то мне не нравится underscore решение, куча кода и разбираться минимум пол часа, что от куда вызывается)))

[Вячеслав Лебедев]

Aves: ого, разобрался в коде... переписал кое что, apply это медленно, зачем map?, можно же проще. 1М итераций - нативный способ выиграл в 8 раз :)
jsbench.github.io/#91eb28ae31e9aafc2abb0c1fc223157f

[Aves]

Вячеслав Лебедев: у меня по ссылке мой вариант открывается. Но подозреваю что вы создаёте массив как Array(1000000). С элементами undefined sort функцию сравнения вообще ни разу не будет выполнять. Для этого я apply и map и использовал, чтобы создать заполненный индексами элементов массив [0, 1, 2, 3, ..., n]. Ну для массива с миллионом элементов это не подходит, поэтому можно просто

var arr = [];
for (var i = 0; i < 1000000; i++) arr.push(i);

Сделал так по ссылке, и sort медленнее больше чем в 20 раз.

[Aves]

Вячеслав Лебедев: а underscore решение в принципе точно такое же, только там тело цикла засунуто в оператор for.