class MyHash(object):
def __init__(self):
self._entries = [None]*37
def calculate_index(key, array):
h = hash(key)
return h % len(array)
hash("this thing") == 482052534689916146
482052534689916146 % 37 == 7
def insert_into_array(key, value, array):
index = calculate_index(key, array)
if array[index] and array[index][0] != key:
return False
array[index] = (key, value)
return True
>>> insert_into_array("this thing", "the value it maps to", my_array)
>>> print my_array[7]
("this thing", "the value it maps to")
def add(self, key, value):
if insert_into_array(key, value, self._entries):
return
#Resize
length = len(self._entries)
while True:
length = length*2+1
if self.resize(length):
break
self.add(key,value)
def resize(self, length):
new_array = [None]*length
for entry in self._entries:
if not entry:
continue
if not insert_into_array(entry[0], entry[1], new_array):
return False
self._entries = new_array
return True
def get(self, key, default=None):
index = calculate_index(key, self._entries)
if self._entries[index] and self._entries[index][0] == key:
return self._entries[index][1]
return default
def member(self, key):
index = calculate_index(key, self._entries)
val = self._entries[index]
return val and val[0] == key
def keys(self):
return [x[0] for x in self._entries if x]
def values(self):
return [x[1] for x in self._entries if x]
def items(self):
return [x for x in self._entries if x]
class MySet(object):
def __init__(self, *args):
self._values = MyHash()
for k in args:
self.add(k)
def add(self, k):
self._values.add(k, None)
def values(self):
return self._values.keys()
def member(self, k):
return self._values.member(k)
def issubset(self, other):
for k in self.values():
if not other.member(k):
return False
return True
a = MySet(1,2,3)
b = MySet(1,2,3,4,5)
assert not b.issubset(a)
assert a.issubset(b)
def intersection(self, other):
rv = MySet()
for k in self.values():
if other.member(k):
rv.add(k)
return rv
a = MySet(1,2,3)
b = MySet(2,3,4,5)
assert a.intersection(b) == MySet(2,3)
def union(self, other):
rv = MySet()
for k in self.values():
rv.add(k)
for k in other.values():
rv.add(k)
return rv
a = MySet(1,2,3,4)
b = MySet(3,4,5,6)
assert a.union(b) == MySet(1,2,3,4,5,6)
def difference(self, other):
rv = MySet()
for k in self.values():
if other.member(k):
continue
rv.add(k)
return rv
a = MySet(1,2,3,4)
b = MySet(2,4,5)
assert a.difference(b) == MySet(1,3)
import random
import collections
def page_rank(g, n, damping_factor=0.85):
rv = collections.Counter()
for _ in range(n):
current = random.choice(g.get_nodes())
while True:
if random.random() > damping_factor:
rv[current] += 1
break
current = random.choice(g.get_edges(current))
return rv
import csv
def import_csv(f):
inp = csv.DictReader(open(f))
g = Graph()
names = {}
def get_or_create(t):
if t not in names:
names[t] = g.add_node(t)
return names[t]
for d in inp:
l = get_or_create(d['Loser/tie'])
w = get_or_create(d['Winner/tie'])
g.add_edge(l,w)
return g, {v:k for k,v in names.items()}