4 ms·

Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?

dantiberian 11y ago
I had the same thought. However thinking about it more, the requirement is that this algorithm is O(k). As k gets closer and closer to the size of the list, you will spend more and more time looking for unique items. You also need to pay the costs of checking for uniqueness which also grows with k.
- franciscop 11y ago
  Well yeah, that is exactly why I said for the situation where the lenght of the list is much smaller than the total number of tweets. Which should cover most practical usages.
- keypusher 11y ago
  You store the selected items in a hashtable or similar data structure with O(1) behavior of "x in y".
gd1 11y ago
It's not O(k) then. As he mentioned, he's writing this as a language feature, so he can't make simplifying assumptions about k or n. It must handle large n, and can't assume k << n.
- franciscop 11y ago
  I see, as a language feature it makes sense to overoptimize for any situation.
GauntletWizard 11y ago
In certain circumstances, like when you're drawing from a limited pool, this becomes N^2 and unbounded - Imagine you're trying to shuffle a deck of cards. Select a card number, 1-52. The first draw, you're guaranteed to get a unique card, the second, you've got a 1/52 chance of having to generate a second number, all the way up to the final card you have a 1/52 chance of generating the final number you need, and you'll spin for quite a bit waiting for that to come up, with a possibility (if your RNG is bad) that you'll never get there. This gets amplified if you've got a larger set - If you draw from six decks, you'll go through an average of 156 'draws' before you get your final card... and the card before it almost as many! 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.
- ivanche 11y ago
  "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." I have to add my $0.02. This is correct, your algorithm will give correct result with no chance of duplicates. However in some context this absolutely must not be done - I've worked in a company which made online gambling games and the auditing requirement was 1-to-1 correspondence of number drawn from RNG and the card player sees. For example Ace of spades must always be 49, whether it was drawn as first or last card from the deck.
ktRolster 11y ago
You can, but that becomes inefficient for very large numbers
ridiculous_fish 11y ago
I think the other replies to you are mistaken. This algorithm meets the requirements of running in linear time, once you apply the inverting trick when the sample size exceeds half of the pool size. See my top-level comment.

dantiberian 11y ago

I had the same thought. However thinking about it more, the requirement is that this algorithm is O(k). As k gets closer and closer to the size of the list, you will spend more and more time looking for unique items. You also need to pay the costs of checking for uniqueness which also grows with k.

franciscop 11y ago
Well yeah, that is exactly why I said for the situation where the lenght of the list is much smaller than the total number of tweets. Which should cover most practical usages.
keypusher 11y ago
You store the selected items in a hashtable or similar data structure with O(1) behavior of "x in y".

gd1 11y ago

It's not O(k) then. As he mentioned, he's writing this as a language feature, so he can't make simplifying assumptions about k or n. It must handle large n, and can't assume k << n.

franciscop 11y ago
I see, as a language feature it makes sense to overoptimize for any situation.

GauntletWizard 11y ago

In certain circumstances, like when you're drawing from a limited pool, this becomes N^2 and unbounded - Imagine you're trying to shuffle a deck of cards. Select a card number, 1-52. The first draw, you're guaranteed to get a unique card, the second, you've got a 1/52 chance of having to generate a second number, all the way up to the final card you have a 1/52 chance of generating the final number you need, and you'll spin for quite a bit waiting for that to come up, with a possibility (if your RNG is bad) that you'll never get there. This gets amplified if you've got a larger set - If you draw from six decks, you'll go through an average of 156 'draws' before you get your final card... and the card before it almost as many! 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.

ivanche 11y ago
"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." I have to add my $0.02. This is correct, your algorithm will give correct result with no chance of duplicates. However in some context this absolutely must not be done - I've worked in a company which made online gambling games and the auditing requirement was 1-to-1 correspondence of number drawn from RNG and the card player sees. For example Ace of spades must always be 49, whether it was drawn as first or last card from the deck.

ktRolster 11y ago

You can, but that becomes inefficient for very large numbers

ridiculous_fish 11y ago

I think the other replies to you are mistaken. This algorithm meets the requirements of running in linear time, once you apply the inverting trick when the sample size exceeds half of the pool size. See my top-level comment.