파이썬의 숫자 집합에서 숫자의 존재를 확인하는 가장 좋은 방법은 무엇입니까

Question

이렇게 목록의 파이썬 목록은 다음과 같습니다. [1,89,1221,1919,1920,10210,...] 숫자가 몇 천 개가 넘는 나는 나는 그 안에 variabele을 가지고있다.

는 나는이 방법을 수행

if i in mylist: 

그러나 가장 빠른 방법이다?

일부 추가 사양 :

• 목록이 목록은 해당 목록이 사실에 설정 될 수
• 성능을 향상 경우 주문하실 수 있습니다 정수를
• 목록을 보유하고
• 에는 중복을 보유하지 (따라서 중복이 없음)
• 목록은 어떤 종류의 컬렉션이 될 수 있습니다.

Answer 1

집합으로 변환하고 in을 수행하는 것이 가장 빠릅니다.

if i in set(mylist): 

집합은 기본적으로 해시 테이블이며 조회는 O (1)입니다.

Answer 2

목록에서 세트를 만들고 세트를 교차 시키며 교차의 크기를 확인 하시겠습니까?

Answer 3

set으로의 변환은이 목록에서 여러 번 조회 할 때만 가치가 있습니다. 성능이 중요한 경우 처음부터 set으로 작업하는 경우 (요소를 삽입하는 동안) 목록을 작성하는 것보다 더 나은 성능을 제공하는지 측정해야합니다. 요컨대, 몇 가지 시도하고 측정하십시오.

그러나 단일 멤버십 테스트 용 세트로 변환하면 새 데이터 구조를 만드는 오버 헤드로 인해 비효율적입니다.

import random 
import timeit 

mylist = list(random.randint(1, 50000) for i in xrange(1000)) 
myset = set(mylist) 

s = "1919 in mylist" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in set(mylist)" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

다음은 결과입니다 :

1919 in mylist:22.81 usec/pass 
1919 in set(mylist):65.42 usec/pass 

Answer 4

한 가지 방법은 다양한 방법을 테스트 timeit module을 사용하는 것입니다. 예를 들어, 다음 코드 채찍질 :

import array 
import bisect 
import random 
import timeit 

mylist = list(random.randint(1, 50000) for i in xrange(1000)) 
myset = set(mylist) 
myarray = array.array('l', mylist) 

s = "1919 in mylist" 
t = timeit.Timer(s, "from __main__ import mylist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in myset" 
t = timeit.Timer(s, "from __main__ import myset") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in myarray" 
t = timeit.Timer(s, "from __main__ import myarray") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

mysortedlist = sorted(mylist) 
mysortedarray = array.array('l', mysortedlist) 

s = "1919 in mysortedlist" 
t = timeit.Timer(s, "from __main__ import mysortedlist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

s = "1919 in mysortedarray" 
t = timeit.Timer(s, "from __main__ import mysortedarray") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

def bisect_in(a, x): 
    i = bisect.bisect_left(a, x) 
    return (i != len(a) and a[i] == x) 

s = "bisect_in(mysortedlist, 1919)" 
t = timeit.Timer(s, "from __main__ import bisect_in, mysortedlist") 
print s + ":%.2f usec/pass" % (1000000 * t.timeit(number = 100000)/100000) 

을 나는 다음과 같은 결과를 얻었다 :이 테스트가 가정에서 세트를 사용하는 것이 가장 빠른 것으로 다른 사람의 주장을 (지원

1919 in mylist:73.89 usec/pass 
1919 in myset:0.29 usec/pass 
1919 in myarray:103.77 usec/pass 
1919 in mysortedlist:75.12 usec/pass 
1919 in mysortedarray:114.21 usec/pass 
bisect_in(mysortedlist, 1919):4.17 usec/pass 

코드가 만든다).

Answer 5

일부 메모리 효율성을 희생하려는 경우 목록 색인이 확인하려는 값인 조회 테이블을 작성할 수 있습니다.

원본 목록 :

In [106]: %timeit i in myList 
    10000 loops, best of 3: 21.3 us per loop 

는 조회 테이블을 건물 :

In [90]: lookup = [False for i in range(max(myList)+1)] 

    In [91]: for i in myList: 
       lookup[i] = True 

    In [92]: %timeit lookup[i] 
    10000000 loops, best of 3: 50.7 ns per loop 

룩업 테이블은 여기에 정렬되지 않은 목록 이상 ~ 400 배 빠르다.

이 옵션은 목록의 최대 값이 허용 가능하게 낮고 조회 테이블을 설정할 시간이 변수가 테이블에 있는지 확인하는 데 소요되는 시간보다 현저히 짧은 경우에만 실제로 가능합니다.

흥미롭게도 Numpy 배열을 사용할 때 룩업 테이블 방법이 25 % 더 느립니다. (하지만 조회 테이블을 작성하는 것이 훨씬 빠릅니다.)

편집 :이 방법은 "i set (myList)"에서 속도면에서 2를 능가합니다.