[python] 파이썬 : 룩업 테이블에 대한 목록 대 Dict

Program / 글쓴이

나는 어떤 종류의 룩업 테이블에 넣어야 할 약 1 천만 개의 값을 가지고 있으므로 어느 것이 더 효율적인 목록 이나 딕트 인지 궁금합니다 .

나는 당신이 둘 다 이와 같은 것을 할 수 있다는 것을 안다.

if something in dict_of_stuff:
    pass

과

if something in list_of_stuff:
    pass

내 생각은 dict이 더 빠르고 효율적일 것입니다.

당신의 도움을 주셔서 감사합니다.

편집 1
내가하려는 일에 대한 조금 더 많은 정보. 오일러 문제 92 . 계산 된 값이 모두 준비되었는지 확인하기 위해 룩업 테이블을 만들고 있습니다.

편집 2
효율성을 검색하십시오.

편집 3
값과 관련된 값이 없습니다 … 그래서 세트 가 더 좋습니까?

답변

속도

목록의 조회는 O (n)이고, 사전의 조회는 데이터 구조의 항목 수와 관련하여 O (1)로 상각됩니다. 값을 연관시킬 필요가 없으면 세트를 사용하십시오.

기억

사전과 세트 모두 해싱을 사용하며 오브젝트 스토리지에만 사용하는 것보다 훨씬 많은 메모리를 사용합니다. Beautiful Code의 AM Kuchling에 따르면 구현시 해시 2/3가 가득 차도록 유지하려고하므로 약간의 메모리가 낭비 될 수 있습니다.

업데이트 된 질문에 따라 즉시 새 항목을 추가하지 않으면 목록을 정렬하고 이진 검색을 사용하는 것이 좋습니다. 이것은 O (log n)이며 문자열의 경우 속도가 느려질 수 있으며 자연스러운 순서가없는 객체에서는 불가능합니다.

답변

dict는 해시 테이블이므로 키를 찾는 것이 정말 빠릅니다. dict과 list 사이에서 dict가 더 빠릅니다. 그러나 연결할 값이 없으면 세트를 사용하는 것이 좋습니다. “테이블”부분이없는 해시 테이블입니다.

편집 : 새로운 질문, 예, 세트가 더 좋습니다. 하나는 1로 끝나는 시퀀스와 다른 하나는 89로 끝나는 시퀀스에 대해 2 개의 세트를 만들면됩니다. 세트를 사용하여이 문제를 성공적으로 해결했습니다.

답변

set()정확히 당신이 원하는 것입니다. O (1) 조회이며 dict보다 작습니다.

답변

나는 약간의 벤치마킹을했고 dict가 Linux의 i7 CPU에서 python 2.7.3을 실행하여 큰 데이터 세트에 대해 목록과 설정보다 빠릅니다.

  • python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

    10 루프, 루프 당 3 : 64.2 msec 이상

  • python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

    10000000 루프, 3 : 3의 최고 루프 당 0.0759 usec

  • python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

    1000000 루프, 최고 3 : 3 루프 당 0.262 usec

보시다시피, dict는 목록보다 상당히 빠르며 설정보다 약 3 배 빠릅니다. 그러나 일부 응용 프로그램에서는 여전히 아름다움의 세트를 선택하려고 할 수 있습니다. 그리고 데이터 세트가 실제로 작은 경우 (<1000 요소) 목록이 잘 수행됩니다.

답변

당신은 받아쓰기를 원합니다.

파이썬에서 (정렬되지 않은)리스트의 경우, “in”연산에는 O (n) 시간이 필요합니다. 많은 양의 데이터가있을 때는 좋지 않습니다. 반면 dict은 해시 테이블이므로 O (1) 조회 시간을 예상 할 수 있습니다.

다른 사람들이 지적했듯이 키 / 값 쌍이 아닌 키 만있는 경우 대신 세트 (특별한 유형의 dict)를 선택할 수 있습니다.

관련 :

  • Python Wiki : Python 컨테이너 작업의 시간 복잡성에 대한 정보.
  • SO : Python 컨테이너 작업 시간 및 메모리 복잡성

답변

데이터가 고유 한 경우 set ()이 가장 효율적이지만 두 가지 dict (독점도 필요합니다 🙂

답변

@ EriF89를 보여주는 새로운 테스트 세트는이 세월이 지난 후에도 여전히 옳습니다.

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

여기서는 일부 사용 사례에서 tuple보다 빠르며 lists메모리를 적게 사용 하는 것으로 알려진을 비교합니다 . 조회 테이블의 경우tuple 공정하지 않습니다.

모두 dict와set 아주 잘 수행. 이것은 고유성에 대한 @SilentGhost 답변과 관련이있는 흥미로운 점을 제시합니다. OP에 데이터 세트에 10M 값이 있고 중복 된 값이 있는지 알 수없는 경우 요소의 세트 / dict를 병렬로 유지할 가치가 있습니다. 실제 데이터 세트 및 해당 세트 / dict에 존재하는지 테스트합니다. 10M 데이터 포인트는 10 개의 고유 한 값만 가질 수 있으며, 이는 검색 할 공간이 훨씬 작습니다!

dicts에 대한 SilentGhost의 실수는 실제로 dict을 사용하여 중복 된 데이터 (값)를 중복되지 않은 세트 (키)와 상관시켜 하나의 데이터 오브젝트를 유지하여 모든 데이터를 보유 할 수 있지만 여전히 룩업 테이블처럼 빠르기 때문입니다. 예를 들어, dict 키는 조회되는 값일 수 있으며 값은 해당 값이 발생한 가상 목록의 색인 목록 일 수 있습니다.

예를 들어, 검색 할 소스 데이터 목록이 l=[1,2,3,1,2,1,4]인 경우 검색 및 메모리를이 dict로 바꾸어 검색 및 메모리 모두에 대해 최적화 할 수 있습니다.

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

이 구술을 통해 다음을 알 수 있습니다.

  1. 경우 값이 원본 데이터 셋에 있었다 (즉, 2 in d반환 True)
  2. 어디 값이 원본 데이터 셋에 있었다 (즉 d[2]데이터가 원본 데이터 목록에서 발견 된 인덱스의 목록을 반환합니다 [1, 4])