Czy poprawne jest użycie metody JavaScript Array.sort () do odtwarzania losowego?

Pomagałem komuś z jego kodem JavaScript i moje oczy zwróciły się na sekcję, która wyglądała tak:

function randOrd(){
  return (Math.round(Math.random())-0.5);
}
coords.sort(randOrd);
alert(coords);

Moja pierwsza myśl brzmiała: hej, to nie może zadziałać! Ale potem trochę poeksperymentowałem i stwierdziłem, że rzeczywiście przynajmniej wydaje się dostarczać ładnie zrandomizowanych wyników.

Potem przeszukałem sieć i prawie na górze znalazłem artykuł, z którego ten kod został najdokładniej skopiowany. Wyglądało na całkiem przyzwoitą witrynę i autora ...

Ale przeczucie podpowiada mi, że to musi być złe. Zwłaszcza, że ​​algorytm sortowania nie jest określony przez standard ECMA. Myślę, że różne algorytmy sortowania spowodują różne niejednorodne tasowania. Niektóre algorytmy sortowania mogą prawdopodobnie zapętlić się w nieskończoność ...

Ale co o tym myślisz?

A jako kolejne pytanie ... jak mam teraz zmierzyć, jak losowe są wyniki tej techniki tasowania?

aktualizacja: wykonałem kilka pomiarów i zamieściłem wyniki poniżej jako jedną z odpowiedzi.

To nigdy nie był mój ulubiony sposób tasowania, częściowo dlatego, że jest specyficzny dla implementacji, jak mówisz. W szczególności, wydaje mi się, że średnia z obu sortowania biblioteki Java lub .NET (nie wiem który) często można wykryć, jeśli kończy się z niespójnym porównania pomiędzy elementami (np ciebie pierwszego zastrzeżenia A < Bi B < C, ale potem C < A).

Kończy się również jako bardziej złożone (pod względem czasu wykonania) przetasowanie, niż naprawdę potrzebujesz.

Preferuję algorytm tasowania, który efektywnie dzieli kolekcję na „shuffled” (na początku kolekcji, początkowo pustą) i „unshuffled” (reszta kolekcji). Na każdym kroku algorytmu wybierz losowy nieprzetasowany element (może to być pierwszy) i zamień go na pierwszy nieprzetasowany element - następnie potraktuj go jako przetasowany (tj. Przesuń w myślach partycję, aby go uwzględnić).

To jest O (n) i wymaga tylko n-1 wywołań generatora liczb losowych, co jest miłe. Tworzy również prawdziwe tasowanie - każdy element ma 1 / n szansy, że znajdzie się w każdym polu, niezależnie od jego pierwotnej pozycji (zakładając rozsądny RNG). Posortowana wersja zbliża się do równomiernego rozkładu (zakładając, że generator liczb losowych nie wybiera dwukrotnie tej samej wartości, co jest wysoce nieprawdopodobne, jeśli zwraca losowe liczby podwójne), ale łatwiej jest mi rozumować co do wersji losowej :)

To podejście nazywa się tasowaniem Fishera-Yatesa .

Uważam, że najlepszą praktyką jest jednorazowe zakodowanie tego tasowania i ponowne użycie go wszędzie tam, gdzie trzeba tasować elementy. Wtedy nie musisz martwić się o implementacje sortowania pod względem niezawodności lub złożoności. To tylko kilka wierszy kodu (których nie będę próbował w JavaScript!)

Artykuł Wikipedii o tasowaniu (aw szczególności sekcja algorytmów tasowania) mówi o sortowaniu losowej projekcji - warto przeczytać sekcję o słabych implementacjach tasowania w ogóle, aby wiedzieć, czego unikać.

Po tym, jak Jon omówił już teorię , oto implementacja:

function shuffle(array) {
    var tmp, current, top = array.length;

    if(top) while(--top) {
        current = Math.floor(Math.random() * (top + 1));
        tmp = array[current];
        array[current] = array[top];
        array[top] = tmp;
    }

    return array;
}

Algorytm jest O(n), a sortowanie powinno O(n log n). W zależności od obciążenia związanego z wykonywaniem kodu JS w porównaniu z sort()funkcją natywną może to prowadzić do zauważalnej różnicy w wydajności, która powinna rosnąć wraz z rozmiarami tablic.

W komentarzach do odpowiedzi bobobobo stwierdziłem, że omawiany algorytm może nie dawać równomiernie rozłożonych prawdopodobieństw (w zależności od implementacji sort()).

Mój argument idzie w tym kierunku: algorytm sortowania wymaga pewnej liczby cporównań, np. c = n(n-1)/2Dla Bubblesort. Nasza funkcja porównania losowego sprawia, że ​​wynik każdego porównania jest równie prawdopodobny, tj. Istnieją 2^c równie prawdopodobne wyniki. Teraz każdy wynik musi odpowiadać jednej z n!permutacji wpisów tablicy, co w ogólnym przypadku uniemożliwia równomierne rozłożenie. (Jest to uproszczenie, ponieważ rzeczywista liczba niezbędnych porównań zależy od tablicy wejściowej, ale stwierdzenie powinno nadal obowiązywać).

Jak zauważył Jon, to samo w sobie nie jest powodem, aby preferować Fisher-Yatesa od używania sort(), ponieważ generator liczb losowych mapuje również skończoną liczbę wartości pseudolosowych do n!permutacji. Ale wyniki Fisher-Yatesa powinny być nadal lepsze:

Math.random()tworzy liczbę pseudolosową z zakresu [0;1[. Ponieważ JS używa wartości zmiennoprzecinkowych o podwójnej precyzji, odpowiada to 2^xmożliwym wartościom gdzie 52 ≤ x ≤ 63(jestem zbyt leniwy, aby znaleźć rzeczywistą liczbę). Rozkład prawdopodobieństwa wygenerowany za pomocą Math.random()przestanie działać dobrze, jeśli liczba zdarzeń atomowych jest tego samego rzędu wielkości.

Używając Fishera-Yatesa, odpowiednim parametrem jest rozmiar tablicy, która nigdy nie powinna się zbliżać 2^52ze względu na ograniczenia praktyczne.

Podczas sortowania za pomocą funkcji porównania losowego funkcja zasadniczo dba o to, czy wartość zwracana jest dodatnia czy ujemna, więc nigdy nie będzie to problemem. Ale jest podobny: ponieważ funkcja porównania zachowuje się dobrze, 2^cmożliwe wyniki są, jak stwierdzono, równie prawdopodobne. Jeśli c ~ n log nwtedy 2^c ~ n^(a·n)gdzie a = const, co sprawia, że ​​jest przynajmniej możliwe, że 2^cma taką samą wielkość jak (lub nawet mniej niż), n!a tym samym prowadzi do nierównomiernego rozkładu, nawet jeśli algorytm sortowania zakłada równomierne mapowanie na permutacje. Jeśli to ma jakikolwiek praktyczny wpływ, jest poza mną.

Prawdziwym problemem jest to, że algorytmy sortowania nie gwarantują równomiernego odwzorowania na permutacje. Łatwo zauważyć, że Mergesort działa tak, jak jest symetryczny, ale rozumowanie o czymś takim jak Bubblesort lub, co ważniejsze, Quicksort lub Heapsort, nie jest.

Podsumowując: tak długo, jak sort()używasz Mergesort, powinieneś być w miarę bezpieczny, z wyjątkiem przypadków narożnych (przynajmniej mam nadzieję, że 2^c ≤ n!jest to przypadek narożny), jeśli nie, wszystkie zakłady są wyłączone.

Zrobiłem kilka pomiarów tego, jak losowe są wyniki tego losowego sortowania ...

Moja technika polegała na pobraniu małej tablicy [1, 2, 3, 4] i utworzeniu jej wszystkich (4! = 24) permutacji. Następnie zastosowałbym funkcję tasowania do tablicy wiele razy i policzyłbym, ile razy każda permutacja jest generowana. Dobry algorytm tasowania rozłożyłby wyniki dość równomiernie na wszystkie permutacje, podczas gdy zły nie dałby takiego jednolitego wyniku.

Korzystając z poniższego kodu testowałem w Firefox, Opera, Chrome, IE6 / 7/8.

Zaskakujące jest dla mnie, że losowe sortowanie i prawdziwe tasowanie stworzyły równie jednolite rozkłady. Wygląda więc na to, że (jak wielu sugerowało) główne przeglądarki używają sortowania przez scalanie. Nie oznacza to oczywiście, że nie może być przeglądarki, która robi inaczej, ale powiedziałbym, że oznacza to, że ta metoda losowego sortowania jest wystarczająco niezawodna, aby można ją było zastosować w praktyce.

EDYCJA: Ten test nie zmierzył poprawnie losowości lub jej braku. Zobacz inną odpowiedź, którą opublikowałem.

Ale jeśli chodzi o wydajność, funkcja shuffle nadana przez Cristopha była wyraźnym zwycięzcą. Nawet w przypadku małych czteroelementowych tablic rzeczywiste tasowanie przebiegało około dwa razy szybciej niż sortowanie losowe!

// Funkcja odtwarzania losowego opublikowana przez Cristopha.
var shuffle = function (tablica) {
    var tmp, current, top = array.length;

    if (top) while (- top) {
        current = Math.floor (Math.random () * (top + 1));
        tmp = tablica [bieżąca];
        tablica [bieżąca] = tablica [góra];
        tablica [góra] = tmp;
    }

    return array;
};

// funkcja losowego sortowania
var rnd = function () {
  return Math.round (Math.random ()) - 0,5;
};
var randSort = function (A) {
  return A.sort (rnd);
};

var permutations = function (A) {
  if (A.length == 1) {
    powrót [A];
  }
  else {
    var perms = [];
    for (var i = 0; i <A.length; i ++) {
      var x = A. plastry (i, i + 1);
      var xs = A. plastry (0, i). concat (A. plastry (i + 1));
      var subperms = permutations (xs);
      for (var j = 0; j <subperms.length; j ++) {
        perms.push (x.concat (subperms [j]));
      }
    }
    powrót zezwoleń;
  }
};

var test = function (A, iterations, func) {
  // init permutacje
  var stats = {};
  var perms = permutations (A);
  for (var i in perms) {
    stats ["" + perms [i]] = 0;
  }

  // tasuj wiele razy i zbieraj statystyki
  var start = new Date ();
  for (var i = 0; i <iterations; i ++) {
    var shuffled = func (A);
    stats ["" + shuffled] ++;
  }
  var end = new Date ();

  // sformatuj wynik
  var arr = [];
  for (var i in stats) {
    arr.push (i + "" + stats [i]);
  }
  return arr.join ("\ n") + "\ n \ nPobrany czas:" + ((koniec - początek) / 1000) + "sekundy.";
};

alert ("losowe sortowanie:" + test ([1,2,3,4], 100000, randSort));
alert ("shuffle:" + test ([1,2,3,4], 100000, shuffle));

Co ciekawe, Microsoft zastosował tę samą technikę w swojej losowej-stronie-przeglądarki.

Użyli nieco innej funkcji porównania:

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

Dla mnie wygląda prawie tak samo, ale okazało się, że nie jest taki przypadkowy ...

Zrobiłem więc ponownie kilka testów z tą samą metodologią, co w połączonym artykule i rzeczywiście - okazało się, że metoda losowego sortowania dała błędne wyniki. Nowy kod testowy tutaj:

function shuffle(arr) {
  arr.sort(function(a,b) {
    return (0.5 - Math.random());
  });
}

function shuffle2(arr) {
  arr.sort(function(a,b) {
    return (Math.round(Math.random())-0.5);
  });
}

function shuffle3(array) {
  var tmp, current, top = array.length;

  if(top) while(--top) {
    current = Math.floor(Math.random() * (top + 1));
    tmp = array[current];
    array[current] = array[top];
    array[top] = tmp;
  }

  return array;
}

var counts = [
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0],
  [0,0,0,0,0]
];

var arr;
for (var i=0; i<100000; i++) {
  arr = [0,1,2,3,4];
  shuffle3(arr);
  arr.forEach(function(x, i){ counts[x][i]++;});
}

alert(counts.map(function(a){return a.join(", ");}).join("\n"));

Umieściłem prostą stronę testową w mojej witrynie, pokazującą stronniczość Twojej obecnej przeglądarki w porównaniu z innymi popularnymi przeglądarkami używającymi różnych metod odtwarzania losowego. Pokazuje straszną stronniczość zwykłego używania Math.random()-0.5, kolejne „losowe” tasowanie, które nie jest stronnicze, oraz wspomnianą powyżej metodę Fishera-Yatesa.

Widać, że w niektórych przeglądarkach istnieje aż 50% szansa, że ​​pewne elementy w ogóle nie zmienią się podczas „tasowania”!

Uwaga: możesz nieco przyspieszyć implementację tasowania Fisher-Yates przez @Christoph dla Safari, zmieniając kod na:

function shuffle(array) {
  for (var tmp, cur, top=array.length; top--;){
    cur = (Math.random() * (top + 1)) << 0;
    tmp = array[cur]; array[cur] = array[top]; array[top] = tmp;
  }
  return array;
}

Wyniki testu: http://jsperf.com/optimized-fisher-yates

Myślę, że jest to dobre w przypadkach, w których nie jesteś wybredny w dystrybucji i chcesz, aby kod źródłowy był mały.

W JavaScript (gdzie źródło jest stale przesyłane), mały ma wpływ na koszty przepustowości.

To z pewnością hack. W praktyce nieskończenie zapętlony algorytm jest mało prawdopodobny. Jeśli sortujesz obiekty, możesz zapętlić tablicę coords i zrobić coś takiego:

for (var i = 0; i < coords.length; i++)
    coords[i].sortValue = Math.random();

coords.sort(useSortValue)

function useSortValue(a, b)
{
  return a.sortValue - b.sortValue;
}

(a następnie ponownie przejrzyj je, aby usunąć sortValue)

Wciąż jednak hack. Jeśli chcesz zrobić to ładnie, musisz to zrobić na własnej skórze :)

Minęły cztery lata, ale chciałbym zwrócić uwagę, że metoda losowego komparatora nie będzie poprawnie dystrybuowana, niezależnie od używanego algorytmu sortowania.

Dowód:

1. W przypadku tablicy nelementów istnieją dokładnie n!permutacje (tj. Możliwe przetasowania).
2. Każde porównanie podczas tasowania to wybór między dwoma zestawami permutacji. W przypadku losowego komparatora istnieje 1/2 szansy na wybranie każdego zestawu.
3. Zatem dla każdej permutacji p szansa na uzyskanie permutacji p jest ułamkiem o mianowniku 2 ^ k (dla jakiegoś k), ponieważ jest to suma takich ułamków (np. 1/8 + 1/16 = 3/16 ).
4. Dla n = 3 istnieje sześć równie prawdopodobnych permutacji. Szansa na każdą permutację wynosi zatem 1/6. 1/6 nie może być wyrażona jako ułamek, którego mianownikiem jest potęga 2.
5. Dlatego sortowanie monet nigdy nie zapewni sprawiedliwego rozłożenia tasowań.

Jedyne rozmiary, które mogłyby być poprawnie rozmieszczone, to n = 0,1,2.

W ramach ćwiczenia spróbuj narysować drzewo decyzyjne różnych algorytmów sortowania dla n = 3.

Istnieje luka w dowodzie: jeśli algorytm sortowania zależy od spójności komparatora i ma nieograniczony czas działania z niespójnym komparatorem, może mieć nieskończoną sumę prawdopodobieństw, które mogą sumować się do 1/6, nawet jeśli każdy mianownik w sumie to potęga 2. Spróbuj znaleźć jeden.

Ponadto, jeśli komparator ma stałą szansę na udzielenie którejkolwiek odpowiedzi (np. (Math.random() < P)*2 - 1Stałej P), powyższy dowód jest ważny. Jeśli zamiast tego komparator zmieni swoje kursy na podstawie wcześniejszych odpowiedzi, możliwe będzie wygenerowanie uczciwych wyników. Znalezienie takiego komparatora dla danego algorytmu sortowania mogłoby być pracą badawczą.

Jeśli używasz D3, jest wbudowana funkcja tasowania (używając Fisher-Yates):

var days = ['Lundi','Mardi','Mercredi','Jeudi','Vendredi','Samedi','Dimanche'];
d3.shuffle(days);

A oto Mike omawia szczegóły na ten temat:

http://bost.ocks.org/mike/shuffle/

Oto podejście wykorzystujące pojedynczą tablicę:

Podstawowa logika to:

Kod:

for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);

Czy możesz użyć Array.sort()funkcji do tasowania tablicy - tak.

Czy wyniki są wystarczająco losowe - Nie.

Rozważ następujący fragment kodu:

var array = ["a", "b", "c", "d", "e"];
var stats = {};
array.forEach(function(v) {
  stats[v] = Array(array.length).fill(0);
});
//stats = {
//    a: [0, 0, 0, ...]
//    b: [0, 0, 0, ...]
//    c: [0, 0, 0, ...]
//    ...
//    ...
//}
var i, clone;
for (i = 0; i < 100; i++) {
  clone = array.slice(0);
  clone.sort(function() {
    return Math.random() - 0.5;
  });
  clone.forEach(function(v, i) {
    stats[v][i]++;
  });
}

Object.keys(stats).forEach(function(v, i) {
  console.log(v + ": [" + stats[v].join(", ") + "]");
})

Przykładowe dane wyjściowe:

a [29, 38, 20,  6,  7]
b [29, 33, 22, 11,  5]
c [17, 14, 32, 17, 20]
d [16,  9, 17, 35, 23]
e [ 9,  6,  9, 31, 45]

W idealnym przypadku liczby powinny być równomiernie rozłożone (w powyższym przykładzie wszystkie zliczenia powinny wynosić około 20). Ale tak nie jest. Najwyraźniej dystrybucja zależy od tego, jaki algorytm sortowania jest zaimplementowany przez przeglądarkę i jak iteruje elementy tablicy do sortowania.

Więcej informacji znajduje się w tym artykule:
Array.sort () nie powinien być używany do shuffle tablicy

Nie ma w tym nic złego.

Funkcja, którą przekazujesz do .sort () zwykle wygląda podobnie

function sortingFunc (pierwszy, drugi)
{
  // przykład:
  powrót pierwszy - drugi;
}

Twoim zadaniem w sortowaniuFunc jest powrót:

• liczba ujemna, jeśli pierwsza występuje przed drugą
• liczba dodatnia, jeśli pierwsza ma następować po drugiej
• i 0, jeśli są całkowicie równe

Powyższa funkcja sortowania porządkuje rzeczy.

Jeśli wrócisz losowo i + jako to, co masz, otrzymasz losową kolejność.

Jak w MySQL:

WYBIERZ * z tabeli ZAMÓW WEDŁUG rand ()