Skip to content

Commit 3b3e15c

Browse files
heinemanheineman
committed
initial upload of code
1 parent e885b58 commit 3b3e15c

64 files changed

Lines changed: 36885 additions & 0 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎1. Fundamentals/README.txt‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
Module 1 Fundamentals
2+
3+
Change Log
4+

‎1. Fundamentals/bigO.py‎

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
"""
2+
Demonstrate O(n) behavior of simple for loop.
3+
4+
Author: George Heineman
5+
"""
6+
import random
7+
import timeit
8+
9+
print ('N\tSum Time')
10+
for trial in [2**_ for _ in range(1,9)]:
11+
numbers = [random.randint(1,9) for _ in range(trial)]
12+
m = timeit.timeit(stmt='sum = 0\nfor d in numbers:\n\tsum = sum + d',
13+
setup='import random\nnumbers = ' + str(numbers))
14+
print ('{0:d}\t{1:f}'.format(trial, m))
15+
16+
17+
"""
18+
Sample Output:
19+
20+
N Sum Time
21+
2 0.266628
22+
4 0.386807
23+
8 0.647032
24+
16 1.156006
25+
32 2.163258
26+
64 4.586453
27+
128 9.979934
28+
256 20.174862
29+
"""

‎1. Fundamentals/bigOduplicate.py‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
"""
2+
Demonstrate O(n) behavior with O(n) storage for determining whether
3+
list contains duplicate values
4+
5+
Shows alternate implementation with O(n^2) behavior with O(1) storage
6+
to solve same problem
7+
8+
Author: George Heineman
9+
"""
10+
import random
11+
import timeit
12+
13+
def uniqueCheckFast(aList):
14+
"""
15+
Return True if aList contains any duplicates. Its contents are not
16+
altered and completes in O(n) time with O(n) space required. The
17+
individual elements must be hashable.
18+
"""
19+
check = set()
20+
for v in aList:
21+
if v in check:
22+
return True
23+
check.add(v)
24+
return False
25+
26+
def uniqueCheckSlow(aList):
27+
"""
28+
Return True if aList contains any duplicates. Its contents are not
29+
altered and completes in O(n^2) time with no space required.
30+
"""
31+
for i in range(len(aList)-1):
32+
for j in range(i+1, len(aList)):
33+
if aList[i] == aList[j]:
34+
return True
35+
return False
36+
37+
print ('N\tSlow \tFast')
38+
for trial in [2**_ for _ in range(1,10)]:
39+
numbers = [random.random() for _ in range(trial)]
40+
mSlow = timeit.timeit(stmt='uniqueCheckSlow(numbers)',
41+
setup='import random\nfrom __main__ import uniqueCheckSlow\nnumbers = ' + str(numbers),
42+
number=1000)
43+
mFast = timeit.timeit(stmt='uniqueCheckFast(numbers)',
44+
setup='import random\nfrom __main__ import uniqueCheckFast\nnumbers = ' + str(numbers),
45+
number=1000)
46+
47+
print ('{0:d}\t{1:f}\t{2:f}'.format(trial, mSlow, mFast))
48+
49+
50+
"""
51+
Sample Output:
52+
53+
N Slow Fast
54+
2 0.001619 0.001241
55+
4 0.003531 0.001805
56+
8 0.009362 0.003077
57+
16 0.030581 0.006073
58+
32 0.098761 0.011974
59+
64 0.338519 0.020638
60+
128 1.276854 0.043545
61+
256 4.887293 0.080524
62+
512 22.114716 0.173997
63+
"""

‎2. Ubiquitous Lists/README.txt‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
Module 1 Fundamentals
2+
3+
Change Log
4+
----------
5+
2015.07.30 cleaned up movingAverage implementation of add
6+

‎2. Ubiquitous Lists/circBuffer.py‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
"""
2+
Implementation of a circular buffer of fixed storage size.
3+
4+
Author: George Heineman
5+
"""
6+
class CircularBuffer:
7+
8+
def __init__(self, size):
9+
"""Store buffer in given storage."""
10+
self.buffer = [None]*size
11+
self.low = 0
12+
self.high = 0
13+
self.size = size
14+
self.count = 0
15+
16+
def isEmpty(self):
17+
"""Determines if buffer is empty."""
18+
return self.count == 0
19+
20+
def isFull(self):
21+
"""Determines if buffer is full."""
22+
return self.count == self.size
23+
24+
def __len__(self):
25+
"""Returns number of elements in buffer."""
26+
return self.count
27+
28+
def add(self, value):
29+
"""Adds value to buffer, overwrite as needed."""
30+
if self.isFull():
31+
self.low = (self.low+1) % self.size
32+
else:
33+
self.count += 1
34+
self.buffer[self.high] = value
35+
self.high = (self.high + 1) % self.size
36+
37+
def remove(self):
38+
"""Removes oldest value from non-empty buffer."""
39+
if self.count == 0:
40+
raise Exception ("Circular Buffer is empty");
41+
value = self.buffer[self.low]
42+
self.low = (self.low + 1) % self.size
43+
self.count -= 1
44+
return value
45+
46+
def __iter__(self):
47+
"""Return elements in the circular buffer in order using iterator."""
48+
idx = self.low
49+
num = self.count
50+
while num > 0:
51+
yield self.buffer[idx]
52+
idx = (idx + 1) % self.size
53+
num -= 1
54+
55+
def __repr__(self):
56+
"""String representation of circular buffer."""
57+
if self.isEmpty():
58+
return 'cb:[]'
59+
60+
return 'cb:[' + ','.join(map(str,self)) + ']'

‎2. Ubiquitous Lists/fibonacci.py‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
"""
2+
Fibonacci series as list.
3+
4+
Author: George Heineman
5+
"""
6+
def fibonacci(n):
7+
"""Return first n>=2 elements of fibonacci as list."""
8+
a = b = 1
9+
result = [a, b]
10+
while n > 2:
11+
n = n - 1
12+
a,b = b,a+b
13+
result.append(b)
14+
return result
15+
16+
def fibonacciGenerator(n):
17+
"""Return first n>=2 elements of fibonacci as generator."""
18+
a = b = 1
19+
yield a
20+
yield b
21+
while n > 2:
22+
n = n - 1
23+
a,b = b,a+b
24+
yield b
25+
26+
27+
28+
"""
29+
Sample Output:
30+
31+
>>> fibonacci(7)
32+
[1, 1, 2, 3, 5, 8, 13]
33+
>>> for _ in fibonacciGenerator(5):
34+
print (_)
35+
36+
1
37+
1
38+
2
39+
3
40+
5
41+
42+
"""
43+

‎2. Ubiquitous Lists/movingAverage.py‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
"""
2+
Implementation of a moving average by extending CircularBuffer.
3+
4+
Author: George Heineman
5+
"""
6+
from circBuffer import CircularBuffer
7+
8+
class MovingAverage(CircularBuffer):
9+
10+
def __init__(self, size):
11+
"""Store buffer in given storage."""
12+
CircularBuffer.__init__(self, size)
13+
self.total = 0
14+
15+
def getAverage(self):
16+
"""Returns moving average (zero if no elements)."""
17+
if self.count == 0:
18+
return 0
19+
return self.total/self.count
20+
21+
def remove(self):
22+
"""Removes oldest value from non-empty buffer."""
23+
removed = CircularBuffer.remove(self)
24+
self.total -= removed
25+
return removed
26+
27+
def add(self, value):
28+
"""Adds value to buffer, overwrite as needed."""
29+
if self.isFull():
30+
self.total -= self.buffer[self.low]
31+
32+
self.total += value
33+
CircularBuffer.add(self,value)
34+
35+
def __repr__(self):
36+
"""String representation of moving average."""
37+
if self.isEmpty():
38+
return 'ma:[]'
39+
40+
return 'ma:[' + ','.join(map(str,self)) + ']:' + str(self.getAverage())
41+
42+
"""
43+
Change Log
44+
----------
45+
2015.07.30 simplified add() function by eliminating delta
46+
"""

‎2. Ubiquitous Lists/naiveBuffer.py‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
"""
2+
Implementation of a naive buffer of limited storage size.
3+
4+
Author: George Heineman
5+
"""
6+
class NaiveBuffer:
7+
8+
def __init__(self, size):
9+
"""Store buffer in given storage."""
10+
self.buffer = []
11+
self.size = size
12+
13+
def __len__(self):
14+
"""Return number of elements"""
15+
return len(self.buffer)
16+
17+
def isEmpty(self):
18+
"""Determines if buffer is empty."""
19+
return len(self.buffer) == 0
20+
21+
def isFull(self):
22+
"""Determines if buffer is full."""
23+
return len(self.buffer) == self.size
24+
25+
def count(self):
26+
"""Returns number of elements in buffer."""
27+
return len(self.buffer)
28+
29+
def add(self, value):
30+
"""Adds value to non-full buffer."""
31+
if len(self.buffer) == self.size:
32+
del self.buffer[0]
33+
self.buffer.append(value)
34+
35+
def remove(self):
36+
"""Removes oldest value from non-empty buffer."""
37+
value = self.buffer[0]
38+
del self.buffer[0]
39+
return value
40+
41+
def __iter__(self):
42+
"""Return elements in the circular buffer in order using iterator."""
43+
for _ in self.buffer:
44+
yield _
45+
46+
def __repr__(self):
47+
"""String representation of circular buffer."""
48+
return str(self.buffer)
49+

‎2. Ubiquitous Lists/projectStatistics.py‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
"""
2+
Implementation of a moving statistics by extending CircularBuffer.
3+
This computes Standard deviation in the same way that MovingAverage
4+
is computed.
5+
"""
6+
from circBuffer import CircularBuffer
7+
8+
class Statistics(CircularBuffer):
9+
10+
def __init__(self, size):
11+
"""Store buffer in given storage."""
12+
CircularBuffer.__init__(self, size)
13+
self.total = 0
14+
self.sumSq = 0
15+
16+
def getAverage(self):
17+
"""Returns moving average (zero if no elements)."""
18+
if self.count == 0:
19+
return 0
20+
return self.total/self.count
21+
22+
def getStdev(self):
23+
"""Returns moving stdev (zero if fewer than one element)."""
24+
if self.count <= 1:
25+
return 0
26+
var = (self.sumSq - self.total*self.total/self.count)/self.count
27+
return var ** 0.5
28+
29+
def remove(self):
30+
"""Removes oldest value from non-empty buffer."""
31+
removed = CircularBuffer.remove(self)
32+
self.total -= removed
33+
self.sumSq -= removed*removed
34+
return removed
35+
36+
def add(self, value):
37+
"""Adds value to buffer, overwrite as needed."""
38+
if self.isFull():
39+
delta = self.buffer[self.low]
40+
else:
41+
delta = 0
42+
43+
self.total += value - delta
44+
self.sumSq += value*value - delta*delta
45+
CircularBuffer.add(self,value)
46+
47+
def __repr__(self):
48+
"""String representation of moving average."""
49+
if self.isEmpty():
50+
return 'ma:[]'
51+
return 'ma:[{0:s}]:{1:f} {2:f}'.format(','.join(map(str,self)),
52+
self.getAverage(),
53+
self.getStdev())
54+
if __name__ == '__main__':
55+
b = Statistics(5)
56+
for _ in range(10):
57+
b.add(_*_)
58+
print (b)
59+
60+
61+
"""
62+
Sample Output:
63+
64+
ma:[0]:0.000000 0.000000
65+
ma:[0,1]:0.500000 0.500000
66+
ma:[0,1,4]:1.666667 1.699673
67+
ma:[0,1,4,9]:3.500000 3.500000
68+
ma:[0,1,4,9,16]:6.000000 5.899152
69+
ma:[1,4,9,16,25]:11.000000 8.648699
70+
ma:[4,9,16,25,36]:18.000000 11.436783
71+
ma:[9,16,25,36,49]:27.000000 14.240786
72+
ma:[16,25,36,49,64]:38.000000 17.052859
73+
ma:[25,36,49,64,81]:51.000000 19.869575
74+
"""

0 commit comments

Comments
 (0)