12 ms·
Algorithm No One Knows About (2016)
- OscarCunningham 7y ago>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 agoIf 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 agoThat 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 agoThe "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 agoI think the article discusses the fact that shuffling the entire initial set takes up way too much memory.
- andreareina 7y agoBirthday 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 agoAh, right. I wasn't thinking properly. Thanks for the explanation.
- petters 7y agoYou're right, but it's not 2^8. It is √2^64 = 2^32.
- andreareina 7y agoYes, thanks. Took the root of the wrong number.
- IIAOPSW 7y agoBut 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 agoYeah, 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.
- klingonopera 7y agoA use case may be shuffling the entire list, if I'm not mistaken?
- OscarCunningham 7y agoThey 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 agoAn 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 agoWouldn'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 agoThe problem the author tries to avoid here is in this way the memory requirement is proportional to 2^63.
- LolWolf 7y agoEDIT: 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 agoI 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 agoSee 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 agoNo structure can check membership in O(1) time if n is big enough.
- LolWolf 7y agoIn 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 agoThis solution requires storing the 2^63 cards you have picked. That's impossible to do today.
- vardump 7y agoIt 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.
- tiborsaas 7y agoWhy 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--; } }
- empath75 7y agoThat gets pretty slow and memory intensive once you sample a large amount of the total doesn’t it?
- tiborsaas 7y agoIt was not a requirement :) However it won't get slow, it's O(1) to lookup if a key exists.
- kadoban 7y agoIt will get slow towards the end once each loop iteration has a very low chance of being productive (only happens when you're choosing all or almost all elements). You can fix that, though there's potential tradeoffs.
- andreareina 7y ago> (Stated more formally: given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.) As k approaches n the expected number of draws needed to get k unique values increases faster than O(k).
- deleted 7y ago[deleted]
- ozgung 7y ago>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). This will take longer time at each iteration and when both MAX_TWEET_ID and and TWEET_COUNT is large and close to (or equal to) each other it may take very long to complete.
- klingonopera 7y agoOh 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...
- airstrike 7y agoYeah, I'm way out of my comfort zone here but I found the choice of n and N pretty off-putting
- klingonopera 7y agoA typo is only a (sticky) shift away, and not even obvious! EDIT: ...and compiles, too!
- Gene_Parmesan 7y agoThey are like that because they essentially transliterated the original Pascal code from the paper. Leaving the variable names as they were in the paper allows for the paper to act as documentation for the code, so to speak.
- js8 7y agoCan't you use https://en.wikipedia.org/wiki/Lehmer_random_number_generator 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.
- deleted 7y ago[deleted]
- mankyd 7y agoNot if you want it to be actually random. But you might be correct if you simply want the appearance of randomness.
- mehrdadn 7y agoI haven't read the algorithm code, but I think you can do the following? For n items, pick a random k <= log(n!), then enumerate the k'th permutation of n items. It's not trivial, but there are already algorithms for it, e.g.: https://code.activestate.com/recipes/126037-getting-nth-permutation-of-a-sequence/ https://code.activestate.com/recipes/126037-getting-nth-perm...
- LolWolf 7y agoOoh, this feels like it gets close to the solution! It's not quite there as stated, though, since this algorithm requires O(k^2) time (where k is the number of elements to be randomly drawn) as you have to insert items into specific indices in the array.
- mehrdadn 7y agoYeah, but I think you can be more clever than just doing naive array insertions, by trying to batch them up. At least, we know decreasing sequences of indices can be done in one pass with no changes, and increasing sequences can be done in one pass by accumulating shifts. That leaves alternations to worry about. Now I haven't fully thought this through, but I think something along these lines might work (there may be errors in some of the details here): treat the list of indices you're inserting into as the leaves of a binary tree, and create the intermediate nodes of that tree, initializing them to zero. The intermediate nodes represent offsets (initialized to 0) that will be logically added to all earlier nodes. Then sort the nodes, breaking ties so that the later ones are first. Now perform every insertion at {the given index plus its ancestors}, and then increment the counters for all ancestors of that index so that you account for shifts of later elements. This should get you to O(k log k) or so. In fact, this makes me wonder why there isn't a multi-insert function in every language's vector implementation...
- vardump 7y agoWhile 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 https://en.wikipedia.org/wiki/Linear-feedback_shift_register
- panic 7y agoWolfenstein 3D's FizzleFade uses an LFSR to visit each screen pixel exactly once in a pseudorandom order: http://fabiensanglard.net/fizzlefade/index.php http://fabiensanglard.net/fizzlefade/index.php There's an alternative FizzleFade implementation using Feistel networks: http://antirez.com/news/113 http://antirez.com/news/113 -- I think the same technique could be used here to randomly permute the index space.
- theandrewbailey 7y agoI was thinking the same. Depends on what "random" actually means. If you want to "pick one of these that you haven't already", a LFSR is great. Less so if you want truly random, or if anyone will start looking closely.
- altmind 7y agoExactly 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...
- tripzilch 7y agoEspecially 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.
- fergie 7y ago"(Stated more formally: given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.)" "...it’s also possible to use the language of cards: deal k cards from a deck of size n, without replacement. So a poker hand like A2345 of clubs is valid for k=5 and n=52, but a hand containing AAAAA of clubs is not." These seem to be fairly straight forward problems to solve- can anybody ELI5 why the Vitter algorithm is necessary?
- rini17 7y agoTrivial algorithms (like one implemented in Python) slow down when k is close to n. Or when n is large, then it is not possible to use bitmap to mark dealt cards.
- avip 7y agoThe python algo does not get slow when n is large. The k~n case obviously calls for inverse selection. https://github.com/python/cpython/blob/master/Lib/random.py#L386 https://github.com/python/cpython/blob/master/Lib/random.py#...
- LolWolf 7y agoNOTE: This comment I wrote is totally wrong. I haven't had my morning coffee yet. H_n - H_(cn) ≈ constant, not diverging (for 0 < c ≤ 1). :) 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.
- yorwba 7y agoActually, 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.
- floor_ 7y agoI may be misinterpreting the question here but can't the author just use a large prime to to pull from the array like you would when hashing? Its how you would in place shuffle a music playlist.
- epeus 7y agoGetting this wrong can tank your product - see what happened to Draw Something http://epeus.blogspot.com/2012/04/draw-something-ceo-grace-and-high.html http://epeus.blogspot.com/2012/04/draw-something-ceo-grace-a...
- lucb1e 7y agoSummary without the drama: by not using a "discard pile" but picking randomly from the same set of words every time, you get repeat words paradoxically often (birthday paradox), which is what pictionary did and people complained about.
- Dylan16807 7y agoOkay, so this is a way to generate a sampling in order, so you don't have to keep a sorted list and your run time can be k instead of klogk. Mostly. The body of the post, with its talk of strict timing and sample bias, had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n. If this algorithm hits certain rare values it will re-sample the RNG.
- caf 7y agoThis appears to be the state of the art in minimising the resampling cost: https://arxiv.org/pdf/1805.10941.pdf https://arxiv.org/pdf/1805.10941.pdf
- ChrisLomont 7y ago>had me thinking it had some clever way to pick a random number from 1 to n in finite time. But that's not actually possible to do with a random bit source and a non-power-of-two n I can sample 1-6 in finite time by rolling a die. I suppose you mean given a RNG in range 1-2^n, you cannot get a sample range non-power-of-two in fixed time. However, you can sample in finite time with probability as high as you like, since the likelihood of another roll falls off exponentially. So if the odds of your machine quantum tunneling into a star is p, then you can make an algorithm that does your sampling with fixed time T with probability more than 1-p, making it perfectly usable. in practice, resampling rand takes very, very little time. I use it all the time for uniform [0,n) queries. The avg number of rolls is for the most part like 1.1 or less. For example, to sample 0-9 given a 32 bit full period generator, since 2^32 mod 10 is 6, only in 6 cases out of 2^32 cases do you need a second roll. This is common.
- GistNoesis 7y agoHere is how I would do it. Pick a prime p bigger than N. Pick a random permutation of Z/pZ. Pick an initial state. Advance to the next state, to cycle through all the values exactly once. You use rejection sampling if the state is greater than N, so as long as you pick p close to N this should happen very rarely and be amortized O(1). If N is big this advance to the next state can be encoded easily as a multiplication by an element of Z/pZ (multiplication followed by modulo p), and you will cycle through all the values because Maths. If N is not so big you pick a few (m) elements of Z/pZ to represent your permutation, and you use the first number as a multiplier mod p the first time, then the second number as a multiplier mod p the second time, and so on..., and you will also cycle through all the value, because Maths as long as you don't get a 1 while multiplying sequentially your m elements. Don't forget to stamp it good enough(TM), if not use Dual-ECC.
- ikeboy 7y agoTldr of the algorithm from the paper: Instead of choosing random numbers to include in the list, they're choosing the gap between numbers. They derive the distribution of this gap then approximate it so it can be calculated quickly.
- eyegor 7y agoDoes anyone have a mirror for this? No matter what I do, all I'm getting is an empty page with a sidebar.
- nomadictype 7y agoIn Firefox: View -> Page Style -> No Style (For whatever reason the page has a CSS rule #content { display: none; }, which presumably gets removed via JS.)
- jbotz 7y agoIf this really was such an obscure but useful algorithm, someone should change the title of this post to help people find it in the future so it doesn't remain obscure (add "card drawing"?)
- LolWolf 7y agoIt's... not that useful, as far as I can tell (unless I'm still under-caffeinated!) @avip mentions the following comment https://news.ycombinator.com/item?id=20961320 https://news.ycombinator.com/item?id=20961320 , which means that we only have to consider k ~ cn for 0 ≤ c ≤ 1/2. Drawing in this fashion, we have an expected runtime of k * (H_n - H_{(1-c)n}) ≤ k * (H_n - H_{n/2}) ~ O(k).[1] The latter is true since H_n ~ log n + C + O(1/n) for some[2] constant C. Of course, depending on what the author's constraints are, there would be an additional O(k) space requirement for keeping track of indices that have already been picked. Vitter's algorithm is particularly nice, since it can report the items without this additional space requirement. --- [1] https://en.wikipedia.org/wiki/Coupon_collector's_problem https://en.wikipedia.org/wiki/Coupon_collector's_problem [2] https://en.wikipedia.org/wiki/Euler–Mascheroni_constant https://en.wikipedia.org/wiki/Euler–Mascheroni_constant
- drfuchs 7y agoA 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 if they're hidden in some cute construct built into your favorite language.
- OscarCunningham 7y agoIs 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.
- web007 7y agoYou 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.
- supergarfield 7y agoI understand "you can't use any kind of data structure to remember which cards you've already picked among 2^64 of them" as "N cards don't fit in memory". Or is the relevant distinction memory vs disk, as it's feasible to randomize on-disk data?
- svat 7y agoThe problem asks to find k cards (integers) out of n, in time O(k) and O(1) additional space — this means additional to the k required to store the output. So while holding n items wouldn't fit in memory, it is implicit that k would. But we still want to avoid Ω(k log k) time, or more than a constant amount of additional space.
- aasasd 7y ago
- IIAOPSW 7y agoOk 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 on the space 0 to p-1 and p+1 to N. Some pseudo-code. def deckpicker(N,k,offset=0): if k == 0: return p = uniform_dist(0,N) m = binomial_dist(k-1, p/(N-1)) deckpicker(p-1,m,offset) print(p+offset) deckpicker(N-(p+1),(k-1)-m,offset+p+1)
- ghusbands 7y agoThe 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.
- garganzol 7y agoThis 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.
- convivialdingo 7y agoI 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.
- twic 7y agoThe 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.
- 7y ago
- jchook 7y ago> given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. > We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.) Sounds like the Knuth multiplicative hash. The Art of Computer Programming vol. 3, section 6.4, page 516.
- amcsi 7y agoSo let me get this straight... This algorithm creates an initially empty array of size K with the DB internal ids of what would randomly be selected. Then it goes in order from 0 to the number of rows - 1, and for each one it goes e.g. "What are the chances that number 0 would get randomly picked out of N items if K items need to be picked?" Then, if the #0 passes the "random check", it gets added. Then it would go to 1 and go "What are the chances #1 would be picked out of N-1 items if K-1 items need to be picked?" ...and repeated so on until all K random items have been picked?
- eapriv 7y agoNo, what you described is O(n).
- natch 7y agoSome of the variable names used: i, j, t, qu1, S, n, N, U, X, y1, y2, V I know others have already commented on this but I think it's worth laying out all of the cryptic variables and asking: are some of these shorthand for well known math concepts that make it unnecessary to have a more descriptive name? I understand the use of temporary value holders like `i`, but have no clue what some of the others might be used for or what the single letter names indicate. Another way to ask the question: if the author had just used instead a, b, c, d, e, f, g, h, etc. what information would be lost, that is gained by the particular letter choices that were used? This isn't rhetorical, although there is a point to be made for sure about clarity in naming... I'm really wondering if anyone can explain what these letters might mean if you are more versed in the math than I am. BTW here's another Vitter paper I found in case anyone's interested: https://www.cs.umd.edu/~samir/498/vitter.pdf https://www.cs.umd.edu/~samir/498/vitter.pdf
- SilasX 7y agoI don't have an answer, but I remember Go programmers on Quora swearing up and down that (the Go convention of) using single-letter variables is ingenius and leads to great code ... although none of them could give a single example.
- jasonshaev 7y agoThis is a bad take and odd place to criticize Go programmers. Go convention is often short variable names, but the only place I know where single-letter variable names is encourage is for receiver methods. https://golang.org/doc/effective_go.html#methods https://golang.org/doc/effective_go.html#methods In that case the definition of the single-letter variable is literally a line or two of code away.
- SilasX 7y agoSo is HN a good place to ask, and if so, are you able to find a perspicuous example highlighting the superior code quality?
- TheMerovingian 7y agohttps://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
- Bossle 7y agoExactly, just truncate the iteration to the first k elements. Need a hash table to get the modified values, so it breaks the "O(1) extra space" condition, but that condition is bullshit anyway, you're already using O(k) space to store the numbers you find, an extra hash table is also O(k) space. http://ideone.com/5uwqNO http://ideone.com/5uwqNO
- dahart 7y agoIt’s related to Fisher-Yates shuffle, https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to_Fisher-Yates_shuffle https://en.wikipedia.org/wiki/Reservoir_sampling#Relation_to... But it’s not the same thing. The difference is whether you can keep all samples in memory at the same time. With Vitter / reservoir sampling, you only need to have your reservoir in memory plus enough space for 1 new sample at a time, so you can stream through a large number of samples with a tiny amount of memory.
- agumonkey 7y agoI remember an article about the space complexity of drawing all colors randomly.. this seems related, isn't it ?
- Someone 7y ago”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 <= n, 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 number of magnitude n!, and even that would be extremely slow, the more items you have to produce (uniformly pick a permutation of n items, and produce as many of them as requested)
- saagarjha 7y agoI don't see why you'd need to generate a permutation?
- Someone 7y agoIf you don’t know k beforehand, you have to (eventually) handle the case where k is large, possibly even equal to n. If it turns out to be equal to n, you have to generate a permutation. If it isn’t, you don’t need to, but you need to keep enough information around, in case it turns out that you need. For example, by the time you’ve generated 2⁶³ integers in the range 1…2⁶⁴, you need to know which 2⁶³ integers still are ‘available’. I think you can’t do that more compactly than by just picking the permutation to generate at start (whether you can efficiently determine the k-th number in that permutation is a separate problem)
- tripzilch 7y agoThe author fails to emphasize this, but the key property here is that the output must be returned in order.
- jonplackett 7y agoAnyone feel like doing a human readable breakdown of what the algorithm is going? That would make me happy
- qws 7y agoYeah, really. A lot of filler paragraphs building up to unreadable code. Bad article.
- pmiller2 7y agoAnd I still don’t know about it, because the article just has a code dump and some vaguely relevant historical commentary. Posting the actual paper would have been better.
- deleted 7y ago[deleted]
- dahart 7y agoIt’s called Reservoir Sampling https://en.wikipedia.org/wiki/Reservoir_sampling https://en.wikipedia.org/wiki/Reservoir_sampling I was just re-reading this yesterday! I think a lot of the Monte Carlo rendering people know about this family of algorithms, and the idea is pretty simple. I’m not sure why it’s described from the start as picking k samples though, I find it a lot easier to understand and see how it works when you start with k=1. Btw, it’s fun to work out the probabilities of picking a sample to prove how this algorithm works, and that it’s uniform. Big piles of factorials that all cancel out. Pps the other super rad algorithms that aren’t well knows are the alias method for simulating a discrete distribution https://en.wikipedia.org/wiki/Alias_method https://en.wikipedia.org/wiki/Alias_method ...and the suffix array, which is crazy surprisingly useful https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array
- yati 7y agoReservoir sampling requires you to maintain a reservoir of n items that will be your sample. This can be prohibitive if the sample size itself is huge. The algorithm described here decides (commits) whether an item is to be sampled as it sees it (i.e., online), while consuming a constant amount of memory. It differs from the usual reservoir sampling approach in that it cannot go back and "unsample" an item it already selected (whereas the crux of a reservoir sampling approach is evicting current candidate items and replacing them with new items).
- tripzilch 7y ago> When I came across a need for the algorithm in my work, it took a lot of detective work to even find it. There was no source code online. The algorithm is not referenced often, and when it is, it is in a highly obscure fashion. Well, the author certainly isn't helping that problem with a clickbait title like that, and being all mysterious for the first few paragraphs, teasing "you almost certainly don't know this". "Dealing cards from an extremely large deck: Vitter's Algorithm" Except he doesn't even explain the algorithm, just some source code (which is super unclear, no comments, short variables). And the unhelpful comment that it was hard to figure out from the paper. All the reason to put a more descriptive title. How does he expect to help people find this, figure this out, or was this entire post just to brag that "his" solution is better than anyone else's because he found the right algorithm almost nobody else knows about?