dict과 list에서 어떤 값을 찾을 경우.

전에도 알고있었는데 그냥 그렇구나 하고 넘어갔던 문제이다.

알고리즘 문제를 풀면서 아 이랬어도 됬구나! 하면서 다시 깨달았다. 역시 코딩은 실전.

리스트에서 어떤 값을 찾는다고 했을때는 O(n)의 시간복잡도가 걸린다. 왜냐하면 하나하나 반복문을

돌면서 값이 맞는지 검사를 해야 하기 때문이다. 그런데 딕셔너리같은경우는 시간복잡도가 O(1)이다.

딕셔너리는 해쉬 테이블이기 때문에 메모리에 값을 직접 저장해놓기 때문이다.

즉 딕셔너리는 메모리를 조금 더 먹는 대신 어떤값을 찾을때 빠르다고 보면 되겠다. 알고리즘 문제를 풀때

파이썬의 특성상 시간초과가 나는 경우가 많이 있는데 이때 리스트대신 딕셔너리를 쓰면 해결될수

있을것 같다.

---

http://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table

의 첫번째답글. 대충 요약만 해둠.

Speed

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure. If you don't need to associate values, use sets.

리스트는 O(n), 딕셔너리는 O(1)의 시간복잡도.

Memory

Both dictionaries and sets use hashing and they use much more memory than only for object storage. According to A.M. Kuchling in Beautiful Code, the implementation tries to keep the hash 2/3 full, so you might waste quite some memory.

딕셔너리와 셋은 메모리를 더 많이 먹고 낭비한다.

If you do not add new entries on the fly (which you do, based on your updated question), it might be worthwhile to sort the list and use binary search. This is O(log n), and is likely to be slower for strings, impossible for objects which do not have a natural ordering.

정렬한 후 이진 탐색으로 하는것도 가치있다. 시간복잡도는 O(log n)이다.

확인 코드.

a = xrange(10000000)
b = dict([[i,0] for i in xrange(10000000)])
import time
s = time.time()
print 999999999 in a
print time.time() - s
s = time.time()
print 999999999999 in b
print time.time() - s