Oto zoptymalizowana wersja kodu przeniesionego z Pythona przez @Derek, z dodaną opcją destrukcyjną (w miejscu), która sprawia, że jest to najszybszy możliwy algorytm, jeśli możesz z nim skorzystać. W przeciwnym razie albo tworzy pełną kopię, albo w przypadku niewielkiej liczby elementów żądanych z dużej tablicy przełącza się na algorytm oparty na wyborze.
function sample(pool, k, destructive) {
var n = pool.length;
if (k < 0 || k > n)
throw new RangeError("Sample larger than population or is negative");
if (destructive || n <= (k <= 5 ? 21 : 21 + Math.pow(4, Math.ceil(Math.log(k*3) / Math.log(4))))) {
if (!destructive)
pool = Array.prototype.slice.call(pool);
for (var i = 0; i < k; i++) {
var j = i + Math.random() * (n - i) | 0;
var x = pool[i];
pool[i] = pool[j];
pool[j] = x;
}
pool.length = k;
return pool;
} else {
var selected = new Set();
while (selected.add(Math.random() * n | 0).size < k) {}
return Array.prototype.map.call(selected, i => pool[i]);
}
}
W porównaniu z implementacją Dereka, pierwszy algorytm jest znacznie szybszy w Firefoksie, a nieco wolniejszy w Chrome, chociaż teraz ma destrukcyjną opcję - najbardziej wydajną. Drugi algorytm jest po prostu szybszy o 5-15%. Staram się nie podawać żadnych konkretnych liczb, ponieważ różnią się one w zależności od k i ni prawdopodobnie nie będą miały żadnego znaczenia w przyszłości w nowych wersjach przeglądarek.
Heurystyka, która dokonuje wyboru między algorytmami, pochodzi z kodu Pythona. Zostawiłem go tak, jak jest, chociaż czasami wybiera wolniejszy. Powinien być zoptymalizowany pod kątem JS, ale jest to złożone zadanie, ponieważ wydajność przypadków narożnych zależy od przeglądarki i ich wersji. Na przykład, gdy spróbujesz wybrać 20 z 1000 lub 1050, przełączy się odpowiednio na pierwszy lub drugi algorytm. W tym przypadku pierwszy z nich działa 2x szybciej niż drugi w Chrome 80, ale 3x wolniej w Firefoksie 74.