如何提高Python中的大型列表的性能

Question

我有一個龐大的列表，說1000萬整數（排序）「alist」。我需要的是讓一些整數（來自「blist」）和列表中的鄰居之間的距離最小。我通過查找整我找的位置做了，之前和之後獲得該項目，並測量差異：

alist=[1, 4, 30, 1000, 2000] #~10 million integers 
blist=[4, 30, 1000] #~8 million integers 

for b in blist: 
    position=alist.index(b) 
    distance=min([b-alist[position-1],alist[position+1]-b]) 

這種操作要重複數百次，不幸的是，它發生在年齡我機。有沒有一種方法來提高此代碼的性能？我使用Python 2.6和python 3不是一個選項。

Answer 1

我真的很喜歡這種計算的Numpy模塊。

在你的情況，這將是（這是很長的答案，可以工廠化更有效率）：

import numpy as np 

alist = [1, 4, 30, 1000, 2000] 
blist = [4, 30, 1000] 

a_array = np.asarray(alist) 
b_array = np.asarray(blist) 

a_index = np.searchsorted(a_array, b_array) # gives the indexes of the elements of b_array in a_array 

a_array_left = a_array[a_index - 1] 
a_array_right = a_array[a_index + 1] 

distance_left = np.abs(b_array - a_array_left) 
distance_right = np.abs(a_array_right - b_array) 

min_distance = np.min([distance_left, distance_right], axis=0) 

如果blist的第一個元素是第一ALIST的它不會工作，同樣的結局。 我猜：

alist = [b[0] - 1] + alist + [b[-1] + 1] 

是一個骯髒的解決方法。

基準
的 「仍在運行」 可能我在我的電腦的錯..

alist = sorted(list(np.random.randint(0, 10000, 10000000))) 
blist = sorted(list(alist[1000000:9000001])) 
a_array = np.asarray(alist) 
b_array = np.asarray(blist) 

矢量化解決方案

%%timeit 
a_index = np.searchsorted(a_array, b_array) 

a_array_left = a_array[a_index - 1] 
a_array_right = a_array[a_index + 1] 

min_distance = np.min([b_array - a_array_left, a_array_right - b_array], axis=0) 
1 loop, best of 3: 591 ms per loop 

二進制搜索解決方案

%%timeit 
for b in blist: 
    position = bisect.bisect_left(alist, b) 
    distance = min([b-alist[position-1],alist[position+1]-b]) 
Still running.. 

Ø普的解決方案

%%timeit 
for b in blist: 
    position=alist.index(b) 
    distance=min([b-alist[position-1],alist[position+1]-b]) 
Still running.. 

較小的輸入

alist = sorted(list(np.random.randint(0, 10000, 1000000))) 
blist = sorted(list(alist[100000:900001])) 
a_array = np.asarray(alist) 
b_array = np.asarray(blist) 

矢量化解決方案

%%timeit 
a_index = np.searchsorted(a_array, b_array) 

a_array_left = a_array[a_index - 1] 
a_array_right = a_array[a_index + 1] 

min_distance = np.min([b_array - a_array_left, a_array_right - b_array], axis=0) 
10 loops, best of 3: 53.2 ms per loop 

二進制搜索解決方案

​​

OP的soluti在

%%timeit 
for b in blist: 
    position=alist.index(b) 
    distance=min([b-alist[position-1],alist[position+1]-b]) 
Still running.. 

Answer 2

我建議使用二進制搜索。使其更快，不花費額外的內存，並且只需要稍微改變。而不是alist.index(b)，只需使用bisect_left(alist, b)。

如果您blist被分類爲好，你也可以用一個很簡單的漸進式搜索，沒有從alist開始，但是從以前b的索引搜索當前b。

與的基準Python 2.7。11所並列出包含10萬個，800萬整數：

389700.01 seconds Andy_original (time estimated) 
377100.01 seconds Andy_no_lists (time estimated) 
    6.30 seconds Stefan_binary_search 
    2.15 seconds Stefan_incremental_search 
    3.57 seconds Stefan_incremental_search2 
    1.21 seconds Jacquot_NumPy 
    (0.74 seconds Stefan_only_search_no_distance) 

安迪的原件將需要約4.5天，所以我只用了blist每10個條目，並擴大規模。二進制搜索速度更快，增量搜索速度更快，NumPy擊敗所有，儘管它們都只需要幾秒鐘。

以0.74秒爲單位的最後一項是我的增量搜索，沒有distance = min(...)行，所以它不具有可比性。但它表明，搜索只需要總共2.15秒中的34％。所以我沒有更多的工作可做，因爲大部分時間distance = min(...)計算是負責任的。

與Python的結果3.5.1是相似的：

509819.56 seconds Andy_original (time estimated) 
505257.32 seconds Andy_no_lists (time estimated) 
    8.35 seconds Stefan_binary_search 
    4.61 seconds Stefan_incremental_search 
    4.53 seconds Stefan_incremental_search2 
    1.39 seconds Jacquot_NumPy 
    (1.45 seconds Stefan_only_search_no_distance) 

與所有版本和測試的完整代碼：

def Andy_original(alist, blist): 
    for b in blist: 
     position = alist.index(b) 
     distance = min([b-alist[position-1], alist[position+1]-b]) 

def Andy_no_lists(alist, blist): 
    for b in blist: 
     position = alist.index(b) 
     distance = min(b-alist[position-1], alist[position+1]-b) 

from bisect import bisect_left 
def Stefan_binary_search(alist, blist): 
    for b in blist: 
     position = bisect_left(alist, b) 
     distance = min(b-alist[position-1], alist[position+1]-b) 

def Stefan_incremental_search(alist, blist): 
    position = 0 
    for b in blist: 
     while alist[position] < b: 
      position += 1 
     distance = min(b-alist[position-1], alist[position+1]-b) 

def Stefan_incremental_search2(alist, blist): 
    position = 0 
    for b in blist: 
     position = alist.index(b, position) 
     distance = min(b-alist[position-1], alist[position+1]-b) 

import numpy as np 
def Jacquot_NumPy(alist, blist): 

    a_array = np.asarray(alist) 
    b_array = np.asarray(blist) 

    a_index = np.searchsorted(a_array, b_array) # gives the indexes of the elements of b_array in a_array 

    a_array_left = a_array[a_index - 1] 
    a_array_right = a_array[a_index + 1] 

    distance_left = np.abs(b_array - a_array_left) 
    distance_right = np.abs(a_array_right - b_array) 

    min_distance = np.min([distance_left, distance_right], axis=0) 

def Stefan_only_search_no_distance(alist, blist): 
    position = 0 
    for b in blist: 
     while alist[position] < b: 
      position += 1 

from time import time 
alist = list(range(10000000)) 
blist = [i for i in alist[1:-1] if i % 5] 
blist_small = blist[::100000] 

for func in Andy_original, Andy_no_lists: 
    t0 = time() 
    func(alist, blist_small) 
    t = time() - t0 
    print('%9.2f seconds %s (time estimated)' % (t * 100000, func.__name__)) 

for func in Stefan_binary_search, Stefan_incremental_search, Stefan_incremental_search2, Jacquot_NumPy, Stefan_only_search_no_distance: 
    t0 = time() 
    func(alist, blist) 
    t = time() - t0 
    print('%9.2f seconds %s' % (t, func.__name__))