Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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()
share|improve this question

1 Answer 1

General thoughts:

  1. You are abusing lists. If you are passing around two elements you are almost certainly better off just to pass around two parameters. Keeping them as lists just confuses the whole question.
  2. You seem to like short variable names. Don't. Use variable names that give enough information about what they are doing.
  3. Your classes are sparse, and your other code does a lot of work. More code should be in your classes

More details:

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] 

Putting the definition of the function on the same line makes your code harder to read

def __str__(self): return " Interval " + str(self.interval) + "%%" 

Its considered bad form to refer to attributes which nothing in your class defines. You should at least assign interval a value of None in the constructor. Or better yet, pass the correct interva to the constructor

class ref_ll:

The python style guide recommends CamelCase for class names.

    def __init__(self,q = [False,False]): self.xy = list(q)

Using a list to hold two values like this is frowned upon. A list is for well, lists. The data here should either be attributes or a tuple.

    def __mul__(self,y): return ref_ll([ x ^ z for x,z in zip(self.xy,y)])

Since self.xy is only two elements, its probably slower to use a list comprehension here.

    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)

Python has a higher overhead for creating a class like this. All of the operations on this class will be considerably slower then if you were operating on tuples. Since the only thing your class does is provide a muliplication operator, I'd remove this class and put that multiplication in a function.

def point(interval): return True if interval[0] == interval[1] else False

Use return interval[0] == interval[1] otherwise you are abusing explicit bools. Secondly I have no idea how point relates to what this function is doing.

class q_list:
    def __init__(self,lis): self.quad = lis

I recommend against abbreviations like lis. Find a better name.

    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)

To duplicate a list use self.quad[:]

        if parameter[0]:
            df = list(reversed(df))

Use df.reverse()

        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])

Split that up across several lines. As it stands: really hard to follow. Additionally, since it doesn't use self, should it a method?

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

Instead of repeating this, move it up above.

    q = interval[0] + interval[1]
    q = q/2

Combine those two lines

    node.l = build_tree(lis,[interval[0],q])
    node.r = build_tree(lis,[q+1,interval[1]])

l and r are poor choices of name, use left and right

    node.quadrant = node.l.quadrant + node.r.quadrant  
    return node

This whole function should probably be put as the constructor for 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

Doing this only serves to confuse.

    N = int(raw_input())
    lis = []
    for x in xrange(N):
        lis.append([int(y) for y in str(raw_input()).split()])

raw_input() already produces a string, don't pass the result to str.

    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])

Instead do mode, start, stop = y and use the names of the variables. Your code will be easier to read that way.

        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()

If you should do:

if name == 'main': go()

That way other code can import this module if need be.

share|improve this answer
    
Thanks for the comprehensive review, need to make a lot of changes. Could you perhaps tell me why its taking such a large running time? –  elricL Sep 12 '11 at 15:49
    
@ericL, some of my points will help with performance. But I suspect that in query, doing if interval == self.interval isn't correct. I think you end up heading down multiple branches at the same time more then you need to. –  Winston Ewert Sep 12 '11 at 17:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.