11–20 of 83 posts
Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?
Nonetheless, I find this coding style unreadable. "Y" is not a very good name for an exponentially distributed random variate, especially in a function that defines 24 variables with mostly meaningless names. :-(
Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?
The nicer way to do this is to have two lists. Put all of your cards into the first list. Choose a number between 1 and the length of list 1, then remove that element from the list and add it to the end of list 2. Repeat until list 1 is empty. It's linear-time (with a linked list), and there's no chance of duplicates.
But this isn't the scenario presented in the article - It's an algorithm for a very specialized version of a shuffle, where you need a random sample from an unbounded sequential (meaning, you don't know it's length ahead of time) list. The algorithm presented is for getting a good random sample from a dataset well beyond the size of memory, not for doing a perfect shuffle on a small list.
Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?
>>> random.sample(xrange(0, 1000000000), 5)
[5258132, 23096612, 43529214, 91062733, 4912658]
https://svn.python.org/projects/python/tags/r32/Lib/random.p...
>>> random.sample(xrange(0, 1000000000), 5) [5258132, 23096612, 43529214, 91062733, 4912658] This ran in a few milliseconds on my old macbook in python. It is an iterator over 1 billion element list. Looking at the source, they seem to track previous selections for large populations in a set, for which lookup of "x in y" is avg O(1). https://svn.python.org/projects/python/tags/r32/Lib/random.p...
for i = 1 to k
pickedCardIndex = randomInt(n - i)
hand[i - 1] = deck[pickedCardIndex]
swap(deck[pickedCardIndex], deck[n - i])
Considering there are somewhere over 1 trillion tweets (over 200 billion/year), this is a very easy problem, you do not even have to check for duplicates because the chance of getting a duplicate is so small it would be statistically unlikely to ever happen.
> generate a list of random tweets, without duplication. Considering there are somewhere over 1 trillion tweets (over 200 billion/year), this is a very easy problem, you do not even have to check for duplicates because the chance of getting a duplicate is so small it would be statistically unlikely to ever happen.