파이썬에서 큰 목록의 성능을 향상시키는 방법

Question

나는 1,000,000 개의 정수 (정렬 된) "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]) 

이 작업을 반복하는 수백만 달러를 내 기계. 이 코드의 성능을 향상시킬 수있는 방법이 있습니까? 나는 파이썬 2.6을 사용하고 파이썬 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.. 

O P의 솔루션

%%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 

이진 검색 솔루션

%%timeit 
for b in blist: 
    position = bisect.bisect_left(alist, b) 
    distance = min([b-alist[position-1],alist[position+1]-b]) 
1 loop, best of 3: 1.57 s per loop 

영업 이익의 쉽고 신속

%%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.10,000,000 및 8,000,000의 int를 포함하는 11 개 및 목록 :

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의 모든 100000 번째 항목을 사용하고 스케일 업. 이진 검색은 훨씬 빠르며 점진적 검색은 더 빠르며 NumPy는 모두 정상입니다. 단 몇 초만 걸립니다.

마지막 항목은 distance = min(...) 행이없는 나의 증분 검색이므로 비교할 수 없습니다. 그러나 검색 결과 전체 2.15 초 중 약 34 % 만 차지하는 것으로 나타났습니다. 그래서 지금은 distance = min(...) 계산이 대부분의 시간을 책임지고 있기 때문에 제가 할 수있는 일은별로 없습니다. 파이썬

결과는 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) 

모든 버전 및 테스트에 전체 코드 : 당신이 집중적는 CPU 파이썬을 사용하는 이유

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__))