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

71–80 of 200 posts

Re: Algorithm No One Knows About (2016)

#71

Post by LolWolf »

OscarCunningham wrote: post #60
LolWolf wrote: post #57

Earlier quoted context omitted.

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 :)

No structure can check membership in O(1) time if n is big enough.

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.

Re: Algorithm No One Knows About (2016)

#72

Post by yorwba »

klingonopera wrote: post #67
yorwba wrote: post #49

Earlier quoted context omitted.

You can shuffle k items in O(k) time using an algorithm that swaps items in place. You can't use a similar algorithm to pick k out of n because that'd require you to materialize all n items in memory simultaneously, which exceeds the space constraints.

I thought of swapping too, but there's something about it I can't quite fathom, that tells me, it will not be "truly" randomized as with the method I described above... ...and a way to offset that, if you insist on the method of swapping, would be to remember what you've swapped and cross-checking that, but then you end up with the same problem as when you pick random items...

OscarCunningham's implementation https://news.ycombinator.com/item?id=20961548 remembers what has already been swapped using the counter i.

Re: Algorithm No One Knows About (2016)

#73

Post by klingonopera »

OscarCunningham wrote: post #46
klingonopera wrote: post #39

Earlier quoted context omitted.

...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...

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.

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.

Re: Algorithm No One Knows About (2016)

#74

Post by IIAOPSW »

yorwba wrote: post #65
IIAOPSW wrote: post #56

Ok I'll take a shot at it. Pick a number between 0 and N. Let's call it p for pivot. Each draw after this initial draw is either less than p with probability p/(N-1) or greater than p with probability 1-p/(N-1). You need to make k-1 additional draws. The probability of m of those draws being less than p is given by the binomial distribution. Choose m from the binomial distribution. Then run the algorithm recursively…

What's the time complexity of sampling from the binomial distribution?

well...shit.

Re: Algorithm No One Knows About (2016)

#75

Post by kadoban »

yorwba wrote: post #59
kadoban wrote: post #4

Earlier quoted context omitted.

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 ca…

The algorithm in the paper does have a threshold of n/13, beyond which it switches to "Method A".

Ah, thank you, I did not see that part.

Re: Algorithm No One Knows About (2016)

#76

Post by LolWolf »

garganzol wrote: post #70
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 approach. Thanks to bijective mapping between original and encrypted spaces the result is guaranteed to be unique. And since the mapping function is a secure encryption algorithm, the output has uniform distribution. Well done.

Indeed, but this assumes that modern crypto is secure! :)

Re: Algorithm No One Knows About (2016)

#77

Post by LolWolf »

yorwba wrote: post #68
LolWolf wrote: post #31

Earlier quoted context omitted.

NOTE: This comment I wrote is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 Yeah, but the k ~ n/2 case (in which inverse selection and normal selection have the same runtime) is still Ω(n log n) (equiv Ω(k log k)), which is still "slower" than the presented algorithm.

Actually, this comment is correct despite making a similar argument to your incorrect one elsewhere. Using a set to accumulate intermediate results requires k inserts at O(log k) each.

I'm still not sure about this—the amortized time of insertion should be O(1) on any one of the usual hash table-type-structures. We're not inserting a single item to an already-built hash-table, but rather k of them into an empty hash-table, with elements being uniformly drawn and bucketed using a good hash function. All of this should give O(1) average time for insertions.

Re: Algorithm No One Knows About (2016)

#78

Post by convivialdingo »

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.

I know this, as I work in crypto.

But I’d have never considered using it for this - it doesn’t register in the brain as anything other then crypto.

Awesome solution, thanks for hacking my brain.

Re: Algorithm No One Knows About (2016)

#79

Post by web007 »

OscarCunningham wrote: post #58
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…

Is there an easy way to adapt the algorithm to get the cards drawn in a random order? The article says "it’s easy to randomize the order after the fact" but if we can't store them in memory then that's a no-go.

You select N from M, in order, where M is "too big" and N fits in memory / swap / disk. You then shuffle your N selections to get random ordering.

Re: Algorithm No One Knows About (2016)

#80

Post by [deleted] »

OscarCunningham wrote: post #58
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…

Is there an easy way to adapt the algorithm to get the cards drawn in a random order? The article says "it’s easy to randomize the order after the fact" but if we can't store them in memory then that's a no-go.

[deleted]
Post reply on HN