Python adds performance

Question

I'm having trouble adding in Python. I am writing an algorithm that checks for the presence of two overlapping circles in a (large) set of circles. I start by placing the extreme points of the circles (x_i-R_i and x_i + R_i) in the list, and then sorting the list.

class Circle: def __init__(self, middle, radius): self.m = middle self.r = radius 

In the span, I generate N random circles and put them on the list of circles.

 """ Makes a list with all the extreme points of the circles. Format = [Extreme, left/right ~ 0/1 extreme, index] Seperate function for performance reason, python handles local variables faster. Garbage collect is temporarily disabled since a bug in Python makes list.append run in O(n) time instead of O(1) """ def makeList(): """gc.disable()""" list = [] append = list.append for circle in circles: append([circle.m[0]-circle.r, 0, circles.index(circle)]) append([circle.m[0] + circle.r, 1, circles.index(circle)]) """gc.enable()""" return list 

When doing this with 50k circles, it takes more than 75 seconds to create a list. As you can see in the comments, I wrote that I turned off garbage collection, put it in a separate function, used

 append = list.append append(foo) 

instead

 list.append(foo) 

I turned off gc, as after some searching, it seems that there is an error starting python so that the application runs in O (n) instead of O (c).

So is this the fastest way or is there a way to make this run faster? Any help is appreciated.

Answer 1

Instead

 for circle in circles: ... circles.index(circle) ... 

using

 for i, circle in enumerate(circles): ... i ... 

This can reduce your O (n ^ 2) to O (n).

Your entire makeList can be written as:

 sum([[[circle.m[0]-circle.r, 0, i], [circle.m[0]+circle.r, 1, i]] for i, circle in enumerate(circles)], []) 

Answer 2

The performance problem is not in the append() method, but when using circles.index() , which does the whole thing O (n ^ 2).

A further (relatively minor) improvement is to use list comprehension instead of list.append() :

 mylist = [[circle.m[0] - circle.r, 0, i] for i, circle in enumerate(circles)] mylist += [[circle.m[0] + circle.r, 1, i] for i, circle in enumerate(circles)] 

Please note that this will give the data in a different order (which does not matter, since you plan to sort it anyway).

Answer 3

If performance was a problem, I would not use append. Instead, predefine the array, and then fill it. I would also avoid using the index to find a position in the circles list. Corresponding here. It is not compact, but I will bet quickly because of the deployed cycle.

 def makeList(): """gc.disable()""" mylist = 6*len(circles)*[None] for i in range(len(circles)): j = 6*i mylist[j] = circles[i].m[0]-circles[i].r mylist[j+1] = 0 mylist[j+2] = i mylist[j+3] = circles[i].m[0] + circles[i].r mylist[j+4] = 1 mylist[j+5] = i return mylist 

Answer 4

I just tried some tests to improve the speed of the application. It will definitely help you.

• Using Python
• Using a list (map (lambda - known as bit means faster than for + append
• Using cython
• Using Numba - jit

CODE CONTENT: getting numbers from 0 ~ 9999999, squaring them and adding them to a new list by adding.

• Using Python

   import timeit st1 = timeit.default_timer() def f1(): a = range(0, 10000000) result = [] append = result.append for i in a: append( i**2 ) return result f1() st2 = timeit.default_timer() print("RUN TIME : {0}".format(st2-st1)) 

OPERATION TIME: 3.7 s

2. Using a list (map (lambda

    import timeit st1 = timeit.default_timer() result = list(map(lambda x : x**2 , range(0,10000000) )) st2 = timeit.default_timer() print("RUN TIME : {0}".format(st2-st1)) 

OPERATION TIME: 3.6 s

3. Using cython

   • encoding in a .pyx file

     def f1 (): cpdef double i a = range (0, 10000000)

      result = [] append = result.append for i in a: append( i**2 ) return result 

and I compiled it and ran it in a .py file.

• in .py file

   import timeit from c1 import * st1 = timeit.default_timer() f1() st2 = timeit.default_timer() print("RUN TIME : {0}".format(st2-st1)) 

OPERATION TIME: 1.6 s

4. Using Numba - jit

    import timeit from numba import jit st1 = timeit.default_timer() @jit(nopython=True, cache=True) def f1(): a = range(0, 10000000) result = [] append = result.append for i in a: append( i**2 ) return result f1() st2 = timeit.default_timer() print("RUN TIME : {0}".format(st2-st1)) 

OPERATION TIME: 0.57 s

CONCLUSION:

As you mentioned above, changing the simple form of append speed up a bit. And using Cython is much faster than in Python. However, it turned out that Numba is the best choice in terms of increasing speed for "for + add"!