Created
June 13, 2012 07:26
-
-
Save masahi/2922521 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import random | |
import math | |
def sort_by_z_order(a,b): | |
return a.z_value - b.z_value | |
def push_zeros(a, n): | |
if len(a) < n: | |
for i in xrange(n-len(a)): | |
a = '0' + a | |
return a | |
a = '0'*(n-len(a)) + a | |
return a | |
def interleave(a,b): | |
ret = "" | |
for i in range(len(a)): | |
ret = ret + a[i] + b[i] | |
return ret | |
def gen_membership_vector(n): | |
n_digit = int(math.ceil(math.log(n,2))) | |
ret = '' | |
for i in xrange(n_digit): | |
ret += str(random.randint(0,1)) | |
return ret | |
def print_points(points): | |
for p in points: | |
print p.z_value | |
def calc_z_value(x,y, n): | |
s1 = format(x, 'b') | |
s2 = format(y, 'b') | |
s1 = push_zeros(s1, n) | |
s2 = push_zeros(s2,n) | |
bits = interleave(s1, s2) | |
return int(bits, 2), bits | |
class Point(): | |
def __init__(self, x, y): | |
self.pos = (x,y) | |
self.z_value, _ = calc_z_value(x,y,3) | |
class SkipGraph(): | |
class Node(): | |
def __init__(self, key, value): | |
self.key = key | |
self.value = value | |
self.neighbors = [] | |
self.membership_vectors = None | |
def get_prev(self, level): | |
return self.neighbors[level][0] | |
def get_next(self, level): | |
return self.neighbors[level][1] | |
def __init__(self): | |
self.nodes = [] | |
def build(self, points): | |
points.sort(sort_by_z_order) | |
for i, p in enumerate(points): | |
n = Node(p.z_value, p) | |
while True: | |
vec = gen_membership_vector(len(points)) | |
if not vec in vec_set: | |
n.membership_vectors = vec | |
vec_set.add(vec) | |
break | |
self.nodes.append(n) | |
def print_me(self): | |
pass | |
def search(self, key): | |
cand = self.find_nearest_key(key) | |
if cand.key == key: | |
print "Found." | |
return cand | |
else: | |
print "Not found." | |
return None | |
def find_nearest_key(self, key): | |
pass | |
def range_search(self, key1, key2): | |
assert key1 <= key2, "key1 has to be less than key2" | |
start_node = self.find_nearest_key(key1) | |
last_node = self.find_nearest_key(key2) | |
print "(start, end) : (%d, %d)" % (start_node.key, last_node.key) | |
return self._range_search(start_node, last_node, len(self.levels)-1) | |
def _range_search(self, start, end,level): | |
pass | |
def gen_membership_vector(n): | |
n_digit = int(math.ceil(math.log(n,2))) | |
ret = '' | |
for i in xrange(n_digit): | |
ret += str(random.randint(0,1)) | |
return ret | |
def print_points(points): | |
for p in points: | |
print (p.pos[0], p.pos[1]), | |
def gen_points(num): | |
c, n = 0,num | |
points = [] | |
used = set() | |
while c < n : | |
x = random.randint(0,7) | |
y = random.randint(x, 7) | |
p = Point(x,y) | |
if (x,y) not in used: | |
points.append(p) | |
used.add((x,y)) | |
c += 1 | |
return points | |
def test_nearest(): | |
points = gen_points(10) | |
print "Point being queryed: " | |
print_points(points) | |
print "Building Skip Graph ..." | |
skgraph = SkipGraph() | |
skgraph.build(points) | |
print "Skip Graph built." | |
skgraph.print_me() | |
while True: | |
print "Give me a key:", | |
key = int(raw_input()) | |
print "Search for a key %d" % key | |
cand = skgraph.find_nearest_key(key) | |
if cand.key == key: | |
print "Found %d." % cand.key | |
else: | |
print "Nearest key %d. " % cand.key | |
def test_range(): | |
points = gen_points(10) | |
print "Point being queryed: " | |
print_points(points) | |
print "Building Skip Graph ..." | |
skgraph = SkipGraph() | |
skgraph.build(points) | |
print "Skip Graph built." | |
skgraph.print_me() | |
print "Give me two keys:", | |
line = raw_input() | |
key1, key2 = line.strip().split() | |
key1, key2 = int(key1), int(key2) | |
print "Range search with %d <= key <= %d " % (key1, key2) | |
skgraph.range_search(key1, key2) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment