5 ms·

>The misleading part in using the language of cards is that you don’t often consider a deck of size 2^64. What’s nice about the card formulation though is that

>The misleading part in using the language of cards is that you don’t often consider a deck of size 2^64. What’s nice about the card formulation though is that it conveys how simple the problem statement really is. This is a fundamental problem that was open for a long time. Nobody knew how to deal cards. >The first obstacle that makes the “dealing” (without replacement) hard is that the “draw” method doesn’t work. If you draw (with replacement) over and over again, ignoring cards you’ve already picked, you can simulate a deal, but you run into problems. The main one is that eventually you’re ignoring too many cards and the algorithm doesn’t finish on time (this is the coupon collector’s problem). How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 cards you're going to be rejecting only half of your draws, so the average slowdown is just a factor of 2. If you really want to draw more than half the deck then just randomly pick the cards that you don't want.

AllegedAlec 7y ago
> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.
- kadoban 7y ago
  If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
  - mihaifm 7y ago
    That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
    - kadoban 7y ago
      The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k. If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties) This also wouldn't use much extra space, and doesn't require special handling for small or large k. Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.
      - SamBam 7y ago
        I think the article discusses the fact that shuffling the entire initial set takes up way too much memory.
- andreareina 7y ago
  Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.
  - AllegedAlec 7y ago
    Ah, right. I wasn't thinking properly. Thanks for the explanation.
  - petters 7y ago
    You're right, but it's not 2^8. It is √2^64 = 2^32.
    - andreareina 7y ago
      Yes, thanks. Took the root of the wrong number.
- IIAOPSW 7y ago
  But on each draw you need to check if its a card you've already drawn. You can hold your cards in a set data structure but then you pick up the complexity of the insertion operation into sets. IIRC sets are basically hash tables that map keys to themselves. Insertion is O(1)...until you need to resize your table due to hash collision.
kadoban 7y ago
Yeah, the motivating text from the article isn't very convincing. Seemed really odd that they didn't even describe the algorithm either. Sure, there's code and a link to the paper, but you spent so much time in prose trying to talk it up, needs to have the full story in prose too if you're going to do that. At least give the main idea. I skimmed the paper, and the sort of algorithm used does have some advantages I can see. Mostly, you can start giving output right away and don't need extra storage, and you don't have to be careful that n << N or have separate algorithms with a threshold or anything.
- yorwba 7y ago
  The algorithm in the paper does have a threshold of n/13, beyond which it switches to "Method A".
  - kadoban 7y ago
    Ah, thank you, I did not see that part.
klingonopera 7y ago
A use case may be shuffling the entire list, if I'm not mistaken?
- OscarCunningham 7y ago
  They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn. > The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.
  - klingonopera 7y ago
    ...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail? You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...
    - OscarCunningham 7y ago
      An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.
      - klingonopera 7y ago
        Wouldn't this have a bias to how the initial input sequence is? EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.
afiori 7y ago
The problem the author tries to avoid here is in this way the memory requirement is proportional to 2^63.
LolWolf 7y ago
EDIT: This is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 < c ≤ 1). :) The problem is that all of these little errors add up to give you a logarithmic slowdown. In particular, the solution proposed in this comment is still Ω(k log k) (where k is the number of elements drawn), which is slower than the algorithm's proposed solution of O(k).
- OscarCunningham 7y ago
  I see. In particular the log(k) doesn't come from repeat attempts, it comes from the time needed to search through your list of drawn elements to see if you've seen the chosen element before.
  - LolWolf 7y ago
    See my edit! Oops. Anyways, if you were to keep it in some hash-based structure, you could check membership! (But I'm sure you already knew that :)
    - OscarCunningham 7y ago
      No structure can check membership in O(1) time if n is big enough.
      - LolWolf 7y ago
        In general, assuming that we have constant-time operations on arbitrarily large numbers (which we almost universally assume when doing these analyses, except in very specific fields), then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Additionally, the only problem with this approach is the extra O(k) space taken up by the structure, which doesn't meet the condition if the result is to be reported in a streaming fashion (but this is not the case in most practical applications)! For comparison, Vitter's is able to do this streaming output in O(1) space.
dahfizz 7y ago
This solution requires storing the 2^63 cards you have picked. That's impossible to do today.
- vardump 7y ago
  It would take a lot of storage, but it's not impossible. 2^64 bits equals 2097152 terabytes. A lot, but doable with modern technology. I guess for $100-200M.

AllegedAlec 7y ago

> How is this true? If you're drawing from a deck of 2^64 cards then unless you're drawing almost all of them there's not going to be any problem with rejection. Even if you're drawing 2^63 card you're going to be rejecting only half of your draws, so the average slowdown is going a factor of 2. It it though? I'm a but shoddy on my mathematics, but I'd wager from the birthday problem that you'd probably have to reject much more than half of the 'cards', and as you get to the end, you'd have to redraw several times for each card.

kadoban 7y ago
If you think about it one draw at a time it's pretty clear and there's no room to be missing anything really. 2^63 is half of 2^64. For the last draw, each time you try to pick an unused, what's the odds it was taken already? (approx 1/2) You won't have to try too many times. The draws before the last are strictly better, so overall you should be fine.
- mihaifm 7y ago
  That seems correct. On top of that, if you ever need to choose more than half, you choose n-k first then reverse the set. Could it be that the distribution condition is not satisfied? Although I don’t see how. The article could’ve explained the problem better (I mean it keeps reffering to “draw without replacement” - what does that even mean).
  - kadoban 7y ago
    The "choose n-k" trick is quite nice. It has one big downside though, which is that you can't start reporting any results until you're totally done. One algorithm that I haven't yet seen mentioned in this discussion is: shuffle the array of choices, pick the first k. If you're clever about it, this has some nice properties: you can stop shuffling after the first k, and if you want you can start reporting results immediately. (You'd want to use something like Fisher-Yates to shuffle for these properties) This also wouldn't use much extra space, and doesn't require special handling for small or large k. Biggest downside is it will change the order of the original set. And it's only worth doing if you already have an array full of the items to choose, most likely.
    - SamBam 7y ago
      I think the article discusses the fact that shuffling the entire initial set takes up way too much memory.
andreareina 7y ago
Birthday problem says that once you've gone through ~2^8 cards you've got a ~50% of having had to reject at least once. It takes 2^63 until you have a 50% chance of rejecting on each draw.
- AllegedAlec 7y ago
  Ah, right. I wasn't thinking properly. Thanks for the explanation.
- petters 7y ago
  You're right, but it's not 2^8. It is √2^64 = 2^32.
  - andreareina 7y ago
    Yes, thanks. Took the root of the wrong number.
IIAOPSW 7y ago
But on each draw you need to check if its a card you've already drawn. You can hold your cards in a set data structure but then you pick up the complexity of the insertion operation into sets. IIRC sets are basically hash tables that map keys to themselves. Insertion is O(1)...until you need to resize your table due to hash collision.

kadoban 7y ago

Yeah, the motivating text from the article isn't very convincing. Seemed really odd that they didn't even describe the algorithm either. Sure, there's code and a link to the paper, but you spent so much time in prose trying to talk it up, needs to have the full story in prose too if you're going to do that. At least give the main idea. I skimmed the paper, and the sort of algorithm used does have some advantages I can see. Mostly, you can start giving output right away and don't need extra storage, and you don't have to be careful that n << N or have separate algorithms with a threshold or anything.

yorwba 7y ago
The algorithm in the paper does have a threshold of n/13, beyond which it switches to "Method A".
- kadoban 7y ago
  Ah, thank you, I did not see that part.

klingonopera 7y ago

A use case may be shuffling the entire list, if I'm not mistaken?

OscarCunningham 7y ago
They specifically say that a nice thing about Vitter's algorithm is that it produces its results in sorted order, and that it's easy to shuffle them after they've been drawn. > The reason it’s nice for an algorithm to produce results in sorted order is because it’s easy to randomize the order after the fact.
- klingonopera 7y ago
  ...but is it actually so? The more I think about it, the entire topic seems to be, how do you say, a dog biting its own tail? You have a sorted list. Now randomize it. Either you pick random from source, or you place randomly into destination. And then, as k approaches n...
  - OscarCunningham 7y ago
    An easy way to randomise a list is the following: import random list = [0,1,2,3,4,5,6,7,8,9] length = len(list) for i in range(1,length): j = length - i k = random.randrange(j+1) list[j], list[k] = list[k], list[j] print(list) [3, 9, 6, 4, 7, 8, 5, 1, 0, 2] The randrange(j) can be done quickly by finding the smallest power of 2 above j and then picking randomly below it until you get an answer less than j.
    - klingonopera 7y ago
      Wouldn't this have a bias to how the initial input sequence is? EDIT: On the other hand, due to randomness, it could cancel itself out, I don't know, beats me. My brain hurts, at this point, I'd try to figure it out statistically first, to see if it's even a valid assumption before continuing the theoretical thought, but I'm presently too lazy to code that out... it's Friday, cheers.

afiori 7y ago

The problem the author tries to avoid here is in this way the memory requirement is proportional to 2^63.

LolWolf 7y ago

EDIT: This is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 < c ≤ 1). :) The problem is that all of these little errors add up to give you a logarithmic slowdown. In particular, the solution proposed in this comment is still Ω(k log k) (where k is the number of elements drawn), which is slower than the algorithm's proposed solution of O(k).

OscarCunningham 7y ago
I see. In particular the log(k) doesn't come from repeat attempts, it comes from the time needed to search through your list of drawn elements to see if you've seen the chosen element before.
- LolWolf 7y ago
  See my edit! Oops. Anyways, if you were to keep it in some hash-based structure, you could check membership! (But I'm sure you already knew that :)
  - OscarCunningham 7y ago
    No structure can check membership in O(1) time if n is big enough.
    - LolWolf 7y ago
      In general, assuming that we have constant-time operations on arbitrarily large numbers (which we almost universally assume when doing these analyses, except in very specific fields), then hash structures do check membership and add items in O(1) time (since the time spent increasing the structure size is amortized fairly quickly). Additionally, the only problem with this approach is the extra O(k) space taken up by the structure, which doesn't meet the condition if the result is to be reported in a streaming fashion (but this is not the case in most practical applications)! For comparison, Vitter's is able to do this streaming output in O(1) space.

dahfizz 7y ago

This solution requires storing the 2^63 cards you have picked. That's impossible to do today.

vardump 7y ago
It would take a lot of storage, but it's not impossible. 2^64 bits equals 2097152 terabytes. A lot, but doable with modern technology. I guess for $100-200M.