codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#!/usr/bin/env python import itertools from math import log def erat2(): D = {} yield 2 for q in itertools.islice(itertools.count(3), 0, None, 2): p = D.pop(q, None) if p is None: D[q * q] = q yield q else: x = p + q while x in D or not (x & 1): x += p D[x] = p # Inefficient, but not the point of the exercise def next_prime(p): e = erat2() x = e.next() while x <= p: x = e.next() return x def ilog2(x): return int(log(x, 2)) def string_hash(s, x): return reduce(lambda h, c: h * x + ord(c), s, 0) class CuckooTable(dict): def __init__(self, max_size=25, x1=31, x2=37): self.max_probes = max(2 * ilog2(max_size), 20) self.table_size = next_prime(2 * max_size) self.x1 = x1 self.x2 = x2 return None def __repr__(self): r = "Cuckoo Table:\nx1 = %d\nx2 = %d\n" % (self.x1, self.x2) r += dict.__repr__(self) return r def resetMultipliers(self): self.x1 = next_prime(self.x1) self.x2 = next_prime(self.x2) return None def keyHash(self, key, x): return string_hash(key, x) % self.table_size def lookup(self, key): for x in (self.x1, self.x2): h = self.keyHash(key, x) if self.get(h) and self[h][0] == key: return self[h] return None def insert(self, key, value): if self.lookup(key): h1, h2 = self.keyHash(key, self.x1), self.keyHash(key, self.x2) if self.get(h1) and self[h1][0] == key: self[h1] = (key, value) else: self[h2] = (key, value) else: k, v, c = key, value, self.max_probes while c > 0: h1, h2 = self.keyHash(k, self.x1), self.keyHash(k, self.x2) if not self.get(h1): self[h1] = (k, v) break elif not self.get(h2): self[h2] = (k, v) break else: t = self[h1] self[h1] = (k, v) k, v, c = t[0], t[1], c - 1 if c == 0: self.rehash() self.insert(k, v) return None def rehash(self): self.resetMultipliers() _newTable = self.copy() self.clear() for item in _newTable.itervalues(): self.insert(item[0], item[1]) return None def delete(self, key): for x in (self.x1, self.x2): h = self.keyHash(key, x) if self.get(h) and self[h][0] == key: self.pop(h) return None def enlist(self): return sorted(self.items()) # Do we even require sorted order? words = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel", "india", "juliet", "kilo", "lima", "mike", "november", "oscar", "papa", "quebec", "romeo", "sierra", "tango", "uniform", "victor", "whiskey", "xray", "yankee", "zulu"] def cuckoo_test(): t = CuckooTable() print t.lookup("praxis") is None for val in xrange(len(words)): t.insert(words[val], val + 1) print t.lookup("praxis") is None print t.lookup("papa") t.delete("papa") print t.lookup("papa") is None return None if __name__ == "__main__": cuckoo_test()
Private
[
?
]
Run code
Submit