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

Vitter's reservoir sampling algorithm D: randomly selecting unique items

getkerf.wordpress.com

Post reply on HN
Print view View original

51–60 of 83 posts

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#51

Post by dalke »

vrfcodf wrote: post #38
dalke wrote: post #35

Earlier quoted context omitted.

The generator is also highly predictable and suffers from defects that may affect the overall analysis.

This only matters in calculations where randomness is important, i.e. Monte Carlo method. Nevertheless, if you don't use the least significant bits, and if the constants are carefully chosen, MLCG passes most of the hardest statistical tests. For example it passes all DIEHARD tests, and most of TESTU01.

In addition, the described algorithm "is on-line - that is, it requires no preprocessing and can generate each element of the sample in constant expected time." (Quoting from the original paper.) It needs only an upper bound on the number items, while your suggestion requires knowing the number beforehand.

You also need an MLCG over the range 0..2^64-1 to match the given algorithm. I believe that requires some extra code to handle potential overflow in a MLCG, so adds a few more lines to your estimate.

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#53

Post by anonymoushn »

asldaslkksdj wrote: post #44
ridiculous_fish wrote: post #27

> 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). I don't think this…

This is not correct as written: "But we have k < N, so if we are O(N) we are also O(k) or better."

That's right. We can fix it up though. The E(t_i) we care about are bounded above by a constant (2), so the sum of k such expectations is linear in k.

For the cases where k > n/2, the "full table scan" portion is of course also linear in k.

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#54

Post by anonymoushn »

kutkloon7 wrote: post #50

Again, I am confused. Why doesn't this snippet solve the problem? void increasingRandomSequence(arrayptr, base, k, n) { if (k == 0) return; int i = randInt(n - k); *(arrayptr) = base + i; increasingRandomSequence(arrayptr + 1, base + i + 1, k - 1, n - (i + 1)); } increasingRandomSequence(hand, 0, k, n) fills the array hand with a sequence which is picked with uniform distribution over all increasing sequences of leng…

It looks like this dramatically undersamples the beginning. Like if I ask for 1000 numbers out of 10,000, the very first number you provide will be (on average) nearly halfway through the list.

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#56

Post by lsiebert »

yeukhon wrote: post #7

> Reservoir sampling is a family of randomized algorithms for randomly choosing a sample of k items from a list S containing n items, where n is either a very large or unknown number. Typically n is large enough that the list doesn't fit into main memory. So if N is really large and doesn't fit into main memory, how does one iterate over such large list in a reasonable amount of time? When I am taught algorithm my sa…

Basically you do a reverse fisher yates shuffle.

You are selecting n of N items, where N is unknown, in one pass, where every item is treated as unique, and where n is your sample size.

First get n items from N in an array of size n of candidates, which we'll call C.

Then, for each item k in N until you reach the end you know the current highest count, so select a random integer representing a location in an array of that count. If it's 0 to n - 1 (assuming a zero indexed array) replace the item in C with the current item k.

This means that each item will have an equal chance of being a final candidate when you reach N. If you care about order of the random sample, you can always shuffle n after you reach N.

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#57

Post by dalke »

kutkloon7 wrote: post #50

Again, I am confused. Why doesn't this snippet solve the problem? void increasingRandomSequence(arrayptr, base, k, n) { if (k == 0) return; int i = randInt(n - k); *(arrayptr) = base + i; increasingRandomSequence(arrayptr + 1, base + i + 1, k - 1, n - (i + 1)); } increasingRandomSequence(hand, 0, k, n) fills the array hand with a sequence which is picked with uniform distribution over all increasing sequences of leng…

The method is on-line, that is, it doesn't need to know "n".

Assuming I translated your above code correctly into Python, as:

    import random

    def increasingRandomSequence(base, k, n):
      while k > 0:
        i = random.randrange(n - k + 1)
        yield base + i
        base += i+1
        k -= 1
        n -= i+1
then I checked the above using:

    N = 6
    counters = [0] * N
    for i in range(100000):
        for value in increasingRandomSequence(0, 5, N):
            counters[value] += 1
    print(counters)
and found a strong bias towards larger numbers. The counts are:

    [50033, 75037, 87438, 93686, 96900, 96906]
which means 5 is in the hand much more often than 0.

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#58

Post by [deleted] »

dfabulich wrote: post #12

The C code in this article is a mirror of the code from Appendix 2 in Vitter's paper, which I guess explains/excuses the abbreviated variable names. The paper says things like, "use an exponentially distributed random variate Y," and uses variable names like n, N, U, S, X, y1, and y2 in the appendix. Nonetheless, I find this coding style unreadable. "Y" is not a very good name for an exponentially distributed random…

[deleted]

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#59

Post by throwaway_yy2Di »

CephalopodMD wrote: post #4

Could someone explain how this works? I feel like unique shuffling given a random seed is very useful algorithm, but I can't follow this code because of the variable naming and stuff.

The general idea is to draw n uniform samples from [1..N] and return them in sorted order. You can generate these incrementally, in order (no sort needed). The mean difference between successive samples is ~N/n. If the samples are uniformly distributed, their differences should have roughly an exponential [0] distribution (if N, n are large).

So the inductive step is: given k'th sample a[k], let a[k+1] = a[k] + S, where S is drawn from a discrete exponential distribution with mean 1/λ = N/n. That's the `exp(log(rand()) * stuff)' part of the code.

This almost works; there's more details [1] if you want it to actually work, and have accurate statistics, not overflow N, etc.

[0] https://en.wikipedia.org/wiki/Exponential_distribution

[1] https://hal.archives-ouvertes.fr/file/index/docid/75929/file...

Re: Vitter's reservoir sampling algorithm D: randomly selecting unique items

#60

Post by franciscop »

dantiberian wrote: post #10
franciscop wrote: post #5

Why cannot you just create random numbers and discard duplicates? For practical purposes when list.length << total.lenght shouldn't that be good enough?

I had the same thought. However thinking about it more, the requirement is that this algorithm is O(k). As k gets closer and closer to the size of the list, you will spend more and more time looking for unique items. You also need to pay the costs of checking for uniqueness which also grows with k.

Well yeah, that is exactly why I said for the situation where the lenght of the list is much smaller than the total number of tweets. Which should cover most practical usages.
Post reply on HN