Python追加性能

Question

我在Python中使用'append'有一些性能问题.我正在编写一种算法来检查(大)圆圈中是否有两个重叠的圆圈.我首先将圆圈的极点(x_i-R_i和x_i + R_i)放在一个列表中,然后对列表进行排序.

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

在我之间生成N个随机圆圈并将它们放在"圆圈"列表中.

"""
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

使用50k圆圈运行时,生成列表需要75秒.正如您在我写的评论中所看到的那样,我禁用了垃圾收集,将其放在一个单独的函数中使用

append = list.append
append(foo)

而不仅仅是

list.append(foo)

我禁用了gc,因为经过一些搜索似乎有一个python的错误导致追加运行在O(n)而不是O(c)时间.

那么这种方式是最快的方式还是有办法让这种运行更快？任何帮助是极大的赞赏.

Answer 1

代替

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

使用

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

这可以将你的O(n ^ 2)减少到O(n).

你的整体makeList可以写成:

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

Answer 2

你的性能问题不是在append()方法中,而是在你的使用中circles.index(),这使整个事情O(n ^ 2).

另一个(相对较小的)改进是使用列表理解而不是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)]

请注意,这将以不同的顺序提供数据(这无关紧要,因为您计划对其进行排序).

Answer 3

我刚刚尝试了几次测试来提高“附加”函数的速度。这绝对会对你有帮助。

1. 使用Python
2. 使用 list(map(lambda - 被称为比 for+append 更快一点的方法
3. 使用 Cython
4. 使用 Numba - jit

代码内容：获取 0 ~ 9999999 之间的数字，将它们平方，然后使用追加将它们放入新列表中。

1. 使用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))
   

运行时间：3.7 秒

2. 使用列表（映射（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))
   

运行时间：3.6 秒

3. 使用 Cython

   • .pyx 文件中的编码

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

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

我编译了它并在 .py 文件中运行它。

• 在 .py 文件中

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

运行时间：1.6 秒

4. 使用 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))
   

运行时间：0.57 秒

结论 ：

正如您上面提到的，更改简单的附加形式可以稍微提高速度。使用 Cython 比使用 Python 快得多。然而，事实证明使用 Numba 是提高“for+append”速度的最佳选择！