Algorithm No One Knows About (2016)
getkerf.wordpress.com
Algorithm No One Knows About (2016)
1–10 of 200 posts
Re: Algorithm No One Knows About (2016)
#2>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.
Re: Algorithm No One Knows About (2016)
#3>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. I…
> 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.
Re: Algorithm No One Knows About (2016)
#4>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. I…
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.
Re: Algorithm No One Knows About (2016)
#5Why is hashmap not good enough for unique ID generation?
const tweetIDs = {};
while(TWEET_COUNT){
const rnd = Math.random() * MAX_TWEET_ID;
if(!tweetIDs[rnd]){
tweetIDs[rnd] = true;
TWEET_COUNT--;
}
}Re: Algorithm No One Knows About (2016)
#6>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. I…
> 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 rejec…
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.
Re: Algorithm No One Knows About (2016)
#7Why is hashmap not good enough for unique ID generation? const tweetIDs = {}; while(TWEET_COUNT){ const rnd = Math.random() * MAX_TWEET_ID; if(!tweetIDs[rnd]){ tweetIDs[rnd] = true; TWEET_COUNT--; } }
That gets pretty slow and memory intensive once you sample a large amount of the total doesn’t it?
Re: Algorithm No One Knows About (2016)
#8Why is hashmap not good enough for unique ID generation? const tweetIDs = {}; while(TWEET_COUNT){ const rnd = Math.random() * MAX_TWEET_ID; if(!tweetIDs[rnd]){ tweetIDs[rnd] = true; TWEET_COUNT--; } }
That gets pretty slow and memory intensive once you sample a large amount of the total doesn’t it?
It was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
Re: Algorithm No One Knows About (2016)
#9Oh dear, I find those single-letter variable names are quite counter-productive in making the code easy for someone unfamiliar to the project to understand...
Re: Algorithm No One Knows About (2016)
#10Can't you use https://en.wikipedia.org/wiki/Lehmer_random_number_generator for this? I thought that was a common method of generating a random sequence without repetition. True, the result is not very random, but in most applications it doesn't make much of a difference.