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

При выполнении этого с кругами по 50 КБ создание списка занимает более 75 секунд.Как вы могли заметить в комментариях, которые я написал, я отключил сборщик мусора, поместил его в отдельную функцию, использовал

append = list.append
append(foo)

вместо просто

list.append(foo)

Я отключил gc, так как после некоторого поискапохоже, что в Python есть ошибка, приводящая к тому, что append запускается в 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. Использование списка (map (лямбда - известно как немного более быстрое средство, чем для + append
3. Использование Cython
4. Использование Numba - jit

СОДЕРЖАНИЕ КОДА: получение чисел от 0 до 9999999, возведите их в квадрат и поместите в новый список, используя append.

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 с

Использование списка (карта (лямбда

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 с

Использование Cython

• кодирование в файле .pyx

  def f1 (): cpdef double ia = 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 с

Использование 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'!

Answer 4

Если бы производительность была проблемой, я бы не использовал append. Вместо этого предварительно выделите массив, а затем заполните его. Я бы также не использовал индекс, чтобы найти позицию в списке «кругов». Вот переписать. Это не компактно, но я держу пари, что это быстро из-за развернутого цикла.

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 5

Попробуйте использовать 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]})

Это экономит время.