"buffered" reservoir sampling


  • 13

    As I pointed out earlier, reservoir sampling can seem inefficient presumably due to the many requests to the random number generator. My naive count+pick took about 180 ms, much faster than the reservoir sampling solutions taking about 400 ms or more. So I created a buffered way, where I update the random pick only every 100 nodes. Takes about 200 ms now. So still slower than the naive count+pick, but might be advantageous in some situations because it doesn't traverse the list twice.

    class Solution(object):
    
        def __init__(self, head):
            self.head = head
    
        def getRandom(self):
            node = self.head
            before = 0
            buffer = [None] * 100
            while node:
                now = 0
                while node and now < 100:
                    buffer[now] = node
                    node = node.next
                    now += 1
                r = random.randrange(now + before)
                if r < now:
                    pick = buffer[r]
                before += now
            return pick.val
    

    C++ version: (takes about 61 ms)

    class Solution {
    public:
        Solution(ListNode* head) : head(head) {}
        
        int getRandom() {
            ListNode *node = head, *buffer[100], *pick;
            for (int before=0; node; before+=100) {
                int now = 0;
                while (node && now < 100) {
                    buffer[now++] = node;
                    node = node->next;
                }
                int r = rand() % (now + before);
                if (r < now)
                    pick = buffer[r];
            }
            return pick->val;
        }
    private:
        ListNode* head;
    };
    

  • 0

    To the downvoter: If you explain the issue, I'll be happy to fix it or tell you why you're wrong.


  • 0

    @StefanPochmann
    So, when there are more than 100 nodes, let say 200, you solution still needs to go through 200 nodes to pick one to return. In addition, the 100 buffered nodes just the vals of first 100 nodes?


  • 1
    H

    Really cool solution! Thanks for sharing.
    It takes some efforts to figure out why it is right and neat.


  • 0

    @yubad2000 Sorry, I don't understand your question.


  • 1

    @StefanPochmann
    I am not good at Python. Just try to understand your logic and then implement it in Java to compare the run time.
    I think "now" is a pointer which points to the available space or tail of the buffer, right?
    When now < 100, we put current node into the buffer and go to next node until node==null or now == 100.
    There are two cases, N<=100 and N>100, where N is the total number of nodes.
    When N<=100, it is the same as the O(N) space solution.
    When N>100, it seems that your solution initially picks one node between 1st node and the 100th node, and then keep picking one from the next 100 nodes.
    So, the advantage is to call the random once every 100 nodes if I understand your solution correctly.


  • 1

    @yubad2000 Yes, I go through the list in chunks of 100 nodes (or fewer, in the last chunk) and for each chunk I use just one random number to either keep the the result node or replace it by one in the current chunk. My now tells me how many nodes are in the current chunk and my before tells me how many nodes I went through in all previous chunks.


  • 0
    X

    Yes, it's more fast,because it use fewer random() function.Here is my explanation.
    the number of the nodes is mk+n,kis the buffer size,nis the number of the left nodes.
    first buffer:p = 1/k * k/2k * ··· * (m-1)k/mk * mk/mk+n = 1/mk+n
    i th buffer:p = 1/k * k/ik * ik/(i+1)k *···*(m-1)k/mk * mk/mk+n = 1/mk+n
    last buffer: p = 1/n * n/mk+n = 1/mk+n
    so, every node can be chosed with the same probability and no matter what k is.

    :D poor English but great solution


  • 0
    V

    I think this article here might be of help: https://gregable.com/2007/10/reservoir-sampling.html

    Basically to make it fast you only need to keep the last position of the head (i.e. last seen element) and a count of elements seen so far. When you have the new element you calculate the probability that it becomes part of the reservoir.


  • 1

    @vulkum You mean if I undo my speed improvement and go back to regular reservoir sampling, it would be faster? Sorry, but that is nonsense.


  • 0
    V

    @StefanPochmann I might be a bit confused here, but aren't you starting from the head of the list every time when getRandom is being called?


  • 0

    @vulkum Yes I am. Aren't you as well? Can you please show your code? Your above description is quite unclear and now sounds like you're not solving the problem properly.


  • 0
    D

    Brilliant solution @StefanPochmann!


  • 0

    very interesting. Can you tell me why Random number generator is a slow operation? I was not aware of this issue. Thanks!


  • 1

    @jdrogin Well in order to generate something, it needs to do some computations. And it's not something super duper simple with bad randomness. Python for example uses the Mersenne Twister.

    A little test comparing randrange with a "do-nothing"-function:

    >>> from timeit import timeit
    >>> timeit('randrange(2)', 'from random import randrange')
    0.5261339264198597
    >>> timeit('f(2)', 'def f(i): return i')
    0.08923129713238609
    
    

  • 0

    @StefanPochmann very true. I did a time test as well (C#) and results were varied.

    Million iterations

    • Random -> 30-200ms
    • Looping no func call -> 0-15ms
    • Looping func call -> 10-30ms

    So definitely there is some time cost for random, but seems if you're not doing too many cost is low. The results did vary quite a bit so you'd really have to be very performance cautious to want to go around the random call.

            public int RandTime()
            {
                Random rand = new Random(0);
                int x = 0;
                DateTime start = DateTime.Now;
                for (int i = 0; i < 1000000; i++) x = rand.Next(int.MaxValue);
                DateTime end = DateTime.Now;
                Console.WriteLine("Random: " + (end - start).TotalMilliseconds + "ms");
                return x;
            }
            public int NothingTime()
            {
                int x = 0;
                DateTime start = DateTime.Now;
                for (int i = 0; i < 1000000; i++) x = i;
                DateTime end = DateTime.Now;
                Console.WriteLine("Nothing: " + (end - start).TotalMilliseconds + "ms");
                return x;
            }
            public int NothingCallTime()
            {
                int x = 0;
                DateTime start = DateTime.Now;
                for (int i = 0; i < 1000000; i++) x = PlusOne(i);
                DateTime end = DateTime.Now;
                Console.WriteLine("Nothing Call: " + (end - start).TotalMilliseconds + "ms");
                return x;
            }
            public int PlusOne(int i)
            {
                return i + 1;
            }
    

  • 0

    @jdrogin Your comparison isn't fair, as x = i doesn't involve any overhead for accessing and calling a method (and getting int.MaxValue and feeding it to the method). You'd better create an object with a "do-nothing"-method in order to measure how costly the actual work inside rand.Next is.


  • 0

    On the other hand, it's also interesting (maybe more interesting) how fast it is compared to a simple instruction, so your test is good as well. But I'd still like to see what times you get when you call a "do-nothing"-method.


  • 0

    I did another test, mixing our tests:

    >>> n = 10**8
    
    >>> timeit('x = randrange(2)', 'from random import randrange', number=n)
    50.13983665281921
    
    >>> timeit('x = f(2)', 'def f(i): return i', number=n)
    7.2656591126660715
    
    >>> timeit('x = 2', number=n)
    1.4361703853760446
    

  • 0

    @StefanPochmann good catch on the inner work for the loop. I've updated my previous reply with some new results. I think the bottom line is, yes, the random call has some cost, but results will vary and you'd have to be doing a ton of random calls for you to see much difference in performance, at least on my laptop! Thanks for sharing.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.