DEV Community

Discussion on: Random Number and Card Shuffling Algorithm

Collapse
 
costinmanda profile image
Costin Manda • Edited

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.