Reservoir Sampling

example1.py

from random import randint

from node import init_list


def get_random(ll):
    rand_pos = randint(0, len(ll))
    i = 0
    node = None
    for n in ll:
        if i == rand_pos:
            node = n
            break
        i += 1
    return node


def main():
    ll = init_list()
    samples = get_random(ll)
    print(samples)


if __name__ == "__main__":
    main()

example2.py

from random import randint

from node import init_list


def get_random(ll):
    ret = None
    for index, n in enumerate(ll):
        if not ret:
            ret = n
        else:
            r = randint(0, index)  # [0..index]
            if r == 0:
                ret = n
    return ret


def main():
    ll = init_list()
    samples = get_random(ll)
    print(samples)


if __name__ == "__main__":
    main()

example3.py

from random import randint

from node import init_list


def get_random(ll):
    size = 10
    samples = []
    for index, n in enumerate(ll):
        if index < size:
            samples.append(n)
        else:
            r = randint(0, index)  # [0..index]
            if r < size:
                samples[r] = n
    return samples


def main():
    ll = init_list()
    samples = get_random(ll)
    print(samples)


if __name__ == "__main__":
    main()

node.py

from functools import total_ordering


@total_ordering
class Node(object):

    def __init__(self, value):
        self.value = value
        self._next = None

    def __repr__(self):
        nr = self._next.value if self._next else None
        return "<Node: this:%r -- next:%r>" % (self.value, nr)

    def __eq__(self, other):
        return self.value == other.value

    def __lt__(self, other):
        return self.value < other.value

    def __hash__(self):
        return hash(self.value)


class LinkedList(object):

    def __init__(self):
        self._start = None
        self._end = None

    def __iter__(self):
        current = self._start
        while current:
            yield current
            current = current._next
        raise StopIteration()

    def __len__(self):
        i = 0
        for n in self:
            i += 1
        return i

    def add(self, node):
        if not self._start:
            # First element
            self._start = node
            self._end = node
        else:
            self._end._next = node
            self._end = node


def init_list(size=100):
    ll = LinkedList()
    for i in range(size):
        ll.add(Node(i))
    return ll

output.py

In [1]: from node import init_list

In [2]: ll = init_list(size=50)   

In [3]: for n in ll:
   ...:     print(n)
   ...:     
<Node: this:0 -- next:1>
<Node: this:1 -- next:2>
<Node: this:2 -- next:3>
<Node: this:3 -- next:4>
<Node: this:4 -- next:5>
<Node: this:5 -- next:6>
<Node: this:6 -- next:7>
<Node: this:7 -- next:8>
<Node: this:8 -- next:9>
<Node: this:9 -- next:10>
<Node: this:10 -- next:11>
<Node: this:11 -- next:12>
<Node: this:12 -- next:13>
<Node: this:13 -- next:14>
<Node: this:14 -- next:15>
<Node: this:15 -- next:16>
<Node: this:16 -- next:17>
<Node: this:17 -- next:18>
<Node: this:18 -- next:19>
<Node: this:19 -- next:20>
<Node: this:20 -- next:21>
<Node: this:21 -- next:22>
<Node: this:22 -- next:23>
<Node: this:23 -- next:24>
<Node: this:24 -- next:25>
<Node: this:25 -- next:26>
<Node: this:26 -- next:27>
<Node: this:27 -- next:28>
<Node: this:28 -- next:29>
<Node: this:29 -- next:30>
<Node: this:30 -- next:31>
<Node: this:31 -- next:32>
<Node: this:32 -- next:33>
<Node: this:33 -- next:34>
<Node: this:34 -- next:35>
<Node: this:35 -- next:36>
<Node: this:36 -- next:37>
<Node: this:37 -- next:38>
<Node: this:38 -- next:39>
<Node: this:39 -- next:40>
<Node: this:40 -- next:41>
<Node: this:41 -- next:42>
<Node: this:42 -- next:43>
<Node: this:43 -- next:44>
<Node: this:44 -- next:45>
<Node: this:45 -- next:46>
<Node: this:46 -- next:47>
<Node: this:47 -- next:48>
<Node: this:48 -- next:49>
<Node: this:49 -- next:None>

In [4]: from example1 import get_random

In [5]: get_random(ll)
Out[5]: <Node: this:1 -- next:2>

In [6]: get_random(ll)
Out[6]: <Node: this:44 -- next:45>

In [7]: from example2 import get_random

In [8]: get_random(ll)
Out[8]: <Node: this:34 -- next:35>

In [9]: get_random(ll)
Out[9]: <Node: this:41 -- next:42>

In [10]: from example3 import get_random

In [11]: get_random(ll)
Out[11]:
[<Node: this:43 -- next:44>,
 <Node: this:1 -- next:2>,
 <Node: this:24 -- next:25>,
 <Node: this:31 -- next:32>,
 <Node: this:4 -- next:5>,
 <Node: this:33 -- next:34>,
 <Node: this:6 -- next:7>,
 <Node: this:7 -- next:8>,
 <Node: this:8 -- next:9>,
 <Node: this:17 -- next:18>]

In [12]: get_random(ll)
Out[12]:
[<Node: this:24 -- next:25>,
 <Node: this:21 -- next:22>,
 <Node: this:19 -- next:20>,
 <Node: this:3 -- next:4>,
 <Node: this:47 -- next:48>,
 <Node: this:5 -- next:6>,
 <Node: this:42 -- next:43>,
 <Node: this:25 -- next:26>,
 <Node: this:8 -- next:9>,
 <Node: this:17 -- next:18>]