Morning Joe: Are Nesting Loop Comprehenders in Python Somehow Faster than Nested Loops?

As I learn more about Python at work, I have come across list comprehension functions and lambdas. The list comprehender format is [x for x in [] if condition] and the lambda format is (lambda x,y: function, x,y). The former seems extremely fast but is it faster than a nested loop when combined in a similar way?

Logic dictates that both will run in O(n^2) time. I performed a basic test on one, two, and four loops using the time module where a list of 100000 integers is created and then an iteration moves down the list, adding a random number to each slot (pretty easy but I need to get to working). Obviously, the third loop is skipped so that the triple nesting actually has an effect.

The programs are run 32 times apiece (CLT numbers), and averaged. The test computer is a Lenovo laptop with a 2.0 ghz dual core processor and 4 gb of RAM. The results are below.

One Loop

    #comprehension
    avg=0
    for i in range(0,32):
        list=[]
        for i in range(0,100000):
            list.append(random.randint(1,1000))
            
        start=time.time()
        list=[x+random.randint(1,100) for x in list]
        avg+=(time.time()-start)
    
    print "Comprehension Avg. Time "+str(avg/32)
    
    #loop
    avg=0
    for i in range(0,32):
        list=[]
        for i in range(0,100000):
            list.append(random.randint(1,1000))
        start=time.time()
        for i in range(0,len(list)):
            list[i]=list[i]+random.randint(1,100)
        avg+=time.time()-start
     
    print "Loop Avg. Time:"+str(avg/32)

Loop Time: .24775519222(seconds)
Comprehension Function Time: .246111199926 (seconds)

Doubly Nested Loop
In the presence of a time constraint, I have only included the loop code. The remaining code remains the same.

     #comprehension
     list=[x+random.randint(1,100) for x in [y+random.randint(1,100) for y in list]]

     #loop
     for i in range(0,2):
            for j in range(0,len(list)):
                list[j]=list[j]+random.randint(1,100)

Loop Time: 0.502061881125 (seconds)
Comprehension Function Time: 0.451432295144 (seconds)

Quadruple Nested Loop

     #comprehension
     list=[x+random.randint(1,100) for x in [y+random.randint(1,100) for y in [z+random.randint(1,100) for z in [a+random.randint(1,100) for a in list]]]]

     #loop
     for i in range(0,2):
            for j in range(0,2):
                for k in range(0,len(list)):
                    list[k]=list[k]+random.randint(1,100)

Loop Time: 1.08803078532 (seconds)
Comprehension Function Time: .951290503144(seconds)

Conclusion
As the time complexity measurements suggest, the time for each goes up with each level of nesting. However, the differences are extremely small. If any one has an advantage, it seems to be the comprehension but that difference is to small to declare a winner. That difference could be due to the random number function or other factors. The slight difference does seem to grow with each loop though. I would perform a more comprehensive test before making any determinations but comprehensions are faster to write anyway.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s