Python append performance

Question

I'm having some performance problems with 'append' in Python. I'm writing an algorithm that checks if there are two overlapping circles in a (large) set of circles. I start by putting the extreme points of the circles (x_i-R_i & x_i+R_i) in a list and then sorting the list.

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

In between I generate N random circles and put them in the 'circles' list.

"""
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 running this with 50k circles it takes over 75 seconds to generate the list. As you might see in the comments I wrote I disabled garbage collect, put it in a separate function, used

append = list.append
append(foo)

instead of just

list.append(foo)

I disabled gc since after some searching it seems that there's a bug with python causing append to run in O(n) instead of O(c) time.

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

Answer 1

Instead of

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

use

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

This could decrease your O(n^2) to O(n).

Your whole makeList could be written as:

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