Something I've thought about recently: Fisher-Yates has an O(n) complexity, but it does several n operations.
copying the original source in an array
generating n random indexes
reading and writing n numbers (when swapping)
In an online scenario, something like C# Linq, if you want to shuffle the elements, then take only a few, many implementations do ToArray().ShuffleWithFisherYates().Take(k). An improvement would be to create the array, but then yield the values of the swaps in the loop, which would eliminate the overhead of randomizing the entire array for nothing. Even better, although it might be overkill, copy the items in the original source in the array only when you need a certain index. If FY decides it wants to swap index 1 with index 3 you only need to copy the first four elements from the original source. You do need to know the total length though.
Just a thought.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Something I've thought about recently: Fisher-Yates has an O(n) complexity, but it does several n operations.
In an online scenario, something like C# Linq, if you want to shuffle the elements, then take only a few, many implementations do ToArray().ShuffleWithFisherYates().Take(k). An improvement would be to create the array, but then yield the values of the swaps in the loop, which would eliminate the overhead of randomizing the entire array for nothing. Even better, although it might be overkill, copy the items in the original source in the array only when you need a certain index. If FY decides it wants to swap index 1 with index 3 you only need to copy the first four elements from the original source. You do need to know the total length though.
Just a thought.