Algorithms For Dummies

 

   

  PART 4 

 Struggling with Big Data

['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L',

 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',

 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',

 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v',

 'w', 'x', 'y', 'z']

Apart from strings, the example uses functions from the random package to cre-

ate a seed (for stable and replicable solutions) and, drawing a random integer 

number, it checks whether it needs to change an element in the reservoir. Apart 

from the seed value, you can experiment with modifying the sample size or even 

feeding  the  algorithm  a  different  stream  (it  should  be  in  a  Python  list  for  the 

example to work correctly).

from random import seed, randint

seed(9) # change this value for different results

sample_size = 5

sample = []

for index, element in enumerate(datastream):

        # Until the reservoir is filled, we add elements

        if index < sample_size:

                sample.append(element)

        else:

                # Having filled the reservoir, we test a

                # random replacement based on the elements

                # seen in the data stream

                drawn = randint(0, index)

                # If the drawn number is less or equal the

                # sample size, we replace a previous

                # element with the one arriving from the

                # stream

                if drawn < sample_size:

                        sample[drawn] = element

print (sample)

['y', 'e', 'v', 'F', 'i']

This procedure assures you that, at any time, your reservoir sample is a good 

sample representing the overall data stream. In this implementation, the variable 

index

 plays the role of n and the variable 

sample_size

 acts as k. Note two par-

ticular aspects of this algorithm:

---

CHAPTER 12