Re^3: rand + shift || pop

Shuffleing is O(n) and spliceing is O(1), this may matter if your array is large.

Update: Oops, my understanding of splice was wrong. See JavaFan and ikegami below.

Comment on Re^3: rand + shift \|\| pop Download Code

Replies are listed 'Best First'.
Re^4: rand + shift \|\| pop by JavaFan (Canon) on Dec 21, 2010 at 16:41 UTC
Actually, the expected running time of splicing is `Ω(n)`, as a random splice will have to move n/4 elements on average. If you want to repeatedly get a random element (without duplication), shuffle the array and use pop or shift, for a linear running time. Repeatedly splicing a random element has an expected running time of `Ω(n²)`.	[reply]
Re^4: rand + shift \|\| pop by ikegami (Patriarch) on Dec 21, 2010 at 17:21 UTC
It's only O(1) if you remove from the start or the end.	[reply]