Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Algorithm No One Knows About (2016)

getkerf.wordpress.com

Post reply on HN
Print view View original

181–190 of 200 posts

Re: Algorithm No One Knows About (2016)

#181

Post by tripzilch »

stillworks wrote: post #82
norswap wrote: post #81

Earlier quoted context omitted.

I'm feeling like I'm missing something, but why not? 2^64 is the number of cards in the deck, but that's not the number of cards we're picking . That might be just 10.

From the article: "Stated more formally: given non-negative integers k and n with k Focus on k Also, in the comments section in the article, the author counters a comment in favor of Python's random generator along the same lines.

He also just throws this out there: "visual inspection was enough to convince me that it [Python's sample function] was broken, without going further" -- with no explanation or in what way it is supposedly broken.

Re: Algorithm No One Knows About (2016)

#182

Post by tripzilch »

drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

Well the main point of the algorithm is that the output is going to be a sequential, increasing list of int64 "cards".

Which may be useful for tape drives, but I'm not sure what else.

The big point that the author is missing, is that if you drop that requirement, or rather if you require the output to be shuffled, like you'd expect from dealing cards, then there are super easy algorithms.

Just pick a random permutation function over the 64-bit integers, and start counting. It's literally like dealing cards.

People in this thread have suggested block encryption as permutation functions, which will work. But there are also good non-cryptographic (much faster) permutation functions out there.

If you got a permutation function you don't need memory to store the permutation, and poof the problem just goes away.

You need this algorithm only if you absolutely need the output to remain in order. But that's not really part of the problem he sketches, which is about "take X without replacement".

Re: Algorithm No One Knows About (2016)

#183

Post by tripzilch »

debatem1 wrote: post #152
drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

The original problem is to "generate a list of random tweets, without duplication". So lists are most assuredly allowed, and the implied constraints on the output size are in play. Using those to solve the problem under an assumption that the output size is much smaller than the input is therefore fair game.

The problem he states is really not for the algorithm he fails to actually explain. The algorithm only makes sense if you require the output to be in order (and you need a really large sample). The part where he suggests shuffling the output afterwards is absurd; if you wanted random order, there are much simpler algorithms.

Re: Algorithm No One Knows About (2016)

#184

Post by tripzilch »

drfuchs wrote: post #146
aidenn0 wrote: post #127

Earlier quoted context omitted.

If you can store 2^64 data points, why cant you store 2^63 indexes? That's a very small increase in memory requirements.

The issue isn't storage requirements; the issue is that, in the environments where this algorithm is useful, random access to the storage device is orders of magnitude slower than sequential access. Think magnetic tape in 1986, or today's spinning rust hard drives that take relatively forever to "seek", or even RAM being accessed sequentially, allowing the CPU to speculatively pre-fetch cache lines in burst-mode. Usi…

No if you generate them out of order, you can just use a permutation function and have zero memory requirements.

This algorithm is only fast given that sequential access is much faster than random access (and you don't need your output shuffled).

Re: Algorithm No One Knows About (2016)

#185

Post by tripzilch »

twic wrote: post #113
ghusbands wrote: post #61

The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.

The thing the Vitter algorithm does which this doesn't is that it produces the samples in order . This is why it's useful with tape drives, or sampling market data through the day: you can start at the beginning, and take the samples without ever having to seek backwards.

It is also the only reason to use this algorithm :) It's a pretty important requirement that I don't think the author emphasized enough.

If you want them shuffled (or don't care if they're shuffled), better use a permutation function.

BTW there are much faster permutation functions than cryptographic ones (you don't need the security aspect for this application). Look to modern PRNGs.

Re: Algorithm No One Knows About (2016)

#186

Post by tripzilch »

dahart wrote: post #173
ghusbands wrote: post #61

The last time I wanted an unpredictable, non-repeating sampling of 64-bit numbers, I used a symmetric cipher in CTR mode. Essentially, start with a random key and a random value, return the encrypted version of it, then the encrypted version of its increment, and so on. Returns every number in the range, with no predictability.

This is a good way to pick a few 64 bit numbers without duplicates, if 64 bit numbers is what you need. I didn't see any replies to you mention this part, but Vitter's algorithm works on an unknown number of samples. You can pick a 64-bit number uniformly when you know in advance you have exactly 2^64 choices. But how would you pick samples from a stream with equal probability, without knowing how many items are in t…

Incorrect, you do know this number beforehand. The parameter `N` in the code is the upper bound on the number of values, and the parameter `n` is the number of samples.

Re: Algorithm No One Knows About (2016)

#187

Post by tripzilch »

altmind wrote: post #151
vardump wrote: post #13

While reading, I was thinking about LFSR [0] with suitable properties and period. Not strictly random, although LFSRs are commonly used for generating "random" numbers. [0]: https://en.wikipedia.org/wiki/Linear-feedback_shift_register

Exactly my thoughts - its wolfenstein fizzlefade or LSFR that you learn in crypto 101 that can pick all the numbers in the range randomly. "Algorithm No One Knows About" is such a condescending title...

Especially if you don't actually explain the algorithm and seemingly fail to understand its single most important requirement is that the output is in order. Not something to shuffle later, because the only advantage of this algorithm is that the output remains in order.

Otherwise you use a permutation function, such as an LSFR or preferably a family of functions.

Re: Algorithm No One Knows About (2016)

#188

Post by tripzilch »

coleifer wrote: post #22
tiborsaas wrote: post #5

Why 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--; } }

The algorithm described in the article has other desirable properties: * IDs are returned in sorted order * IDs are generated one after another, ie could be implemented as a generator or coroutine * No additional space required during the computation Resulting in a single pass.

> * IDs are returned in sorted order

This is key. The author does not explain this well, or at all. If you require the IDs in sorted order, you need this algorithm.

If you don't mind or want them shuffled, use a permutation function.

(the idea of shuffling afterwards is nonsense, if you could do that, you can also check for duplicates when drawing)

Re: Algorithm No One Knows About (2016)

#189

Post by tripzilch »

Someone wrote: post #126

”Here’s a program roughly 0% of programmers know how to write: generate a list of random tweets, without duplication. […] Stated more formally: given non-negative integers k and n with k , generate a list of k distinct random numbers, each less than n .“ I think that knowing k beforehand makes it a different, easier problem. I don’t see how, if you don’t know k beforehand, you can do without enough memory to store a…

The author fails to emphasize this, but the key property here is that the output must be returned in order.

Re: Algorithm No One Knows About (2016)

#190

Post by svat »

tripzilch wrote: post #182
drfuchs wrote: post #47

A bunch of comments here are missing the main point: Unless you have an Exabyte of memory, you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them. The goal here is an algorithm that generates the selected cards, one by one, in order, as if from a coroutine that only uses a tiny, constant amount of memory. So, no arrays, lists, sets, hash tables, bitmaps, etc., even i…

Well the main point of the algorithm is that the output is going to be a sequential, increasing list of int64 "cards". Which may be useful for tape drives, but I'm not sure what else. The big point that the author is missing, is that if you drop that requirement, or rather if you require the output to be shuffled, like you'd expect from dealing cards, then there are super easy algorithms. Just pick a random permutati…

How do you pick a random permutation function over 64-bit integers? On a set of N=2^64 integers, there are N! permutations, so you need lg(N!) ≈ NlgN random bits to generate a uniformly random permutation, and thus at least that much time. This is too much: we want a solution in O(K) time and O(1) additional space (in addition to the space for K integers) — something that's Ω(NlgN) is out of the question. Things like block encryption do not generate a uniform distribution over all possible N! permutations of N=2^64 integers (at typical parameter sizes); obviously they can generate only as many possible outputs as 2^(the number of random bits used).
Post reply on HN