Fair warning, complete newbie to python, just wanted to implement something in python, Any suggestions welcome. Build tree with 10000 runs in 0.2 sec. Where as 10000 calls of query runs in around 30 sec. Something must me wrong. Build tree takes O(n),where as 10000 queries should take O(n logn). Any help appreciated.
class Node:
def __init__(self): self.xy = ref_ll()
def x(self): self.xy[1] = not self.xy[1]
def y(self): self.xy[0] = not self.xy[0]
def __str__(self): return " Interval " + str(self.interval) + "%%"
class ref_ll:
def __init__(self,q = [False,False]): self.xy = list(q)
def __mul__(self,y): return ref_ll([ x ^ z for x,z in zip(self.xy,y)])
def __iter__(self): return iter(self.xy)
def __getitem__(self,x): return self.xy[x]
def __setitem__(self,x,y): self.xy[x] = y
def __str__(self): return " ".join(self.xy)
def point(interval): return True if interval[0] == interval[1] else False
class q_list:
def __init__(self,lis): self.quad = lis
def __add__(self,y): return q_list([ a + b for a,b in zip(self.quad,y)])
def __iter__(self): return iter(self.quad)
def __str__(self): return " ".join([str(mm) for mm in self.quad])
def reflect(self,parameter):
df = list(self.quad)
if parameter[0]:
df = list(reversed(df))
if parameter[1]:
df[0],df[1] = df[1],df[0]
df[2],df[3] = df[3],df[2]
return q_list(df)
def create_q_list(point):
if point[0] > 0: return q_list([1,0,0,0]) if point[1] > 0 else q_list([0,0,0,1])
else: return q_list([0,1,0,0]) if point[1] > 0 else q_list([0,0,1,0])
def build_tree(lis,interval):
node = Node()
if point(interval):
node.quadrant = create_q_list(lis[interval[0]-1])
node.l = False
node.r = False
node.interval = interval
return node
node.interval = interval
q = interval[0] + interval[1]
q = q/2
node.l = build_tree(lis,[interval[0],q])
node.r = build_tree(lis,[q+1,interval[1]])
node.quadrant = node.l.quadrant + node.r.quadrant
return node
def update(root,axis,interval,xy = [False,False]):
if root.interval == interval or point(root.interval):
return axis(root)
if interval[0] < root.r.interval[0]:
update(root.l,axis,[interval[0],min(interval[1],root.l.interval[1])],(root.l.xy *xy))
if interval[1] > root.l.interval[1]:
update(root.r,axis,[max(interval[0],root.r.interval[0]), interval[1]],(root.r.xy *xy))
root.quadrant = root.l.quadrant.reflect(root.l.xy * xy) + root.r.quadrant.reflect(root.r.xy * xy)
def query(root,interval,xy=ref_ll([False,False])):
#print interval,root
if root.interval == interval or point(root.interval):
return root.quadrant.reflect(root.xy * xy)
a = q_list([0,0,0,0])
if interval[0] < root.r.interval[0]:
a = a + query(root.l,[interval[0],min(interval[1],root.l.interval[1])],root.xy * xy)
if interval[1] > root.l.interval[1]:
a = a + query(root.r,[max(interval[0],root.r.interval[0]), interval[1]],root.xy * xy)
return a
def go():
refx = Node.x
refy = Node.y
N = int(raw_input())
lis = []
for x in xrange(N):
lis.append([int(y) for y in str(raw_input()).split()])
root = build_tree(lis, [1,len(lis)])
N2 = int(raw_input())
for x in xrange(N2):
y = str(raw_input()).split()
y[1],y[2] = int(y[1]),int(y[2])
if y[0] == 'C':
print query(root,[y[1],y[2]])
if y[0] == 'X':
update(root,refy,[y[1],y[2]])
if y[0] == 'Y':
update(root,refx,[y[1],y[2]])
go()