<jupyter_start><jupyter_text>Reservoir Sampling <NAME> ECE '19 IntroductionThis tutorial will give you a taste of a randomized algorithm family called reservoir sampling. This is an algorithm that is commonly used to pick a set number of items from a dataset of unknown size. Before we jump into the algorithm itself, let's look at a sample simple scenario. Simple ScenarioImagine you have a pool of 100 people (N = 100). You want to randomly select 20 of them to come with you on a weekend trip to <NAME> Falling Water (k = 20). The simple and intuitive way to do this to generate k random numbers between 0 and N-1, get the name at every corresponding index, and then invite those people and enjoy your trip. Note: each index must be unique - you can't clone a person and take them on the trip. Let's quickly take a look at how this would work, assuming N is small (10000 will do for this quick example).<jupyter_code>import string
import pandas as pd
import time
import random
import csv
import math
#Let's generate N random, faux names.
def simpleNameGenerator(N):
    result = []
    letters = string.ascii_uppercase
    length = len(letters)
    for i in range(N):
        index = i % length
        multiplier  = i // length + 1
        toAdd = str(letters[index])*multiplier
        result += [toAdd]
    assert (len(result) == N)
    return result

ourNames = simpleNameGenerator(10000)
# print(ourNames)
#From my N friends, pick k of them
def pickMyFriends(myList, N, k):
    result = []
    seen = set([])
    count = 0
    while(count < k):
        index = random.randint(0, N-1)
        if index not in seen:
            seen.add(index)
            result += [myList[index]]
            count += 1
    return result

start_time = time.time()
ourFriends = pickMyFriends(ourNames, 10000, 20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourFriends)<jupyter_output>--- 0.000159978866577 seconds ---
['XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX', 'DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD', 'LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL', 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF', 'UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU[...]<jupyter_text>Tweaked ScenarioAgain, imagine you have a pool of people. You want to randomly select k of them to come with you on a weekend trip to <NAME>'s Falling Water (k = 20). However, now you have absolutely no idea how large your pool of friends is (N). N could equal 4 or it could equal 999,000,000,000. The naive soultion would be to iterate through the given list (of the pool of people) to calculate N and then do as we did above (i.e. generate k random numbers between 0 and N-1, get the name at every corresponding, unique index, and so on. Let's see how this would pan out on the list we used above. Let's assume for the sake of this problem that python's len() function cannot be employed.<jupyter_code>#Find N and then pick k from N
def pickMyFriendsNoN(myList, k):
    result = []
    seen = set([])
    count = 0
    array = myList
    N = 0
    while(array != []):
        N += 1
        array = array[1:]
    while(count < k):
        index = random.randint(0, N-1)
        if index not in seen:
            seen.add(index)
            result += [myList[index]]
            count += 1
    return result

start_time = time.time()
ourFriends = pickMyFriendsNoN(ourNames, 20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourFriends)<jupyter_output>--- 0.362530946732 seconds ---
['VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV', 'UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU', 'EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE', 'VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV', 'SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS', 'QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ', 'XXXXXXXXXXXXXXXXXXXXXXXXXXXX', 'UUUUUUUUUUUUUUU', 'RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR', 'BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB', 'BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB[...]<jupyter_text>The AlgorithmObserve that the latter code we ran where we calculated the length (N) of our list is orders of magnitude slower than our former code where N was provided to us. We need not run through the array twice in the tweaked problem. There has to be a faster way of generating k random samples from an unknown sized pool or reservoir. Cue the algorithm! The ConceptReservoir sampling allows us to solve this tweaked problem in a quick and efficient manner, O(n) time as opposed to O(n^2) from the double pass seen above. It seems intuitive to want to iterate through the pool (also known as stream) to create our reservoir of size k. More often than not, this alogrithm is used when the stream we are sampling from is too large to store in memory and it would be grossly inefficient to iterate through the unknown sized list that could have millions and millions of data points - we will discuss practical uses in a bit. But first, how do we implement this algorithm in O(n) time. The Specifications1. To start, we will fill a reservoir of the first k samples from our pool (also known as stream).2. Next, we want to iterate through the list once, from k+1 to the len(N).3. During this iteration, we will generate a random integer - if that integer is less than k, then we will replace the element at the integer index found with the current element of our iteration.<jupyter_code>#Fill the reservoir with k elements and then randomly pick elements to replace
def reservoirSampling(myList, k):
    reservoir = []
    for index in range(k):
        reservoir += myList[index]
    for j in range(k+1, len(myList)):
        i = random.randint(0, j)
        if i < k:
            reservoir[i] = myList[j]
    return reservoir
        
start_time = time.time()
ourFriends = reservoirSampling(ourNames, 20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourFriends)<jupyter_output>--- 0.0368258953094 seconds ---
['DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD', 'ZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZZ', 'RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR', 'LLLLLLL', 'JJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ[...]<jupyter_text>The WhyWhen we originally pick our k elements from the stream to put into the reservoir, each element is picked with a probability of k/n. We pick our n+1 element with a probability of k/(n+1) and the elements currently in our list have a 1/k probability of eviction. The probability we replace an element is (k/(n+1))*(1/k) = 1/(n+1), which means that the probabilty we don't replace an element is n/(n+1). In order for an element to be in the n+1 set, it has to be chosen and evict an existing element (probability of k/(n+1)) or it has to have been in the original n set and not chosen to be replace ((k/n)*(n/(n+1)) = k/(n+1))! Weighted Reservoir SamplingLet's imagine a similar scenario except we have a corresponding list of weights associated with each item in the list. We prefer certain items to be in our reservoir over others. We adjust the algorithm to be as follows.  The Specifications1. To start, we will fill a reservoir of the first k samples from our pool (also known as stream), again. This time though. We will sum their weights as we go. When we add a new weight in, we divide by k to ensure proportionality.2. Next, we want to iterate through the list once, from k+1 to the len(N).3. We will add the weight of the current element to the sum. The probability of replacement will be this current item's weight over the sum.3. Then we will replace the element at a randomly picked index between 0 and k index with the current element of our iteration if and only if a randomly generated number between 0 and 1 is less than or equal to the probability we calculated earlier!<jupyter_code>#Let's generate N random weights
def weightGenerator(N):
    return [random.random() for i in range(N)]

weightedNames = zip(ourNames,weightGenerator(10000))
# print(weightedNames)
#As you fill the reservoir to start, add the weights proportionally. Then, based on the current weight, add the current
#element to the reservoir
def reservoirSampling(myList, k):
    reservoir = []
    totalWeight = 0
    for index in range(k):
        reservoir += myList[index][0]
        totalWeight += (myList[index][1]/k)
    for j in range(k+1, len(myList)):
        totalWeight += (myList[j][1]/k)
        prob = myList[j][1] / totalWeight
        check = random.random()
        if check < prob:
            index = random.randint(0,k-1)
            reservoir[index] = myList[j][0]
    return reservoir
        
start_time = time.time()
ourFriends = reservoirSampling(weightedNames, 20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourFriends)<jupyter_output>--- 0.0135481357574 seconds ---
['AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA', 'RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR', 'SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSS', 'KKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKK', 'YYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY[...]<jupyter_text>An AsideDistributed Random Sampling is a popular technique used to perform reservoir sampling across several machines. Sometimes our stream of data is too large to be stored in memory and would take too long to process on one machine. At that point, we can decide to distribute the data amongst m machines, each of which does its own weighted sampling of k elements as described above. We amalgamate the k samples from each, and then regenerate keys on one machine to pick the final k elements. Practical UsesAs stated earlier, reservoir sampling comes most in handy when an entire data stream does not fit in memory. Imagine if our stream was every Google search performed in the month of June every year since Google's inception or every transaction made on Amazon in the past three holiday seasons - these streams are extremely large. In order to randomly select a k number of them we would need to probably employ distributed random sampling, as these streams would a) be too large to efficiently iterate over to get its size and b) may not fit into memory - or would significantly slow down our machine if we tried. Twitter ExampleIn our past homeworks, we have manipulated Twitter data. Let's do a real life example where we load and select k tweets from an unknown stream of tweets to presumably do data analysis on.<jupyter_code># From HW2, load our tweets.csv
def load_twitter_data_pandas(tweets_filepath):
    tweets_df = (pd.read_csv(tweets_filepath)).fillna("")
    return tweets_df
(tweets_df) = load_twitter_data_pandas('tweets.csv')
# make sure to change the path to csv files appropriately
print (tweets_df.head())
#Fill the reservoir with k elements and then randomly pick elements to replace
def tweetReservoirSampling(df, k):
    reservoir = []
    listDF = df.values.tolist()
    for index in range(k):
        reservoir += listDF[index]
    for j in range(k+1, len(listDF)):
        i = random.randint(0, j)
        if i < k:
            reservoir[i] = listDF[j]
    return reservoir
        
start_time = time.time()
ourTweets = tweetReservoirSampling(tweets_df, 20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourTweets)<jupyter_output>--- 0.0279831886292 seconds ---
[['RapidCityPD', 'Sat Sep 17 02:05:47 +0000 2016', 0, 1, '@tweeks210 Pretty clam and quiet for the most part, but we see our fair share of action.'], ['AnnCoulter', 'Sat Sep 17 07:40:37 +0000 2016', 954, 0, 'RT @I_AmAmerica: If H<NAME> have the chance to appoint 2 to 4 Supreme Court Justices, it could change our Republic forever.Please C\xe2\x80\xa6'], ['LGlick1', 'Wed Sep 14 00:03:06 +0000 2016', 4, 9, "Let's let the people decide! @realDonaldTrump #VoteTrump #MAGA  https://t.co/ePfDb2Jd7Q"], ['andersoncooper', 'Fri Jul 29 04:02:43 +0000 2016', 0, 34, '@megfarrisWWL cant wait for wrinkle free friday!'], ['evangelistmatt', 'Sat Sep 17 02:04:34 +0000 2016', 37, 0, 'RT @EvanHeadrick: #HillsongMovie was unbelievable. Incredible film. I have such a deeper respect and love for who they are, and their music.'], ['joshspragins', 'Sat Aug 20 16:42:25 +0000 2016', 326, 0, 'RT @CoachKWisdom: All dreams come true if we have the courage to pursue them.'], ['[...]<jupyter_text>Tweaked ScenarioLet's now imagine that we wanted to associate a specific weight with a given scenario. Frist let;s randomly generate weights for the given screen names. After that, let's randomly pick 20 tweets to analyze.<jupyter_code>#First lets isolate the screen names and make a dictionary where the key value pairs are the unique screen name and a
#random weight
def makeSetOfScreenNames(df):
    return set(df["screen_name"].tolist())

myScreenNames = makeSetOfScreenNames(tweets_df)
#print(makeSetOfScreenNames(tweets_df))

def screenNameWeights(screenNames):
    screenNameWeights = {}
    for name in screenNames:
        screenNameWeights[name] = random.random()
    return screenNameWeights
 
myWeights = screenNameWeights(myScreenNames)
print(screenNameWeights(myScreenNames))
#Fill the reservoir with k elements and then randomly pick elements to replace
def tweetWeightedReservoirSampling(df, weight, k):
    reservoir = []
    listDF = df.values.tolist()
    totalWeight = 0
    for index in range(k):
        reservoir += listDF[index]
        totalWeight += (weight[listDF[index][0]]/k)
    for j in range(k+1, len(listDF)):
        totalWeight += (weight[listDF[index][0]]/k)
        prob = weight[listDF[index][0]]/ totalWeight
        check = random.random()
        if check < prob:
            index = random.randint(0,k-1)
            reservoir[index] = listDF[j]
    return reservoir
        
start_time = time.time()
ourWTweets = tweetWeightedReservoirSampling(tweets_df, myWeights,20)
print("--- %s seconds ---" % (time.time() - start_time))
print(ourWTweets)<jupyter_output>--- 0.0220670700073 seconds ---
[['SIGolfPlus', 'Wed Nov 05 21:33:28 +0000 2014', 6, 11, 'The Bump &amp; Run, a shot you need in your bag: http://t.co/GEV2HN2ypl'], ['EricTrumpFdn', 'Fri Jun 24 21:31:06 +0000 2016', 28, 67, "Here's a sneak peek at what to expect at our 10th Annual #ETF Golf Invitational &amp; Auction Dinner!  Details soon! \xe2\x9b\xb3\xef\xb8\x8f https://t.co/vMJQb2bw6T"], ['TrumpChicago', 'Tue Sep 13 15:51:55 +0000 2016', 0, 2, 'Meet the Sixteen Team:\nExecutive Pastry Chef <NAME> \n*From: Iowa\n*Favorite day off food: Vietnamese... https://t.co/KfGjosIpi7'], ['CusterChronicle', 'Thu Sep 15 19:30:39 +0000 2016', 0, 0, 'Volleyball takes three wins in busy week https://t.co/D9dxq3JtQq'], ['Kampkoa', 'Fri May 20 17:45:15 +0000 2016', 0, 0, 'Think people - Do not approach...  they are wild animals...\nhttps://t.co/58cAyepKsB'], ['ErinAndrews', 'Fri Sep 16 00:45:20 +0000 2016', 0, 0, '@Reveretoo ugh what?'], ['BlackHillsWine', 'Wed Sep 07 21:16:17 +0000 2016', 1, 0[...]
{'fraction_non_alphanumeric': 0.07590306355738455, 'fraction_numerical': 0.027377686328303612, 'mean_word_length': 5.0837969401947145, 'pattern_counts': {'":': 0, '<': 30, '<?xml version=': 0, '>': 24, 'https://': 5, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 26, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '540329', 'license': 'MIT', 'n_tokens_mistral': 6458, 'n_tokens_neox': 5567, 'n_words': 1857, 'path': '2016/tutorial_final/161/reservoir_sampling.ipynb', 'repo_name': 'zeromtmu/practicaldatascience.github.io', 'size': '17542'}