bencharks
Let's first see the results then we'll look at each implementation of shuffle below -
splice is slow
Any solution using splice or shift in a loop is going to be very slow. Which is especially noticeable when we increase the size of the array. In a naive algorithm we -
- get a
rand position, i, in the input array, t
- add
t[i] to the output
splice position i from array t
To exaggerate the slow effect, we'll demonstrate this on an array of one million elements. The following script almost 30 seconds -
const shuffle = t =>
Array.from(sample(t, t.length))
function* sample(t, n)
{ let r = Array.from(t)
while (n > 0 && r.length)
{ const i = rand(r.length) // 1
yield r[i] // 2
r.splice(i, 1) // 3
n = n - 1
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via splice")
const result = shuffle(bigarray)
console.timeEnd("shuffle via splice")
document.body.textContent = JSON.stringify(result, null, 2)
body::before {
content: "1 million elements via splice";
font-weight: bold;
display: block;
}
pop is fast
The trick is not to splice and instead use the super efficient pop. To do this, in place of the typical splice call, you -
- select the position to splice,
i
- swap
t[i] with the last element, t[t.length - 1]
- add
t.pop() to the result
Now we can shuffle one million elements in less than 100 milliseconds -
const shuffle = t =>
Array.from(sample(t, t.length))
function* sample(t, n)
{ let r = Array.from(t)
while (n > 0 && r.length)
{ const i = rand(r.length) // 1
swap(r, i, r.length - 1) // 2
yield r.pop() // 3
n = n - 1
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle via pop")
const result = shuffle(bigarray)
console.timeEnd("shuffle via pop")
document.body.textContent = JSON.stringify(result, null, 2)
body::before {
content: "1 million elements via pop";
font-weight: bold;
display: block;
}
even faster
The two implementations of shuffle above produce a new output array. The input array is not modified. This is my preferred way of working however you can increase the speed even more by shuffling in place.
Below shuffle one million elements in less than 10 milliseconds -
function shuffle (t)
{ let last = t.length
let n
while (last > 0)
{ n = rand(last)
swap(t, n, --last)
}
}
const rand = n =>
Math.floor(Math.random() * n)
function swap (t, i, j)
{ let q = t[i]
t[i] = t[j]
t[j] = q
return t
}
const size = 1e6
const bigarray = Array.from(Array(size), (_,i) => i)
console.time("shuffle in place")
shuffle(bigarray)
console.timeEnd("shuffle in place")
document.body.textContent = JSON.stringify(bigarray, null, 2)
body::before {
content: "1 million elements in place";
font-weight: bold;
display: block;
}
