added shuffle to list #2066
added shuffle to list #2066
Conversation
|
|
| while (current) { | ||
| destination = Math.floor(random() * current--); | ||
|
|
||
| tmp = mutable.get(destination); |
There was a problem hiding this comment.
does it need to check for no-op changes, where destination == source?
There was a problem hiding this comment.
tbh i just took the fisher-yates algorithm as it is without tinkering with it
imho the "source = destination" case would likely happen with small lists, in which case performance is not really an issue
in huge lists, the probability is much smaller, therefore i think the "cost" of the "if equals" would be greater than the potential gain from it, wdyt ?
i admit that i didn't run any benchmark for this 😅 🙏
There was a problem hiding this comment.
I was mainly thinking of how good the shuffle is, if it could end up not doing anything. But I am also not sure if I have a logical error in my reasoning of how the algorithm works 😄
There was a problem hiding this comment.
@bdurrer you can read about the FIsher-Yates algorithm here: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
I tried to shuffle 100000 times an array and the repartition seems pretty good.
hmm not sure we need cryptographically strong random values here 🤔 i would go for speed here no ? |
|
Don't bother testing flow. I'm 🤏 to drop support. |
|
Thanks @mazerty . I will release that in the next minor. |
As seen together, here's the shuffle function for the List :)
Sorry for the "mess" with the two new packages for the random number generator, it was the only way I could find to import it in the test 😬
Also I tried to add a test in the
immutable-flow.jsfile, but I don't really understand how it works 😅