Python 3.2.5 (default, May 15 2013, 23:07:10) [MSC v.1500 64 bit (AMD64)] on win32 Type "copyright", "credits" or "license()" for more information. >>> ================================ RESTART ================================ #The repeating substring problem: # Input: string st of length n and a positive integer l # Output: Is there a substring of length l in st which appears more than once? #Running the naive solution for the repeating substring problem >>> >>> repeat_naive("hello", 1) True >>> repeat_naive("hello"*10, 45) True >>> repeat_naive("hello"*10, 46) False #generating a random string >>> s = gen_str(10**3) >>> s 'hrikhkvuljsxkrgsywcfhufjzvdqrgfemqqoumhobvqrminbganpzeufdlpbdfzgvntvdefjmbpkzszlfmucmeokbgpddzfjldcojropjkavodnwxlntcgzznpgiotzwhcojqshxxhukctvjzdmlkkzqkxuapnluzrsidqnwmufybijypxjcxchrtbvbafihtkeapgzbyqintwszpfprczrpcikjbjrmlgyyphgicvbkxkfivkvnefphjcqmlqswdpmbjgscshuagunwwwvokbjnayznscrntmphnzvgyvampywlvjkayyokrxyttyuneshmntzawrgkptmlhzbfukonpagekzugeowvwdyodacbqwkrlnidlmvgtnnwvktkgbttmayehxzzqrifnivqmzzejpappfqaofkehvxekzdzcdfxirghjbunlennousrnrovuqasqbjiczazlkqlexsyzslyufifpjapubbdqnztzceciqjkyukrwqnctxjrdboysliymcjhdqdhedcbzbvhqbvgdtrlxyixwujtkluyqkdlmjxsmdclvnpepqogevbyzfwpdsnfofcpgqznpalesnlltfacqasyeefxjunlobbopwxqmlkewpckyflvyitogseurokbmpkslibfzxxbdmkrhdomyyvcqdawypciphdusukgcdserbvtdpnhqbwuqaqkehqxuigshkfdckwsyypgbnhdwpbqkhaebeqyheaxmdofyindlyjdrxntgadzsgjqfzhmabmdypogqiscxxwbokmlrogmgxdohrhlqxuxqntyaocntstjlevjvdlcfnhwqabnsguxtwtupkuqplrtkfcghjqrjdjyshpjawgbyhehutfxkazeshrmfnarjsktqvxkspdzsqeajsqbjqljcsrqgjehrcutycwifnscaemenkynvjpuufsxioiufczygyyhppgyrypdtocdinifcqjefdyyevtk' >>> repeat_naive(s, 3) True >>> repeat_naive(s, 10) False #running the naive solution over a random string of length 10**4 takes too long >>> s = gen_str(10**4) >>> repeat_naive(s, 10) Traceback (most recent call last): File "", line 1, in repeat_naive(s, 10) File "C:\Personal\Teaching\CS-intro\2016a\Recitations\10\m_09_hash.py", line 8, in repeat_naive if st[i:i+l]==st[j:j+l]: KeyboardInterrupt #running the solution using Hashtable class from the lectures is much more efficient (for the average case) >>> repeat_hash1(s, 10) False #Competition between the 3 solutions: #for a string of length n=1000 >>> ================================ RESTART ================================ >>> str_len= 1000 repeating substring len= 10 repeat_naive 0.22223344996147484 found? False repeat_hash1 0.002262564892824226 found? False repeat_hash2 0.0006647172504389287 found? False >>> ================================ RESTART ================================ #for a string of length n=2000 (we doubled the value of n) >>> str_len= 2000 repeating substring len= 10 repeat_naive 0.8519638368553348 found? False # 4 times slower repeat_hash1 0.004687361846177129 found? False # 2 times slower repeat_hash2 0.0013925905341737321 found? False # ~2 times slower >>> ================================ RESTART ================================ #When a repetition is found (quickly), repeat_hash1 may be slower than the naive solution # since this solution constructs an empty table of size ~(n-l). # On the other hand repeat_hash2 (which uses python set() ) is more efficient, since # a small table is constructed at first (its size increases when the table gets almost full) >>> str_len= 2000 repeating substring len= 2 repeat_naive 0.0004673546463893696 found? True repeat_hash1 0.0003990671853882199 found? True repeat_hash2 2.6841314150743284e-05 found? True >>> ================================ RESTART ================================ >>> str_len= 2000 repeating substring len= 2 repeat_naive 0.0005159058469855626 found? True repeat_hash1 0.0005139322209450677 found? True repeat_hash2 4.1051421642308156e-05 found? True >>> ================================ RESTART ================================ >>> str_len= 2000 repeating substring len= 2 repeat_naive 0.0009189202844547739 found? True repeat_hash1 0.0005190636486503558 found? True repeat_hash2 5.0130101428590146e-05 found? True >>> ================================ RESTART ================================ >>> str_len= 4000 repeating substring len= 2 repeat_naive 0.00037341004686177674 found? True repeat_hash1 0.0009169466584142763 found? True repeat_hash2 4.144614685040737e-05 found? True >>> ================================ RESTART ================================ >>> str_len= 4000 repeating substring len= 2 repeat_naive 0.00024038765173237 found? True repeat_hash1 0.0013014090111028304 found? True repeat_hash2 6.631383496065457e-05 found? True >>> ================================ RESTART ================================ #The effect of table size (when repeat_hash1 is used) --- more details in the pdf str_len= 1000 repeating substring len= 10 0.033428093698291 found? False table size= 1 0.004152114463994744 found? False table size= 10 0.0023628250956813854 found? False table size= 100 0.00239242948628883 found? False table size= 1000 0.0026872892167388723 found? False table size= 1500 0.0041497461127461555 found? False table size= 10000 0.02393376826788264 found? False table size= 100000 >>> ================================ RESTART ================================ >>> str_len= 1000 repeating substring len= 10 0.03902095517184757 found? False table size= 1 0.004150535563162347 found? False table size= 10 0.0023849297073349346 found? False table size= 100 0.0023888769594159337 found? False table size= 1000 0.00237585102754867 found? False table size= 1500 0.004294215538910434 found? False table size= 10000 0.02405100165468807 found? False table size= 100000 #iterators and generators >>> l = [1,2,3] >>> type(l) >>> li = iter(l) >>> 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 >>> next(li) Traceback (most recent call last): File "", line 1, in next(li) StopIteration >>> li = iter(l) >>> for item in l: print(item) 1 2 3 >>> li = iter(l) >>> next(li) 1 >>> for item in li: print(item) 2 3 >>> next(li) Traceback (most recent call last): File "", line 1, in next(li) StopIteration >>> #Creating a generator using a generator function >>> type(countdown_gen) >>> cd = countdown_gen() >>> type(cd) >>> next(cd) 5 >>> next(cd) michal 4 >>> next(cd) 3 >>> next(cd) 2 >>> >>> next(cd) 1 >>> next(cd) 'launch' >>> next(cd) Traceback (most recent call last): File "", line 1, in next(cd) StopIteration >>> cd = countdown_gen() >>> next(cd) 5 >>> cd2 = countdown_gen() >>> next(cd2) 5 >>> next(cd2) michal 4 >>> print(cd) >>> for item in cd2: print(item) 3 2 1 launch >>> >>> cd = countdown_gen() >>> for item in cd: print(item) 5 michal 4 3 2 1 launch >>> cd = countdown_gen() >>> for item in cd: x = 1 michal >>> ================================ RESTART ================================ >>> >>> l = Evens_list(10**8) >>> for x in l: pass >>> del l >>> l = Evens_gen(10**8) >>> for x in l: pass >>> del l >>> type(Evens_gen2) >>> g = Evens_gen2(10) >>> type(g) >>> #An infinite generator, generating all evens natural numbers >>> def all_evens_gen(): i = 0 while True: yield i i+=2