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个随机圆并将它们放入“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

当使用50k个圆运行此代码时，需要超过75秒才能生成列表。正如您在我写的评论中所看到的那样，我禁用了垃圾收集器，将其放在一个单独的函数中，使用了...

append = list.append
append(foo)

不仅仅是

list.append(foo)

我禁用了垃圾收集器，因为经过一些搜索发现 Python 存在一个 bug，导致 append 方法的运行时间变成 O(n) 而不是 O(c)。

那么这种方式是最快的方式吗？还是有其他方法可以使其运行更快呢？任何帮助都将不胜感激。

- Harm De Weirdt

---

在Python中，list不是一个好的变量名。 - eumiro

在任何编程语言中，“list”都不是一个好的变量名称。 - Gordon Gustafson

"""字符串字面值"""不是#注释。文档字符串必须放在函数内部，而不是函数前面。 - Sven Marnach

@eumiro，CrazyJugglerDrummer: true已更改为cirkeList。@Sven：我还不习惯Python的注释方式，但我会记住你的建议。 - Harm De Weirdt

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

- eumiro

---

@Harm 这是很好的建议 - 你也应该考虑使用双端队列（见collections模块），因为它据说在附加操作方面具有略微更好的性能。但你最后可能想将其转换为列表，所以节省的时间可能不会超过开销。 - theheadofabroom

啊，我一直在看错东西...感谢你的回答 :) 能否解释一下为什么获取圆的索引的时间复杂度是O(N²)？如果是O(n)，我会理解的，因为在列表中获取对象的索引等价于线性搜索列表，直到找到该对象。 - Harm De Weirdt

@Harm：线性搜索在每个for循环的n次迭代中完成，总共需要O(n*n)的时间复杂度。 - Sven Marnach

@Harm：一个.index()的时间复杂度是O(n)，但如果对列表中的每个元素都执行一次，则时间复杂度为O(n^2)。 - eumiro

@Sven，@eumiro：我真的很注意了，是吗？Tsss。最后一个问题，像sum这样的数学运算符在制作列表时到底做了什么？你能解释一下那行代码发生了什么吗？ - Harm De Weirdt

他误用了sum来连接大量的列表 - sum([x, y, z] default)是default + x + y + z。顺便说一下，这种方法的性能相当不理想 - 它首先在内存中创建一个大型列表，然后对它们进行n次O(n)级别的连接。更好的一行代码是list(item for i, circle in enumerate(circles) for item in ([circle.m[0]-circle.r, 0, i], [circle.m[0]+circle.r, 1, i])，它避免了在构建列表之前将所有数据都放在内存中，并且一次性构建整个结果列表而不需要连接。 - user395760

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

请注意，这将以不同的顺序提供数据（这应该没有关系，因为您计划进行排序）。

- Sven Marnach

---

我对Python还很陌生，正在学习诸如列表综合之类的Python式东西。感谢你的回答 :) - Harm De Weirdt

Answer 3

我刚刚尝试了几个测试来提高“append”函数的速度。这对你肯定很有帮助。

1. 使用Python语言
2. 使用list(map(lambda……比for+append更快一些
3. 使用Cython语言
4. 使用Numba - jit

代码内容：获取从0到9999999的数字，将它们平方，并使用append函数将它们放入一个新的列表中。

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

运行时间: 3.7秒

2. Using 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))
   

运行时间：3.6秒

3. Using Cython

   • the coding 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
     

我编译了它，然后在.py文件中运行了它。

• in .py file

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

运行时间：1.6秒

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

运行时间：0.57秒

结论：

正如您上面提到的，改变简单的追加表单稍微提高了一点速度。而使用Cython比Python更快。然而，事实证明，在“for+append”方面，使用Numba是提高速度的最佳选择！

- Dane Lee

Answer 4

尝试使用集合包中的deque来附加大量数据行，而不会影响性能。然后使用列表推导式将deque转换回DataFrame。

示例案例：

from collections import deque

d = deque()
for row in rows:
 d.append([value_x, value_y])

df = pd.DataFrame({'column_x':[item[0] for item in d],'column_y':[item[1] for item in d]})

这真是一个省时的工具。

- Qiao Zhang

Answer 5

如果性能是一个问题，我会避免使用append。相反，预先分配一个数组，然后填充它。我也会避免使用索引来查找列表“circles”中的位置。这里有一个重写版本。它不是紧凑的，但我敢打赌由于展开循环，它会非常快速。

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

- Alan Rogers