Python 追加性能

Question

我在使用 Python 中的“追加”时遇到了一些性能问题。我正在编写一个算法来检查一组(大)圆圈中是否有两个重叠的圆圈。我首先将圆的极值点 (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)], [])