<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 A brief overview of runtime analysis, data structures, and hashing
Common terms in computer science and engineering
Step1:  How do we test "contains"
Python gives us the "in" keyword for lists
Step2:  Without 'in', how do we do this?
We have no idea how Python is doing this under the hood. Let's try this without any python keywords.
Step3:  Is this fast? What does fast mean?
Let's say that the most expensive operation for us is a single comparison, word == element
In the best case, we match on the first word.
Let's add a counter to our contains function.
Step4:  In the worst case, we have to check all words.
Step5:  What if each comparison took 1 second?
Step6:  This is less than a MB of text! What if we wanted to search through every book in the library of congress? 
Runtime Analysis
Determining average and worst-case runtimes can be complicated, but for a simple for loop it is easy. Since our worst case runtime is bounded by the number of words ($n$) in the list, inceasing the number of words in the list increases the runtime by a linear factor, i.e. for $2n$, the worst case is $2n$ operations.
Other algorithms will scale in different ways, for example $n^2$ or even $2^n$. There are more details, but these runtimes are referred to as "Big O", so a linear algorithm is $O(n)$.
How can we do better?
What is faster than $O(n)$?
If all we can do is access the list by index, we can't do any better given our python list. We can actually do much better if the list is sorted, but sorting a list is worst case $O(n*\log n)$, which is even slower than our look up method.
Simpler problem
Step7:  We can still use our function to check contains, because python is forgiving that way.
Step8:  Use case
Step9:  If we want to say the integer 2 is in our word set, we set words_map[2] = True
Step10:  Starting from our empty set, let's load our wordslist in
Step11:  We did that look up only checking one entry!
Now we can write a contains function that does the same thing!
Step12:  Summary
We've figured out how to solve the query problem for a set of integer "words", but only if drawing from a fixed number of ints, e.g. 0 to 999,999
How might we apply this to the book problem?
Maybe we only care about words in the English language
~200,000 possible words, can make bitmap of size 200,000
Have some dictionary code for each word, e.g. aardvark = 3, zebra = 199,847
If you searched for a word outside the vocab, answer would be "I don't know"
New words are entering the language constantly!
We could make the bitmap big enough to store every possible word formed with lower case letters
There are 26 characters. There are $26^k$ possible strings of length $k$
Step13:  The modulus
We'll use the remainder of division by some number to reduce the infinite space of things to a list with length of our choosing.
Step14:  If we take $N % k$, the number will always be between $0$ and $k - 1$
Step15:  Populate our word_map
Step16:  This is called a collision. In a basic hashing bitmap, we can only say with certainty is a number is NOT in the map
Step17:  How can we get yes/no?
Instead of a bitmap to True/False, let's store the data directly! One list per entry in the map.
Step18:  How do we add a number to words_map?
Use mod to determine the index
Add the number itself to the list at the index
Step19:  Query, is number in word_map?
Step20:  We just made a hash table!
A "Hash function" is any function that converts some object of arbitrary size to number of fixed size.
Our hash function is just modulus!
Step21:  We set k equal to the length of our array. We can use any size of array by changing the mod k.
More about hash functions
There are many different hash functions. A good hash function will evenly distribute hashed values onto the fixed space. 
Python has a built-in hash function for exactly this purpose!
Step22:  Back to strings
Armed with python "hash" and the modulus, we can finish our hash table for words.
Step23:  Hash table Load Factor
$\lambda = \frac{N_{elements}}{M_{capacity}}$
Typical values are around .5 to .75 to give good performance.
The end!
Bonus
<ASSISTANT_TASK:>
Python Code:
def print_lines(filename, num_lines):
    count = 0
    with open(filename,'r') as f:
        for line in f:
            for word in line.split():
                print word
            count += 1
            if count >= num_lines:
                break
print_lines('leaves-of-grass.txt', 4)
import re
with open('leaves-of-grass.txt','r') as f:
    words = [word.lower() for line in f for word in re.findall(r"[\w']+|[.,!?;]", line)]
print "number of words =", len(words)
print words[0]
print words[12305]
print words[148185]
print words[148186]
Explanation: A brief overview of runtime analysis, data structures, and hashing
Common terms in computer science and engineering:
* "List"
* Array, Linked List
* Worst case runtimes
* O(n) (linear)
* Hashing
* Hash table
* P and NP
Related terms in Python:
* list
* dict (dictionary)
* set
Motivation: Does some word exist in some book?
Case study, Leaves of Grass by Walt Whitman
End of explanation
print 'leaves' in words
print 'leaVes' in words
print 'captain' in words
print 'internet' in words
Explanation: How do we test "contains"
Python gives us the "in" keyword for lists
End of explanation
def contains(wordlist, word):
    if len(wordlist) == 0:
        # Wordlist is empty
        return False
    for i in xrange(len(wordlist)):
        element = wordlist[i]
        if word == element:
            return True
    # No match in wordlist
    return False
print contains(words, 'captain')
print contains(words, 'internet')
Explanation: Without 'in', how do we do this?
We have no idea how Python is doing this under the hood. Let's try this without any python keywords.
End of explanation
def contains(wordlist, word):
    if len(wordlist) == 0:
        # Wordlist is empty
        print "Checked 1 word(s)"
        return False
    for i in xrange(len(wordlist)):
        element = wordlist[i]
        if word == element:
            print "Checked", i+1, "word(s)"
            return True
    # No match in wordlist
    print "Checked", i+1, "word(s)"
    return False
print contains(words, 'leaves')
print contains(words, 'captain')
Explanation: Is this fast? What does fast mean?
Let's say that the most expensive operation for us is a single comparison, word == element
In the best case, we match on the first word.
Let's add a counter to our contains function.
End of explanation
print contains(words, 'internet')
Explanation: In the worst case, we have to check all words.
End of explanation
print "Worst case is %.1f days to query 'words'" % (len(words)/60./60/24)
Explanation: What if each comparison took 1 second?
End of explanation
import random
print random.randint(0, 10**6)
print random.randint(0, 10**6)
print random.randint(0, 10**6)
print random.randint(0, 10**6)
n = len(words)
print n
words = [random.randint(0, 10**6 - 1) for i in range(n)]
words[0:10]
Explanation: This is less than a MB of text! What if we wanted to search through every book in the library of congress? 
Runtime Analysis
Determining average and worst-case runtimes can be complicated, but for a simple for loop it is easy. Since our worst case runtime is bounded by the number of words ($n$) in the list, inceasing the number of words in the list increases the runtime by a linear factor, i.e. for $2n$, the worst case is $2n$ operations.
Other algorithms will scale in different ways, for example $n^2$ or even $2^n$. There are more details, but these runtimes are referred to as "Big O", so a linear algorithm is $O(n)$.
How can we do better?
What is faster than $O(n)$?
If all we can do is access the list by index, we can't do any better given our python list. We can actually do much better if the list is sorted, but sorting a list is worst case $O(n*\log n)$, which is even slower than our look up method.
Simpler problem: list of ints
Let's say that instead of strings, our "words" are just integers randomly chosen from 0 to 1 million
End of explanation
contains(words, 1)
contains(words, 9999)
contains(words, 100000)
contains(words, 413351)
Explanation: We can still use our function to check contains, because python is forgiving that way.
End of explanation
# Start with the empty set of ints from 1 to 999,999
words_map = [False for i in range(1000000)]
words_map[0:10]
Explanation: Use case: fast queries
We can afford to process the data for 1 day, but queries should run in 1 second. How can we do this for arbitary lists.
Since we know that the number of integers is bounded by [0,100000) we can make a custom data structure to represent our unsorted set of words. Its form is a list, where the index is the integer in question, and the data is a boolean representing true or false (in the set, not in the set.)
This type of data structure is sometimes called a bit map. It maps the integer field to a "bit" (yes or no)
End of explanation
words_map[2] = True
words_map[0:10]
Explanation: If we want to say the integer 2 is in our word set, we set words_map[2] = True
End of explanation
words_map = [False for i in range(1000000)]
for i in words:
    words_map[i] = True
contains(words, 219943)
words_map[219943]
Explanation: Starting from our empty set, let's load our wordslist in
End of explanation
def contains_map(word_bitmap, word):
    # Caution, only works on integers up to len(word_bitmap)!
    print "Checked 1 word(s)"
    return word_bitmap[word]
contains(words, 219943)
contains_map(words_map, 219943)
contains(words, 99149)
contains_map(words_map, 129343)
Explanation: We did that look up only checking one entry!
Now we can write a contains function that does the same thing!
End of explanation
for i in range(2,10):
    print "Word of length %d has %d possible combinations" % (i, 26**i)
Explanation: Summary
We've figured out how to solve the query problem for a set of integer "words", but only if drawing from a fixed number of ints, e.g. 0 to 999,999
How might we apply this to the book problem?
Maybe we only care about words in the English language
~200,000 possible words, can make bitmap of size 200,000
Have some dictionary code for each word, e.g. aardvark = 3, zebra = 199,847
If you searched for a word outside the vocab, answer would be "I don't know"
New words are entering the language constantly!
We could make the bitmap big enough to store every possible word formed with lower case letters
There are 26 characters. There are $26^k$ possible strings of length $k$
End of explanation
4/2
4%2
5/2
5%2
2000/1000
2999/1000
2999%1000
3000/1000
Explanation: The modulus
We'll use the remainder of division by some number to reduce the infinite space of things to a list with length of our choosing.
End of explanation
k = 100000
words_map = [False for i in range(k)]
words_map
len(words_map)
Explanation: If we take $N % k$, the number will always be between $0$ and $k - 1$
End of explanation
for i in words:
    words_map[i%k] = True
words_map
words_map[5]
5 % k
100005 % k
Explanation: Populate our word_map
End of explanation
def contains_modmap(word_modmap, k, word):
    print "Checked 1 word(s)"
    if word_modmap[word % k]:
        return "Maybe"
    else:
        return False
contains_modmap(words_map, 100000, 219943)
Explanation: This is called a collision. In a basic hashing bitmap, we can only say with certainty is a number is NOT in the map
End of explanation
k = 100000
words_map = [list() for i in range(k)]
words_map
Explanation: How can we get yes/no?
Instead of a bitmap to True/False, let's store the data directly! One list per entry in the map.
End of explanation
number = 3
word_list = words_map[3 % k]
word_list.append(3)
words_map
number = 100003
word_list = words_map[number % k]
word_list.append(number)
words_map
Explanation: How do we add a number to words_map?
Use mod to determine the index
Add the number itself to the list at the index
End of explanation
def contains_modmap(word_modmap, k, word):
    word_list = word_modmap[word % k]
    print contains(word_list, word)
contains_modmap(words_map, 100000, 100003)
words_map[3 % 100000]
Explanation: Query, is number in word_map?
End of explanation
def our_hash(n):
    k = 100000
    return n % k
Explanation: We just made a hash table!
A "Hash function" is any function that converts some object of arbitrary size to number of fixed size.
Our hash function is just modulus!
End of explanation
hash(0)
hash(1)
hash("Ryan")
hash("Ryan") % 10
Explanation: We set k equal to the length of our array. We can use any size of array by changing the mod k.
More about hash functions
There are many different hash functions. A good hash function will evenly distribute hashed values onto the fixed space. 
Python has a built-in hash function for exactly this purpose!
End of explanation
# Load the book in again
with open('leaves-of-grass.txt','r') as f:
    words = [word.lower() for line in f for word in re.findall(r"[\w']+|[.,!?;]", line)]
k = 100000
words_hashtable = [list() for i in range(k)]
for word in words:
    word_list = words_hashtable[hash(word) % k]
    word_list.append(word)
words_hashtable
def contains_hashtable(words_hashtable, k, word):
    word_list = words_hashtable[hash(word) % k]
    print contains(word_list, word)
print contains(words, 'captain')
contains_hashtable(words_hashtable, 100000, 'lincoln')
Explanation: Back to strings
Armed with python "hash" and the modulus, we can finish our hash table for words.
End of explanation
print "leaves" < "zebra"
print "leaves" < "abc"
words.sort()
print words[0]
print words[30000]
print words[90000]
print words[148186]
book.__contains__("captain")
Explanation: Hash table Load Factor
$\lambda = \frac{N_{elements}}{M_{capacity}}$
Typical values are around .5 to .75 to give good performance.
The end!
Bonus: Sorted lists
End of explanation
<END_TASK>