array_swap_pop_random

[Mercerenies]

A small thought I had while looking at the example code for array_pop_random. Calling array_pop_random in a loop to get several values will be really slow, since every pop is O(n) and has to shift the remainder of the array backward.

The Rust programming language deals with this problem by providing two "pop" functions. Regular Vec::remove just takes the element out of the vector and shifts everything to the right over by one, as we do in array_pop_random. But there's also Vec::swap_remove, which removes the element from the vector but replaces it with the last element of the vector. So if our vector contained

[10, 20, 30, 40, 50]

and we did my_vec.swap_remove(2), we remove the 30 and the resulting vector is

[10, 20, 50, 40]

The benefit to this is that, although we forgot the order of the elements, the removal was O(1) since we only had to swap one element, not several. This is far more efficient, provided you don't care about the order of your vector elements. And since the most common use case for array_pop_random will be drawing random cards (or something like cards) from a deck, I figure our use case here is similar.

So I propose array_swap_pop_random (I'm not married to the name), which takes the same arguments as array_pop_random but does the swap-and-remove trick to pop its element in O(1) time.

array_swap_pop_random(array, [offset], [length])

[Alphish]

I suggest also making a separate request for arrray_swap_pop(array,index), since the swap-and-pop deletion has applications for deterministic removal as well (I might have used that pattern on various occasions).