tag:blogger.com,1999:blog-34049079038124754312024-03-13T12:51:29.345-04:00CSC148 Stuff by Cem YildirimUnknownnoreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3404907903812475431.post-80663789388123477692014-03-28T22:45:00.002-04:002014-04-01T12:39:40.947-04:00An Alternative Approach to Assignment 2As we all know, second part of assignment 2 was a total pain to code and especially, debug. After implementing the all_regex_permutations part by simply permuting the given string and checking whether each permutation is valid or not, I decided to try a different approach to make it faster since this implementation fails to complete in a sensible amount of time after a string which is longer than 12 characters is given as input. The first idea in my mind was to construct a really basic regex tree out of the given string and then permute the tree itself to get every possible variation of the regex. So my first attempt looked like this:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">all_regex_permutations</span><span style="color: #f8f8f2;">(s):</span>
<span style="color: #e6db74;">'''</span>
<span style="color: #e6db74;"> Return a SET of valid regex permutations of s</span>
<span style="color: #e6db74;"> >>> all_regex_permutations('(1|0)')</span>
<span style="color: #e6db74;"> {'(1|0)','(0|1)'}</span>
<span style="color: #e6db74;"> >>> all_regex_permutations('((01.))|e')</span>
<span style="color: #e6db74;"> {'(1|(e.0))', '(0.(e|1))', '((1|e).0)', '(e.(0|1))', '(e|(0.1))', '((0|1).e)', '(0|(1.e))', '(1|(0.e))', '(e|(1.0))', '((1.e)|0)', '(0.(1|e))', '((e|1).0)', '(e.(1|0))', '((e|0).1)', '((1|0).e)', '(1.(0|e))', '((0|e).1)', '((0.1)|e)', '((e.1)|0)', '((0.e)|1)', '(0|(e.1))', '(1.(e|0))', '((e.0)|1)', '((1.0)|e)'}</span>
<span style="color: #e6db74;"> '''</span>
<span style="color: #f8f8f2;">starcount</span> <span style="color: #f92672;">=</span> <span style="color: #ae81ff;">0</span>
<span style="color: #f8f8f2;">leaves</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">addperm</span><span style="color: #f8f8f2;">(x,</span> <span style="color: #f8f8f2;">l):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">[l[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">:i]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">[x]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">l[i:]</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(len(l)</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">)]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">perm</span><span style="color: #f8f8f2;">(l):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">len(l)</span> <span style="color: #f92672;">==</span> <span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">[[]]</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">[x</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">y</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">perm(l[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:])</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">x</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">addperm(l[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">y)]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">sampletree</span><span style="color: #f8f8f2;">(_str):</span>
<span style="color: #66d9ef;">if</span><span style="color: #f8f8f2;">((_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">))</span> <span style="color: #f92672;">==</span>
<span style="color: #ae81ff;">2</span> <span style="color: #f92672;">*</span> <span style="color: #f8f8f2;">(_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'.'</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'|'</span><span style="color: #f8f8f2;">))):</span>
<span style="color: #f8f8f2;">tree</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">_str:</span>
<span style="color: #66d9ef;">if</span><span style="color: #f8f8f2;">(_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">]):</span>
<span style="color: #f8f8f2;">leaves</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(_char)</span>
<span style="color: #f8f8f2;">tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(Leaf(</span><span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">))</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'.'</span><span style="color: #f8f8f2;">)):</span>
<span style="color: #f8f8f2;">tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(DotTree(tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">pop(),</span> <span style="color: #f8f8f2;">tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">pop()))</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(_str</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'|'</span><span style="color: #f8f8f2;">)):</span>
<span style="color: #f8f8f2;">tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(BarTree(tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">pop(),</span> <span style="color: #f8f8f2;">tree</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">pop()))</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">len(tree)</span> <span style="color: #f92672;">==</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">tree[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">raise</span> <span style="color: #a6e22e;">ValueError</span><span style="color: #f8f8f2;">()</span>
<span style="color: #66d9ef;">raise</span> <span style="color: #a6e22e;">ValueError</span><span style="color: #f8f8f2;">()</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">tostring</span><span style="color: #f8f8f2;">(r):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">Leaf):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_symbol()</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">StarTree):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">tostring(r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_children()[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">])</span> <span style="color: #f92672;">+</span> <span style="color: #e6db74;">'*'</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">DotTree)</span> <span style="color: #f92672;">or</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">BarTree):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">(</span><span style="color: #e6db74;">'('</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">tostring(r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_children()[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">])</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_symbol()</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">tostring(r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_children()[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">])</span> <span style="color: #f92672;">+</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">)</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">all_tree_permutations</span><span style="color: #f8f8f2;">(r):</span>
<span style="color: #f8f8f2;">permlist</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">Leaf):</span>
<span style="color: #f8f8f2;">permlist</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(r)</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">BarTree)</span> <span style="color: #f92672;">or</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">DotTree):</span>
<span style="color: #f8f8f2;">firstchild</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_children()[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #f8f8f2;">secondchild</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">r</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">get_children()[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_fprm</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">all_tree_permutations(firstchild):</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_sprm</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">all_tree_permutations(secondchild):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">isinstance(r,</span> <span style="color: #f8f8f2;">BarTree):</span>
<span style="color: #f8f8f2;">permlist</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(BarTree(_fprm,</span> <span style="color: #f8f8f2;">_sprm))</span>
<span style="color: #f8f8f2;">permlist</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(BarTree(_sprm,</span> <span style="color: #f8f8f2;">_fprm))</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">permlist</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(DotTree(_fprm,</span> <span style="color: #f8f8f2;">_sprm))</span>
<span style="color: #f8f8f2;">permlist</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(DotTree(_sprm,</span> <span style="color: #f8f8f2;">_fprm))</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">permlist</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">addstars</span><span style="color: #f8f8f2;">(strlst):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_str</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">strlst:</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">index,</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">enumerate(_str):</span>
<span style="color: #66d9ef;">if</span><span style="color: #f8f8f2;">(_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">]):</span>
<span style="color: #f8f8f2;">lst</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(_str[:index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">+</span> <span style="color: #e6db74;">'*'</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">_str[index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:])</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">lst</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">permuteleaves</span><span style="color: #f8f8f2;">(strlst):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_str</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">strlst:</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">permedleaves</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">perm(leaves):</span>
<span style="color: #f8f8f2;">s</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">_str</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">index,</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">enumerate(_str):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">s</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">(s[:index]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">permedleaves</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">pop()</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">s[index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:])</span>
<span style="color: #f8f8f2;">lst</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(s)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">lst</span>
<span style="color: #66d9ef;">while</span> <span style="color: #f8f8f2;">s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(</span><span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">!=</span> <span style="color: #f92672;">-</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">starcount</span> <span style="color: #f92672;">+=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #f8f8f2;">s</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">s[:s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(</span><span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">)]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">s[s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(</span><span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:]</span>
<span style="color: #66d9ef;">try</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">firstree</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">sampletree(s)</span>
<span style="color: #66d9ef;">except</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">set()</span>
<span style="color: #f8f8f2;">strlist</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[tostring(x)</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">x</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">all_tree_permutations(firstree)]</span>
<span style="color: #f8f8f2;">strlist</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">permuteleaves(strlist)</span>
<span style="color: #66d9ef;">while</span> <span style="color: #f8f8f2;">starcount</span> <span style="color: #f92672;">></span> <span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">strlist</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">addstars(strlist)</span>
<span style="color: #f8f8f2;">starcount</span> <span style="color: #f92672;">-=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">set(strlist)</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
To go through the code, addperm and perm methods are there to be used to permute any list or string you throw at them, then we sampletree method which creates a regex tree disregarding every syntax rule you had to use at build_regex_tree and parsing through every string like an insatiable monster that devours any string as a meal and exudes a regex tree. I use sampletree to create my initial regex tree which I then use to permute. We then have the tostring method, it is a really simple methods that gives you a string representation of any regex tree you present. Then we come to the heart of the code, all_tree_permutations method takes a string and then supposedly returns every possible permutation of it by iterating through each permutation of its children. It does not always work as intended and it needs a bit of rethinking. I also have an addstars method which adds stars to every possible place you can put it on. I am using addstars method as it gets rid of loads of complexity on the algorithm if you tried to just parse unary trees, I simply modify the string representation with every possible permutation of stars. Permuteleaves function essentially combines every possible representation of leaves with every other representation of trees therefore completing the problem. When I first drafted the code, I did not feel a need to use a method to permute the leaves since if I could find every possible combination of tree permutations, I would be done with the problem. After a bit of coding and trying a myriad of ways, I simply could not find an easy way to permute trees altogether with their leaves. Permuteleaves method is there for sake of convenience, if you can find a better way to merge two parts, please contact!<br />
<br />
Anyways after fiddling with tree permutations for a while, I could not come up with a 100% complete solution therefore I moved onto another approach. This way, the solution is complete and the code is also a bit easier to follow. The basic idea is to use a variation of the addstars method on the code above to add each operator iteratively. Here is the code:<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">all_regex_permutations</span><span style="color: #f8f8f2;">(s:</span> <span style="color: #f8f8f2;">str)</span> <span style="color: #f92672;">-></span> <span style="color: #f8f8f2;">set:</span>
<span style="color: #e6db74;">'''</span>
<span style="color: #e6db74;"> Return a set of valid regex permutations of s</span>
<span style="color: #e6db74;"> >>> len(all_regex_permutations('(1|0)'))</span>
<span style="color: #e6db74;"> 2</span>
<span style="color: #e6db74;"> >>> len(all_regex_permutations('(0.1*)'))</span>
<span style="color: #e6db74;"> 6</span>
<span style="color: #e6db74;"> >>> len(all_regex_permutations('(0.1*)*'))</span>
<span style="color: #e6db74;"> 12</span>
<span style="color: #e6db74;"> >>> len(all_regex_permutations('((01.))|e'))</span>
<span style="color: #e6db74;"> 24</span>
<span style="color: #e6db74;"> '''</span>
<span style="color: #f8f8f2;">permset</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">set([])</span>
<span style="color: #f8f8f2;">starcount</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">numcharacters</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">len(s)</span>
<span style="color: #f8f8f2;">operatorlist</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">([</span><span style="color: #e6db74;">'.'</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'.'</span><span style="color: #f8f8f2;">))]</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'|'</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">count(</span><span style="color: #e6db74;">'|'</span><span style="color: #f8f8f2;">))])</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">s:</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'.'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'|'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">]:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">permset</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">allperms</span><span style="color: #f8f8f2;">(_str):</span>
<span style="color: #e6db74;">'''Return a generator of all permutations of a string'''</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">len(_str)</span> <span style="color: #f92672;"><=</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">yield</span> <span style="color: #f8f8f2;">_str</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">perm</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">allperms(_str[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:]):</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(len(perm)</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">):</span>
<span style="color: #66d9ef;">yield</span> <span style="color: #f8f8f2;">perm[:i]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">_str[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">:</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">perm[i:]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">addoperator</span><span style="color: #f8f8f2;">(strlst,</span> <span style="color: #f8f8f2;">operator):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_str</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">strlst:</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">index</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">,</span> <span style="color: #f8f8f2;">len(_str)):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">(</span>
<span style="color: #f8f8f2;">_str[index</span> <span style="color: #f92672;">-</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">and</span>
<span style="color: #f8f8f2;">_str[index]</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">]</span>
<span style="color: #f8f8f2;">):</span>
<span style="color: #f8f8f2;">startindex</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">index</span> <span style="color: #f92672;">-</span> <span style="color: #ae81ff;">1</span>
<span style="color: #f8f8f2;">endindex</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[index</span> <span style="color: #f92672;">-</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">while</span> <span style="color: #f8f8f2;">_str[startindex]</span> <span style="color: #f92672;">!=</span> <span style="color: #e6db74;">'('</span> <span style="color: #f92672;">or</span> <span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">!=</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[startindex]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">+=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[startindex]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">-=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">==</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">break</span>
<span style="color: #f8f8f2;">startindex</span> <span style="color: #f92672;">-=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">=</span> <span style="color: #ae81ff;">2</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[index]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">while</span> <span style="color: #f8f8f2;">_str[endindex]</span> <span style="color: #f92672;">!=</span> <span style="color: #e6db74;">')'</span> <span style="color: #f92672;">or</span> <span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">!=</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[endindex]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">+=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">_str[endindex]</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">-=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">balance</span> <span style="color: #f92672;">==</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">break</span>
<span style="color: #f8f8f2;">endindex</span> <span style="color: #f92672;">+=</span> <span style="color: #ae81ff;">1</span>
<span style="color: #f8f8f2;">lst</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(</span>
<span style="color: #f8f8f2;">_str[:startindex]</span> <span style="color: #f92672;">+</span>
<span style="color: #e6db74;">'('</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">_str[startindex:index]</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">operator</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">_str[index:endindex]</span> <span style="color: #f92672;">+</span>
<span style="color: #e6db74;">')'</span> <span style="color: #f92672;">+</span>
<span style="color: #f8f8f2;">_str[endindex:]</span>
<span style="color: #f8f8f2;">)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">lst</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">addstars</span><span style="color: #f8f8f2;">(strlst):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_str</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">strlst:</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">index,</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">enumerate(_str):</span>
<span style="color: #66d9ef;">if</span><span style="color: #f8f8f2;">(_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'0'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'1'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'2'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'e'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">]):</span>
<span style="color: #f8f8f2;">lst</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(_str[:index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">]</span> <span style="color: #f92672;">+</span> <span style="color: #e6db74;">'*'</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">_str[index</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:])</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">lst</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">_char</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">'('</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">')'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'*'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'.'</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">'|'</span><span style="color: #f8f8f2;">]:</span>
<span style="color: #66d9ef;">while</span> <span style="color: #f8f8f2;">s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(_char)</span> <span style="color: #f92672;">!=</span> <span style="color: #f92672;">-</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">s</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">s[:s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(_char)]</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">s[s</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">find(_char)</span> <span style="color: #f92672;">+</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:]</span>
<span style="color: #f8f8f2;">leafperms</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[i</span> <span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">allperms(s)]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">oplist</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">allperms(operatorlist):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">leafperms[:]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">operator</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">oplist:</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">addoperator(lst,</span> <span style="color: #f8f8f2;">operator)</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(starcount):</span>
<span style="color: #f8f8f2;">lst</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">addstars(lst)</span>
<span style="color: #f8f8f2;">permset</span> <span style="color: #f92672;">|=</span> <span style="color: #f8f8f2;">set(lst)</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">permset:</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">numcharacters</span> <span style="color: #f92672;">!=</span> <span style="color: #f8f8f2;">len(i):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">set([])</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">permset</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
In this version I still have a helper method that gives you the permutation of any list or string you throw at it.(Such convenience!) Then we have the main method that does the manual labor. Addoperator function accepts a list of strings and an operator then gives a list of strings in which the given operator is added to every possible part of each string in the list. The way it does this is by checking any possible indexes to insert an operator, and then checking the balance of parentheses to insert its respective opening and closing parentheses.(This part was hell to debug!) Then we still have our addstars method which I described earlier and that's it for helpers. Firstly, code strips the string of all the characters that are not leaves and then permutes them into a list. We iterate through every operator and add these to our permutation of leaves and that's it! I personally like this way so much that I stuck with this code instead working on the previous way to compute permutations, feel free to derive anything that's working from the tree implementation and thanks for reading!Unknownnoreply@blogger.com7tag:blogger.com,1999:blog-3404907903812475431.post-69361064023539709682014-03-22T11:30:00.000-04:002014-03-28T21:54:05.784-04:00Complexity and O(n) Notation<div class="separator" style="clear: both; text-align: center;">
</div>
This week we went through calculating the complexity of a given function and finding its BigOh notation. This is the standard approach to estimate the efficiency of an algorithm. Since computers are quite fast, the problem with efficiency matters only on really large number of items, therefore BigOh notation is used whenever we assume a great number of items are given to the algorithm. In calculus you can think of this as taking the limit of a function as our parameters, called n from now on, approaches infinity. We essentially analyze and compare the growth rate of the algorithms. A great example is actually the two implementations I did of calculating the fibonacci sequence on a previous post. For the normal recursive solution, a simple call to calculate fibonacci(5) was actually running the function 15 extra times.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-y-Nm1sN0Xj4/UzYk9SUsRBI/AAAAAAAAEKk/ShXQk8xMAWg/s1600/Fibonacci.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-y-Nm1sN0Xj4/UzYk9SUsRBI/AAAAAAAAEKk/ShXQk8xMAWg/s1600/Fibonacci.png" height="400" width="640" /></a></div>
<div class="separator" style="clear: both; text-align: center;">
</div>
<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
</div>
As our n gets pretty big, we can see that our recursive fibonacci algorithm would grow exponentially. Its complexity is O(((1+sqrt(5))/2)^n) to be precise and actually that base is the golden ratio! Another implementation that I showed on my previous post was using memoization to store previously calculated sequences so our number of calls would be 8, we nearly cut it in half!<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/-ILWXXADUByo/UzYmLXr30II/AAAAAAAAEKw/MaHOSFYYfG0/s1600/FibonacciMemoization.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/-ILWXXADUByo/UzYmLXr30II/AAAAAAAAEKw/MaHOSFYYfG0/s1600/FibonacciMemoization.png" height="434" width="640" /></a></div>
<br />
As you can see from the illustration above, the memoization method gets rid of the redundant part of the problem and we just have to calculate and store the left part of our call tree. Hope you guys like the illustration I drew! Since we just have to calculate the leftmost branch of the tree to compute the sequence, our complexity becomes only O(n)! Much better eh? <br />
<br />
<br />Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-85227757335890826632014-03-17T20:57:00.000-04:002014-03-28T20:57:58.472-04:00Binary Search TreesThis week we analyzed a specific version of binary trees called the binary search trees. They are quite similar with the addition of a simple rule. Every left child of the root node must have a smaller value than root's value and every right child has a bigger value than root's value. So a simple binary search tree would look like this.<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://encrypt3d.files.wordpress.com/2010/09/nodes-in-binary-search-tree.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://encrypt3d.files.wordpress.com/2010/09/nodes-in-binary-search-tree.png" /></a></div>
<br />
This special version of binary tree has some fascinating properties. For example, to find the smallest or the highest value, you just have to go to leftmost or the rightmost node without even comparing any value! It is also terrific at finding a given value in the tree, hence its name. To find a value, you just compare it to a node starting from the root and then recursively search through left subtree if given value is smaller than node or scour the right subtree if the value is greater!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-7102613797893799682014-03-06T13:32:00.000-05:002014-03-28T17:03:07.279-04:00Yet Another Comparison of Queue ImplementationsThis week we had a lab on which students had to create an implementation of queue with linked lists. As I've done this out of curiosity couple of weeks ago I decided to up the ante in lab! On this post i will compare three different implementations of queues with graphs and timers only using python code and a great plotting library for python called Matplotlib. As I mentioned the native deque class in python as a really fast way to implement queues, I decided to give it a shot! Here are my three Queue classes that I tested:<br />
<br />
Queue using List:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Queue</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">item):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(item)</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">dequeue</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">del</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">front</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">is_empty</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span> <span style="color: #f92672;">==</span> <span style="color: #f8f8f2;">[]</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
Queue using Linked List:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Node</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">data</span><span style="color: #f92672;">=</span><span style="color: #f8f8f2;">None):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">data</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__str__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">str(self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data)</span>
<span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Queue</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">is_empty</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">and</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">False</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">True</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">False</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">True</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__iter__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">dequeue</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next()</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">next</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">and</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">raise</span> <span style="color: #a6e22e;">StopIteration</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">data):</span>
<span style="color: #f8f8f2;">n</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">Node(data)</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">front</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">dequeue()</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">enqueue(a)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
Queue using Deque:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #f92672;">from</span> <span style="color: #f8f8f2;">collections</span> <span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">deque</span>
<span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Queue</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">deque()</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">item):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(item)</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">dequeue</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">popleft()</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">front</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">popleft()</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(a)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">is_empty</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">try</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_deq</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">popleft()</span>
<span style="color: #66d9ef;">except</span> <span style="color: #a6e22e;">IndexError</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">True</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">False</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
Here is the code I used to time, test, compare and graph these three different implementations of Queues:<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">time</span>
<span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">matplotlib.pyplot</span> <span style="color: #f92672;">as</span> <span style="color: #f8f8f2;">plt</span>
<span style="color: #f92672;">from</span> <span style="color: #f8f8f2;">csc148_queue</span> <span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">Queue</span> <span style="color: #66d9ef;">as</span> <span style="color: #f8f8f2;">ListQueue</span>
<span style="color: #f92672;">from</span> <span style="color: #f8f8f2;">csc148_queue_deque</span> <span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">Queue</span> <span style="color: #66d9ef;">as</span> <span style="color: #f8f8f2;">DequeQueue</span>
<span style="color: #f92672;">from</span> <span style="color: #f8f8f2;">csc148_queue_linked_list</span> <span style="color: #f92672;">import</span> <span style="color: #f8f8f2;">Queue</span> <span style="color: #66d9ef;">as</span> <span style="color: #f8f8f2;">LinkedListQueue</span>
<span style="color: #f8f8f2;">factor</span> <span style="color: #f92672;">=</span> <span style="color: #ae81ff;">10000</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">getduple</span><span style="color: #f8f8f2;">(q,</span> <span style="color: #f8f8f2;">iternum):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">range(factor,</span> <span style="color: #f8f8f2;">factor</span> <span style="color: #f92672;">*</span> <span style="color: #f8f8f2;">iternum,</span> <span style="color: #f8f8f2;">factor)</span>
<span style="color: #f8f8f2;">b</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">a:</span>
<span style="color: #f8f8f2;">b</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(time_queue(i,</span> <span style="color: #f8f8f2;">q))</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a,</span> <span style="color: #f8f8f2;">b</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue_dequeue</span><span style="color: #f8f8f2;">(q,</span> <span style="color: #f8f8f2;">howmany):</span>
<span style="color: #e6db74;">"""Enqueue and dequeue 'howmany' items to/from Queue 'q'.</span>
<span style="color: #e6db74;"> """</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(howmany):</span>
<span style="color: #f8f8f2;">q</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">enqueue(</span><span style="color: #ae81ff;">42</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">q</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">dequeue()</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">time_queue</span><span style="color: #f8f8f2;">(n,</span> <span style="color: #f8f8f2;">q):</span>
<span style="color: #e6db74;">"""Return how long it takes to enqueue and dequeue 'm' items to/from a</span>
<span style="color: #e6db74;"> Queue with 'n' items already in it.</span>
<span style="color: #e6db74;"> """</span>
<span style="color: #66d9ef;">for</span> <span style="color: #f8f8f2;">i</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">range(n):</span>
<span style="color: #f8f8f2;">q</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">enqueue(</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">start</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">time</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">time()</span>
<span style="color: #f8f8f2;">enqueue_dequeue(q,</span> <span style="color: #ae81ff;">20000</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">end</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">time</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">time()</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">end</span> <span style="color: #f92672;">-</span> <span style="color: #f8f8f2;">start</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">__name__</span> <span style="color: #f92672;">==</span> <span style="color: #e6db74;">'__main__'</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">firstqueue</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">getduple(ListQueue(),</span> <span style="color: #ae81ff;">12</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">secondqueue</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">getduple(LinkedListQueue(),</span> <span style="color: #ae81ff;">12</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">thirdqueue</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">getduple(DequeQueue(),</span> <span style="color: #ae81ff;">12</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">p1,</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">plot(firstqueue[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">firstqueue[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">color</span><span style="color: #f92672;">=</span><span style="color: #e6db74;">'r'</span><span style="color: #f8f8f2;">,</span> <span style="color: #f8f8f2;">linewidth</span><span style="color: #f92672;">=</span><span style="color: #ae81ff;">2.0</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">p2,</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">plot(secondqueue[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">secondqueue[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">color</span><span style="color: #f92672;">=</span><span style="color: #e6db74;">'b'</span><span style="color: #f8f8f2;">,</span> <span style="color: #f8f8f2;">linewidth</span><span style="color: #f92672;">=</span><span style="color: #ae81ff;">2.0</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">p3,</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">plot(thirdqueue[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">thirdqueue[</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">color</span><span style="color: #f92672;">=</span><span style="color: #e6db74;">'g'</span><span style="color: #f8f8f2;">,</span> <span style="color: #f8f8f2;">linewidth</span><span style="color: #f92672;">=</span><span style="color: #ae81ff;">2.0</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">legend(</span>
<span style="color: #f8f8f2;">[p1,</span> <span style="color: #f8f8f2;">p2,</span> <span style="color: #f8f8f2;">p3],</span> <span style="color: #f8f8f2;">[</span><span style="color: #e6db74;">"List"</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">"LinkedList"</span><span style="color: #f8f8f2;">,</span> <span style="color: #e6db74;">"Deque"</span><span style="color: #f8f8f2;">],</span> <span style="color: #f8f8f2;">loc</span><span style="color: #f92672;">=</span><span style="color: #e6db74;">'upper left'</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">ylabel(</span><span style="color: #e6db74;">'Time'</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">xlabel(</span><span style="color: #e6db74;">'Number of Items'</span><span style="color: #f8f8f2;">)</span>
<span style="color: #f8f8f2;">plt</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">show()</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
After running the code above you get a nice little graph of the time required for these queues against the number of items that are in the queue. Here is a little screenshot with a really high factor of 10000.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://4.bp.blogspot.com/-hEDaFLl13fY/UzXgtiv9rmI/AAAAAAAAEKE/XYjIckglqvg/s1600/figure_1.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://4.bp.blogspot.com/-hEDaFLl13fY/UzXgtiv9rmI/AAAAAAAAEKE/XYjIckglqvg/s1600/figure_1.png" height="439" width="640" /></a></div>
Here is a bit more zoomed in version on the difference between Deque and LinkedList:<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="http://1.bp.blogspot.com/--gcQHhlCCtU/UzXhNfwdqvI/AAAAAAAAEKM/_uqsO01CvLM/s1600/figure_2.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="http://1.bp.blogspot.com/--gcQHhlCCtU/UzXhNfwdqvI/AAAAAAAAEKM/_uqsO01CvLM/s1600/figure_2.png" height="438" width="640" /></a></div>
As we can see, even though the Deque class outperforms LinkedList, the difference in their times is quite small even for relatively big number of items. Their difference in timings is smaller than 0.2 seconds for numbers as large as 110000 items. That's quite impressive!Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-50272366392084870142014-02-15T16:07:00.000-05:002014-03-28T16:15:23.096-04:00TreesThis we started working on trees as our new data structure. The main advantage of trees is whenever you want to represent a system or data with a hierarchy, trees are your main tool to use. To give an example, mathematical expressions are one of the best ways to implement trees with. As each operator we use is comprised of a symbol and with left and right parts, we can use binary trees to represent them while using leaves to symbolize basic numbers. On this example, hierarchy is used to represent the priorities associated with the operations since (2+1)*3 is completely different than 2+(1*3). We also learned to traverse through trees with recursion since iterating through trees despite being doable, is much more lengthy to do.<br />
<br />
Here are some SLOGS that are worth checking out:<br />
http://fatmothinmycode.wordpress.com/<br />
http://donthate148.blogspot.ca/<br />
http://zccompsci.wordpress.com/<br />
http://berkeycolortran.wordpress.com/<a href="https://www.blogger.com/null"> </a>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-32688379022092700912014-02-05T18:48:00.000-05:002014-03-28T15:55:05.986-04:00Recursion and Fibonacci<div>
This week was one of the slowest classes as it was more like a resting period to help students digest recursion. We continued recursion in lectures and Dan showed us how to break problems into smaller parts and simplify so we can solve them using recursion. We also had a lab involving recursions on which we solved some seemingly basic problems. It was a breeze to write the code with recursion otherwise we had to iterate through all the possibilities by using a variant of a for loop. The thing with recursion is, most problems can be solved without it but using recursions is an elegant and artistic way to solve problems as it saves code and coder's time despite being ever so slightly inefficient at times.</div>
<div>
<br /></div>
<div>
To give an example of inefficiency on recursion let's examine finding the fibonacci sequence given the index. You would normally solve this using recursion by having a base case and then modifying our call to the method.</div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;">1
2
3
4</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">fibonacci</span><span style="color: #f8f8f2;">(index):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">index</span> <span style="color: #f92672;"><=</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #ae81ff;">1</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">fibonacci(index</span><span style="color: #f92672;">-</span><span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">fibonacci(index</span><span style="color: #f92672;">-</span><span style="color: #ae81ff;">2</span><span style="color: #f8f8f2;">)</span>
</pre>
</td></tr>
</tbody></table>
</div>
<div>
<br /></div>
<div>
Although the recursive implementation above is elegant, it is not very practical nor efficient. Calculating fibonacci(<i>index</i>)
requires calculating two smaller methods, which in turn
require two additional recursive calls each, and so on until all
branches reach index=1. Hence, the time required to calculate fibonacci(<i>index</i>) is exponential.<br />
<br />
Another way to do it while still using recursion is by a technique called memoization in which, instead of calling each smaller fibonacci method we already calculated, we store them so we can just use the already calculated data instead of going through all the recursion again. This is easily done in python using dictionaries.<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;">1
2
3
4
5</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">fibonacci</span><span style="color: #f8f8f2;">(index):</span>
<span style="color: #f8f8f2;">stored</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">{</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">:</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">,</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">:</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">}</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">(index</span> <span style="color: #f92672;">in</span> <span style="color: #f8f8f2;">stored):</span>
<span style="color: #f8f8f2;">stored[index]</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">fibonacci(index</span> <span style="color: #f92672;">-</span> <span style="color: #ae81ff;">1</span><span style="color: #f8f8f2;">)</span> <span style="color: #f92672;">+</span> <span style="color: #f8f8f2;">fibonacci(index</span> <span style="color: #f92672;">-</span> <span style="color: #ae81ff;">2</span><span style="color: #f8f8f2;">)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">stored[index]</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
In our dictionary we hold the initial values and whenever we need to find a value that is not yet in our dictionary we simply calculate it and add it to our dictionary therefore eliminating the need to ever calculate a value more than once.<br />
<br /></div>
Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-58130992526194594652014-01-28T15:10:00.000-05:002014-03-28T15:53:13.048-04:00Queue Implementation with Linked Lists As requested, here is my implementation of the Queue class with Linked Lists in Python. Although Python is quite a high level language to utilize a data type as simple as a Linked Lists, it still greatly improves the performance of a Queue class which uses lists. I used timequeue.py given in lab 2 to benchmark and compare the both implementations and here are the results:<br />
<br />
-------Linked List Queue--------------------------------<br />
Running time on 10000 items: 0.07587790489196777<br />
Running time on 20000 items: 0.06835103034973145<br />
Running time on 30000 items: 0.07256507873535156<br />
Running time on 40000 items: 0.07469511032104492<br />
Running time on 50000 items: 0.07767081260681152<br />
Running time on 60000 items: 0.09958291053771973<br />
Running time on 70000 items: 0.1073610782623291<br />
Running time on 80000 items: 0.11011409759521484<br />
Running time on 90000 items: 0.07159709930419922<br />
Running time on 100000 items: 0.11853194236755371<br />
----------------- List Queue--------------------------------<br />
Running time on 10000 items: 0.3262810707092285<br />
Running time on 20000 items: 0.6386370658874512<br />
Running time on 30000 items: 0.948969841003418<br />
Running time on 40000 items: 1.2549891471862793<br />
Running time on 50000 items: 1.5696308612823486<br />
Running time on 60000 items: 1.8530290126800537<br />
Running time on 70000 items: 4.520461082458496<br />
Running time on 80000 items: 5.268892049789429<br />
Running time on 90000 items: 5.846363067626953<br />
Running time on 100000 items: 6.589374780654907<br />
<br />
Here is my code for the two cases:<br />
<br />
Linked List Queue:<br />
<br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Node</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">data</span><span style="color: #f92672;">=</span><span style="color: #f8f8f2;">None):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">data</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__str__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">str(self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data)</span>
<span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Queue</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">is_empty</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">and</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">False</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">True</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">False</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">True</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">None</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__iter__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">dequeue</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next()</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">data</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">next</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">and</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span>
<span style="color: #66d9ef;">elif</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">curr</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">raise</span> <span style="color: #a6e22e;">StopIteration</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">data):</span>
<span style="color: #f8f8f2;">n</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">Node(data)</span>
<span style="color: #66d9ef;">if</span> <span style="color: #f92672;">not</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">head</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #66d9ef;">else</span><span style="color: #f8f8f2;">:</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">n</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">tail</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">next</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">front</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">dequeue()</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">enqueue(a)</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
List Queue:<br />
<br />
<div style="background: #272822; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #66d9ef;">class</span> <span style="color: #a6e22e;">Queue</span><span style="color: #f8f8f2;">:</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">__init__</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">[]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">enqueue</span><span style="color: #f8f8f2;">(self,</span> <span style="color: #f8f8f2;">item):</span>
<span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">append(item)</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">dequeue</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #f8f8f2;">a</span> <span style="color: #f92672;">=</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">del</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">a</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">front</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items[</span><span style="color: #ae81ff;">0</span><span style="color: #f8f8f2;">]</span>
<span style="color: #66d9ef;">def</span> <span style="color: #a6e22e;">is_empty</span><span style="color: #f8f8f2;">(self):</span>
<span style="color: #66d9ef;">return</span> <span style="color: #f8f8f2;">self</span><span style="color: #f92672;">.</span><span style="color: #f8f8f2;">_items</span> <span style="color: #f92672;">==</span> <span style="color: #f8f8f2;">[]</span>
</pre>
</td></tr>
</tbody></table>
</div>
<br />
Actually after a bit of research, the best way to use a Queue class would be to take advantage of the deque objects in collections package. I may implement and benchmark it if I ever find the time. For more info: http://docs.python.org/2/library/collections.html#collections.deque<br />
<mytubeelement data="{"bundle":{"label_delimitor":":","percentage":"%","smart_buffer":"Smart Buffer","start_playing_when_buffered":"Start playing when buffered","sound":"Sound","desktop_notification":"Desktop Notification","continuation_on_next_line":"-","loop":"Loop","only_notify":"Only Notify","estimated_time":"Estimated Time","global_preferences":"Global Preferences","no_notification_supported_on_your_browser":"No notification style supported on your browser version","video_buffered":"Video Buffered","buffered":"Buffered","hyphen":"-","buffered_message":"The video has been buffered as requested and is ready to play.","not_supported":"Not Supported","on":"On","off":"Off","click_to_enable_for_this_site":"Click to enable for this site","desktop_notification_denied":"You have denied permission for desktop notification for this site","notification_status_delimitor":";","error":"Error","adblock_interferance_message":"Adblock (or similar extension) is known to interfere with SmartVideo. Please add this url to adblock whitelist.","calculating":"Calculating","waiting":"Waiting","will_start_buffering_when_initialized":"Will start buffering when initialized","will_start_playing_when_initialized":"Will start playing when initialized","completed":"Completed","buffering_stalled":"Buffering is stalled. Will stop.","stopped":"Stopped","hr":"Hr","min":"Min","sec":"Sec","any_moment":"Any Moment","popup_donate_to":"Donate to","extension_id":null},"prefs":{"desktopNotification":true,"soundNotification":true,"logLevel":0,"enable":true,"loop":false,"hidePopup":false,"autoPlay":false,"autoBuffer":false,"autoPlayOnBuffer":false,"autoPlayOnBufferPercentage":42,"autoPlayOnSmartBuffer":true,"quality":"default","fshd":false,"onlyNotification":false,"enableFullScreen":true,"saveBandwidth":false,"hideAnnotations":false,"turnOffPagedBuffering":true}}" event="preferencesUpdated" id="myTubeRelayElementToPage"></mytubeelement><mytubeelement data="{"loadBundle":true}" event="relayPrefs" id="myTubeRelayElementToTab"></mytubeelement>Unknownnoreply@blogger.com0tag:blogger.com,1999:blog-3404907903812475431.post-57083835693300292702014-01-24T00:39:00.000-05:002014-01-27T16:23:40.763-05:00Except This! (Week 3) Exceptions are the bane of every student's programming life. Until this week we only knew just a handful of them which would usually come up every time I ran a code (IndentationError, SyntaxError being the most common ones). Now, we can even create them! By learning how to create them we also started delving into the concepts of inheritance and OOP. This is when the fun begins!<br />
<br /> I also would like to state how I implemented the Stack and Queue classes
for the lab assignment. I basically used a binary tree consisting of
duples as nodes for the Stack class and used linked list to implement
the Queue class which resulted in better performance from the code. I
also used an integer to solve the balanced parenthesis problem we
discussed in class which was more efficient in space usage than a stack.<br />
<br />
If you want more information about the implementations I would gladly send you the code! Til next time!<br />
<br />
<span style="color: white;">Yo check this sudoku solver written in python! http://norvig.com/sudoku.html</span>Unknownnoreply@blogger.com3tag:blogger.com,1999:blog-3404907903812475431.post-61213276144889710872014-01-17T02:31:00.000-05:002014-01-27T16:24:47.639-05:00Initial Post (Week 2) This week we wrapped up lectures on queues and stacks. These data types are quite imperative in computer science discipline and their usage can be found on the simplest of programs, such as executing any recursive function. We implemented these types in Python using an easy but inefficient method that utilizes lists.<br />
<br />
We also tried to write a method that found the size of a stack by only using the stack's methods. Many people found unique solutions which left us in wonder. This showed us the ubiquitous ways a programmer may approach a problem yet each solutions efficiency would still be in question.<br />
<br />
In our first lab we tried to program a word counter that can also show us some statistics about our usage of certain words. Our TA, in his example, implemented it by using dictionaries to hold words and their frequencies. However I wanted to try a different approach so I used a duple list to store words and their frequencies. This approach had some problems that weren't encountered in the dictionary approach. First of all, as duples are immutable, when you encounter the same word again in the same content you just can't update the frequency in the duple. So I sorted my initial list of words before parsing to find frequency for each word by easily iterating over the list until I came up on a new word. Although, I'm not sure about the efficiency of my algorithm it is nice to come up with different approaches every now and then.<br />
<br />
Til next time, take care!<br />
<mytubeelement data="{"bundle":{"label_delimitor":":","percentage":"%","smart_buffer":"Smart Buffer","start_playing_when_buffered":"Start playing when buffered","sound":"Sound","desktop_notification":"Desktop Notification","continuation_on_next_line":"-","loop":"Loop","only_notify":"Only Notify","estimated_time":"Estimated Time","global_preferences":"Global Preferences","no_notification_supported_on_your_browser":"No notification style supported on your browser version","video_buffered":"Video Buffered","buffered":"Buffered","hyphen":"-","buffered_message":"The video has been buffered as requested and is ready to play.","not_supported":"Not Supported","on":"On","off":"Off","click_to_enable_for_this_site":"Click to enable for this site","desktop_notification_denied":"You have denied permission for desktop notification for this site","notification_status_delimitor":";","error":"Error","adblock_interferance_message":"Adblock (or similar extension) is known to interfere with SmartVideo. Please add this url to adblock whitelist.","calculating":"Calculating","waiting":"Waiting","will_start_buffering_when_initialized":"Will start buffering when initialized","will_start_playing_when_initialized":"Will start playing when initialized","completed":"Completed","buffering_stalled":"Buffering is stalled. Will stop.","stopped":"Stopped","hr":"Hr","min":"Min","sec":"Sec","any_moment":"Any Moment","popup_donate_to":"Donate to","extension_id":null},"prefs":{"desktopNotification":true,"soundNotification":true,"logLevel":0,"enable":true,"loop":false,"hidePopup":false,"autoPlay":false,"autoBuffer":false,"autoPlayOnBuffer":false,"autoPlayOnBufferPercentage":42,"autoPlayOnSmartBuffer":true,"quality":"default","fshd":false,"onlyNotification":false,"enableFullScreen":true,"saveBandwidth":false,"hideAnnotations":false,"turnOffPagedBuffering":true}}" event="preferencesUpdated" id="myTubeRelayElementToPage"></mytubeelement><mytubeelement data="{"loadBundle":true}" event="relayPrefs" id="myTubeRelayElementToTab"></mytubeelement>Unknownnoreply@blogger.com0