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導致append在O（n）而不是O（c）時間運行的bug。

那麼這種方式是最快的方式還是有辦法讓這個運行更快？ 任何幫助，不勝感激。

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）。

進一步（comparitively未成年人）的改進是使用列表理解，而不是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

如果性能問題，我會避免使用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 4

我剛剛嘗試過幾次測試來提高「追加」功能的速度。這對你肯定有幫助。

1. 使用Python
2. 使用列表（地圖（拉姆達 - 被稱爲快一點手段比+追加
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)) 
   

RUN TIME：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)) 

RUN TIME：3.6小號

使用用Cython

• 在.pyx文件的編碼

  DEF F1（）： cpdef double i a =範圍（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)) 
  

RUN TIME：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'提高速度的最佳選擇！