Why everybody is using reservoir sampling?


  • 0

    Using reservoir sampling, for each getRandom(), you need to traverse the entire list. Why not just count the length of the list, and then pick the random()%size th node? The average traverse length is just n/2.

    What is the benefit of doing reservoir sampling?

    Please don't say saving the length takes extra space, because saving the list head also uses space. I don't think O(1) space should be counted as extra space.


  • 0

    Your title claim is false. Not everybody is using reservoir sampling. For example this doesn't, and it already made the same point you're making.


  • 0

    @StefanPochmann Yes, you are correct. I should say "why so many posts are using".


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.