>>> ================================ RESTART ================================
#=========================
# ITERATORS AND GENERATORS
#=========================
# executed y_r11_1_generators.py
# iterating over the elements of an existing container (a list)
>>> lst = [1,2,3]
>>> type(lst)
>>> li = iter(lst)
>>> type(li)
>>> next(li)
1
>>> next(li)
2
>>> next(li)
3
>>> next(li)
Traceback (most recent call last):
File "", line 1, in
next(li)
StopIteration
# "for" generates the iterator, recurrently calls next() and finally swallows the exception
>>> for e in lst:
print(e)
1
2
3
>>> ================================ RESTART ================================
# iterating over a sequence produced by a generator
>>> c1 = countdown_gen()
>>> c2 = countdown_gen()
# two different generators iterating over the same sequence, each preserving its own state
>>> c1 is c2
False
>>> next(c1)
5
>>> next(c2)
5
>>> for e in c1:
print(e)
4
3
2
1
launch
>>> next(c2)
4
>>> ================================ RESTART ================================
>>> l = Evens_list(10**8) # memory consumption goes up, since the entire list is expanded in memory
>>> for e in l:
pass
>>> del l # memory consumption goes down (garbage collector at work)
# in contrast, when using a generator memory consumption remains low
# since the entire sequence is never expanded (lazy evaluation)
>>> l = Evens_gen1(10**8)
>>> for e in l:
pass
>>> l = Evens_gen2(10**8)
>>> for e in l:
pass
>>> ================================ RESTART ================================
#===========
# Karp-Rabin
#===========
# executed y_r11_2_kr.py
>>> ================================ RESTART ================================
# fingerprint computation for basis = 2**16, r = 2**32-3
>>> fp_abr = fingerprint("abr")
# ord('a') = 97, ord('b') = 98, ord('r') = 114
>>> fp_abr == (97*2**32+98*2**16+114)%(2**32-3)
True
# fingerprint computation for next overlapping substring
>>> fp_bra = fingerprint("bra")
>>> fp_bra == ((fp_abr-97*2**32)*2**16+97)%(2**32-3)
True
# examining the choice of r
>>> s = "abracadabra"
>>> p = "da"
>>> find_matches_KR(p,s,basis=2**16, r=2**32-3) # default basis, default r
[6] # no false positives
>>> find_matches_KR(p,s, basis=2**16, r=2**16) # r modified to equal the basis
[2, 4, 6, 9] # false positives added
>>> fingerprint(p,basis=2**16,r=2**16)
97
>>> text_fingerprint(s,2,basis=2**16, r=2**16)
[98, 114, 97, 99, 97, 100, 97, 98, 114, 97] # every substring of length 2 ending with "a" is reported
# more generally, setting r to basis**k retains only k rightmost characters
# the next example demonstrates this for k = 5
>>> fingerprint("Humpty", r=2**(16*5))
2158299737877522940025
>>> fingerprint("Dumpty", r=2**(16*5))
2158299737877522940025
>>> find_matches_KR("Humpty","Humpty Dumpty",r=2**(16*5))
[0, 7]
>>> find_matches_KR("Humpty","Humpty Dumpty",r=(2**(16*6)))
[0]
# if we increase r the problem is solved in this particular case;
# however, when we increase r we pay in complexity.
# a better strategy is to make sure r is not a power of the basis.
# particularly, setting r as prime close to a power of 2 turns out to be a good choice in many cases.