Fixed-Size sample (Reservoir Sampling)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

import random
from typing import List, Any

class ReservoirSampler:
    def __init__(self, k: int):
        """
        Initializes the reservoir sampler.
        
        Args:
            k (int): The number of items to maintain in the reservoir.
        """
        self.k = k
        self.reservoir = []
        self.stream_size = 0  # Tracks the number of items processed in the stream
    
    def add_to_reservoir(self, new_item: Any) -> None:
        """
        Processes a new item from the stream and updates the reservoir.
        
        Args:
            new_item (Any): The new item from the stream to process.
        """
        self.stream_size += 1
        
        if len(self.reservoir) < self.k:
            # Fill the reservoir until it reaches size k
            self.reservoir.append(new_item)
        else:
            # Replace an existing item with a decreasing probability
            j = random.randint(1, self.stream_size)
            if j <= self.k:
                self.reservoir[j - 1] = new_item

    def get_reservoir(self) -> List[Any]:
        """
        Returns the current reservoir.
        
        Returns:
            List[Any]: The list of items in the reservoir.
        """
        return self.reservoir