[ create a new paste ] login | about

Link: http://codepad.org/xW4BHzuJ    [ raw code | output | fork ]

gre - Python, pasted on Feb 4:
#!/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()


Output:
1
2
3
4
True
True
('papa', 16)
True


Create a new paste based on this one


Comments: