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

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

---

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

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

if something in dict_of_stuff:
    pass

과

if something in list_of_stuff:
    pass

내 생각은 그 지시가 더 빠르고 효율적일 것이라는 것이다

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

편집 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 요소) 목록이 잘 수행됩니다.

---

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

---

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

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

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

관련 :

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

---

@ 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 개의 고유 한 값만 가질 수 있으며, 이는 검색 할 공간이 훨씬 작습니다!

SilentGhost's mistake about dicts is actually illuminating because one could use a dict to correlate duplicated data (in values) into a nonduplicated set (keys), and thus keep one data object to hold all data, yet still be fast as a lookup table. For example, a dict key could be the value being looked up, and the value could be a list of indices in an imaginary list where that value occurred.

For example, if the source data list to be searched was l=[1,2,3,1,2,1,4], it could be optimized for both searching and memory by replacing it with this 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]})

With this dict, one can know:

1. If a value was in the original dataset (ie 2 in d returns True)
2. Where the value was in the original dataset (ie d[2] returns list of indices where data was found in original data list: [1, 4])

---

You don't actually need to store 10 million values in the table, so it's not a big deal either way.

Hint: think about how large your result can be after the first sum of squares operation. The largest possible result will be much smaller than 10 million...

참고URL : https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table