Shuffling Javascript Array elegant

Question

Es gibt einige bestehende Threads über Shuffle JS-Arrays, aber sie scheinen alle nicht trivial und nicht elegant, bestehend aus vielen Zeilen Code.

ich einige Blog gestoßen, die die folgende Zeile ein „Abhilfe“ schlägt vor:

yourArray.sort(function() { return 0.5 - Math.random() }); 

Wenn Sie, sind nicht vertraut mit, wie Sortieralgorithmen arbeiten werde ich hier kurz erklären, dass es immer um den Vergleich von zwei Werten ist des Arrays und dann eine Entscheidung treffen. Die vorgeschlagene Lösung "überschreibt" die Standardvergleichsfunktion mit einer anderen Funktion, die für jeden Vergleich von zwei Zellen einen zufälligen Wert erzeugt (bei jedem Vergleich wird nach dem Zufallsprinzip entschieden, welcher größer als der ist).

Das Problem damit ist, dass ich nicht wissen kann, welcher Sortieralgorithmus von jedem Webbrowser verwendet wird. Für einige Sortieralgorithmen, z.B. BubbleSort, eine solche Funktion wird wahrscheinlich dazu führen, dass der Sortieralgorithmus für immer ausgeführt wird, da es 1/2^(Länge) Wahrscheinlichkeit haben, einen Lauf ohne Swap zu haben. Es scheint auch für Quicksort problematisch zu sein. Ich denke, es regelmäßig nur zu beenden, wenn der Web-Browser MergeSort oder HeapSort

Hat jemand versuchen, es benutzt und kann sagen, ob es sicher ist oder auf eine andere Lösung empfehlen?

Answer 1

Der "Workaround" ist eine schreckliche Idee. Es ist ineffizient (viele weitere Aufrufe an Math.random() als nötig) und, wie Sie angemerkt haben, ist gefährlich für einige Sortieralgorithmen zu verwenden. Es ist auch voreingenommen (zumindest für die Version von sort() in meiner Installation von NodeJS, obwohl ich nicht erklären kann, warum). Hier ist ein typisches Ergebnis des Sortierens der Anordnung [1, 2, 3] 60.000 Mal und das Zählen, wie viele jeder Permutation auftaucht:

[1, 2, 3]: 14.821 mal
[1, 3, 2]: 7.637 mal
[2, 1, 3]: 15.097 mal
[2, 3, 1]: 7.590 mal
[3, 1, 2]: 7.416 mal
[3, 2, 1]: 7.439 mal

Für eine unvoreingenommene Shuffle sollten die sechs Permutationen erscheinen Gl oft im Durchschnitt (etwa 10.000 mal für 60.000 Wiederholungen). In meinen Experimenten treten [1, 2, 3] und [2, 1, 3] etwa doppelt so oft auf wie die anderen vier Permutationen. Dies ist über viele Tests hinweg konsistent.

Sie sind viel besser kleben mit dem Standard Fisher-Yates Shuffle (beschrieben in this Wikipedia article und viele andere Orte im Internet). In Pseudo-Code, es sieht aus wie dieser (vom Wikipedia-Artikel entnommen):

-- To shuffle an array a of n elements (indices 0..n-1): 
for i from n−1 downto 1 do 
    j ← random integer such that 0 ≤ j ≤ i 
    exchange a[j] and a[i] 

Nicht zu kompliziert und auf jedem Fall einen besseren Ansatz. Hier ist meine JavaScript-Version (die könnte möglicherweise ein wenig aufgeräumt werden):

P.S.Als Referenz, hier ist der Code, den ich verwendet, um Ihre Problemumgehung zu testen:

function shuffleRandomSort(a) { 
    a.sort(function() { return 0.5 - Math.random() }); 
    return a; 
} 

function score(scores, result) { 
    var index; 
    if (result[0] === 1) { 
     index = result[1] === 2 
      ? 0 // [1, 2, 3] 
      : 1; // [1, 3, 2] 
    } else if (result[0] === 2) { 
     index = result[1] === 1 
      ? 2 // [2, 1, 3] 
      : 3; // [2, 3, 1] 
    } else { // result[0] === 3 
     index = result[1] === 1 
      ? 4 // [3, 1, 2] 
      : 5; // [3, 2, 1] 
    } 
    scores[index]++; 
} 

function runTest(shuffler, n) { 
    var scores = [0, 0, 0, 0, 0, 0], 
     a; 
    for (var i = 0; i < n; ++i) { 
     a = [1, 2, 3]; 
     score(scores, shuffler(a)); 
    } 
    console.log(scores); 
} 

console.log(shuffleRandomSort, runTest(60000)); 

Answer 2

ich einige Algorithmen gepackt und testete sie mit console.time, können Sie die Ergebnisse sehen zu laufen sie:

var smallArray = Array.from({ length: 10 }, (x, i) => i); 
 
var bigArray = Array.from({ length: 1000 }, (x, i) => i); 
 

 
function shuffle1(array) { 
 
    var currentIndex = array.length, temporaryValue, randomIndex; 
 

 
    while (currentIndex) { 
 
    randomIndex = (Math.random() * currentIndex) | 0; 
 
    currentIndex -= 1; 
 

 
    temporaryValue = array[currentIndex]; 
 
    array[currentIndex] = array[randomIndex]; 
 
    array[randomIndex] = temporaryValue; 
 
    } 
 
} 
 

 
function shuffle2(arr) { 
 
    return _.shuffle(arr); 
 
} 
 

 
function shuffle3(arr) { 
 
    for (let i = arr.length - 1; i >= 0; --i) { 
 
    let j = (Math.random() * i) | 0; 
 
    [arr[i], arr[j]] = [arr[j], arr[i]]; 
 
    } 
 
} 
 

 
// inconsistent speeds 
 
function shuffle4(arr) { 
 
    arr.sort(function() { return 0.5 - Math.random() }); 
 
} 
 

 
function test(label, fn) { 
 
    console.time(label); 
 
    for (let i = 0; i < 1000; ++i) { 
 
    fn(); 
 
    } 
 
    console.timeEnd(label); 
 
} 
 

 
// time in comments based on Chrome 55 
 

 
let sa1 = smallArray.slice(0); 
 
let sa2 = smallArray.slice(0); 
 
let sa3 = smallArray.slice(0); 
 
let sa4 = smallArray.slice(0); 
 
test('smallArray shuffle1',() => shuffle1(sa1)); // 0.785ms 
 
test('smallArray shuffle2',() => shuffle2(sa2)); // 1.830ms 
 
test('smallArray shuffle3',() => shuffle3(sa3)); // 5.540ms 
 
test('smallArray shuffle4',() => shuffle4(sa4)); // 3.995ms 
 

 
let ba1 = bigArray.slice(0); 
 
let ba2 = bigArray.slice(0); 
 
let ba3 = bigArray.slice(0); 
 
let ba4 = bigArray.slice(0); 
 
test('bigArray shuffle1',() => shuffle1(ba1)); // 14.195ms 
 
test('bigArray shuffle2',() => shuffle2(ba2)); // 24.645ms 
 
test('bigArray shuffle3',() => shuffle3(ba3)); // 119.425ms 
 
test('bigArray shuffle4',() => shuffle4(ba4)); // 249.930ms

<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.4/lodash.min.js"></script>