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

126

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.

Rene Saarsoo
źródło
tylko po to, aby zauważyć, że bezcelowe jest zaokrąglanie wyniku tylko do liczby znaków
bormat
2
Zauważyłem, że wygląda na to, że daje ładne, losowe wyniki. ” - NAPRAWDĘ ???
Bergi

Odpowiedzi:

109

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ć.

Jon Skeet
źródło
5
Raymond Chen szczegółowo omawia
Jason Kresowaty
1
jeśli moje rozumowanie jest poprawne, posortowana wersja nie daje „prawdziwego” tasowania!
Christoph,
@Christoph: Myśląc o tym, nawet Fisher-Yates poda "idealny" rozkład tylko wtedy, gdy gwarantuje się, że rand (x) będzie dokładnie równy. Biorąc pod uwagę, że zwykle istnieją 2 ^ x możliwe stany dla RNG dla niektórych x, nie sądzę, że będzie to dokładnie równe dla rand (3).
Jon Skeet
@Jon: ale Fisher-Yates utworzy 2^xstany dla każdego indeksu tablicy, tj. Będzie łącznie 2 ^ (xn) stanów, co powinno być trochę większe niż 2 ^ c - szczegóły w mojej zredagowanej odpowiedzi
Christoph
@Christoph: Być może nie wyjaśniłem się poprawnie. Załóżmy, że masz tylko 3 elementy. Pierwszy element wybierasz losowo, spośród wszystkich 3. Aby uzyskać całkowicie jednolity rozkład, musiałbyś być w stanie wybrać losową liczbę z zakresu [0,3) całkowicie jednolicie - i jeśli PRNG ma 2 ^ n możliwych stanów, nie możesz tego zrobić - jedna lub dwie możliwości będą miały nieco większe prawdopodobieństwo wystąpienia.
Jon Skeet
118

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.

Christoph
źródło
Dzięki za realizację. Jest niesamowicie szybki! Szczególnie w porównaniu z tym powolnym bzdurą, którą w międzyczasie sam napisałem.
Rene Saarsoo
1
Jeśli używasz biblioteki underscore.js, oto jak ją rozszerzyć za pomocą powyższej metody tasowania Fishera-Yatesa: github.com/ryantenney/underscore/commit/ ...
Steve,
Bardzo dziękuję za to, połączenie Twojej i Johna odpowiedzi pomogło mi rozwiązać problem, nad którym ja i kolega spędziliśmy łącznie prawie 4 godziny! Początkowo mieliśmy metodę podobną do OP, ale stwierdziliśmy, że randomizacja była bardzo niestabilna, więc wzięliśmy twoją metodę i nieznacznie ją zmieniliśmy, aby działała z odrobiną jquery, aby pomieszać listę obrazów (dla suwaka), aby uzyskać trochę niesamowita randomizacja.
Hello World,
16

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));
Rene Saarsoo
źródło
11

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"));
Rene Saarsoo
źródło
Nie rozumiem, dlaczego musi to być 0,5 - Math.random (), dlaczego nie tylko Math.random ()?
Alexander Mills
1
@AlexanderMills: Przekazana funkcja komparatora sort()ma zwrócić liczbę większą niż, mniejszą lub równą zeru, w zależności od porównania ai b. ( developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… )
LarsH,
@LarsH yeah, to ma sens
Alexander Mills,
9

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

Phrogz
źródło
5

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.

Nosredna
źródło
2
Chodzi o to, że prawie zawsze jesteś bardziej wybredny, jeśli chodzi o dystrybucję, niż myślisz, a dla „małego kodu” zawsze jest arr = arr.map(function(n){return [Math.random(),n]}).sort().map(function(n){return n[1]});, co ma tę zaletę, że nie jest zbyt strasznie dużo dłuższe i właściwie dystrybuowane. Istnieją również bardzo skompresowane warianty odtwarzania losowego Knuth / FY.
Daniel Martin,
@DanielMartin Ta jedna linijka powinna być odpowiedzią. Ponadto, aby uniknąć błędów analizowania dwa średniki należy dodać więc wygląda to tak: arr = arr.map(function(n){return [Math.random(),n];}).sort().map(function(n){return n[1];});.
Giacomo1968
2

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

Thorarin
źródło
2

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ą.

leewz
źródło
1

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/

Renaud
źródło
0

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

Podstawowa logika to:

  • Zaczynając od tablicy n elementów
  • Usuń losowy element z tablicy i wepchnij go do tablicy
  • Usuń losowy element z pierwszych n - 1 elementów tablicy i wepchnij go do tablicy
  • Usuń losowy element z pierwszych n - 2 elementów tablicy i wepchnij go do tablicy
  • ...
  • Usuń pierwszy element tablicy i wepchnij go na tablicę
  • Kod:

    for(i=a.length;i--;) a.push(a.splice(Math.floor(Math.random() * (i + 1)),1)[0]);
    ic3b3rg
    źródło
    Twoja implementacja wiąże się z dużym ryzykiem, że znaczna liczba elementów pozostanie nietknięta. Zostaną po prostu przesunięte w całej tablicy o liczbę gorszych elementów, które zostały wypchnięte na górę. W tym tasowaniu rysuje się wzór, który czyni go zawodnym.
    Kir Kanos
    @KirKanos, nie jestem pewien, czy rozumiem twój komentarz. Rozwiązanie, które proponuję, to O (n). Z pewnością „dotknie” każdego elementu. Oto skrzypce do zademonstrowania.
    ic3b3rg
    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

    Salman A
    źródło
    -3

    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 ()
    
    bobobobo
    źródło
    5
    tam jest coś złego w tym podejściu: w zależności od algorytmu sortowania używanej przez implementację JS, prawdopodobieństwa nie będą równomiernie rozłożone!
    Christoph,
    Czy to jest coś, czym praktycznie się martwimy?
    bobobobo
    4
    @bobobobo: w zależności od aplikacji tak, czasami robimy; ponadto, poprawnie działający shuffle()wystarczy napisać tylko raz, więc nie stanowi to problemu: po prostu umieść fragment kodu w skarbcu kodu i odkop go, kiedy tylko potrzebujesz
    Christoph