2.7. Dictionaries

이 문서는 영문으로된 내용을 구글 번역기를 활용하여 번역한 내용입니다. 
개인적인 공부 및 추후 다시 볼 수 있도록 하기 위해 개인 블로그에 번역 내용을 옮겨 놓았습니다.
원문과 내용이 다를시 책임지지 않으며, 저작권 문제가 발생시 언제든 삭제 될 수 있습니다. 

Problem Solving with Algorithms and Data Structures using Python by Bradley N. Miller, David L. Ranum is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License. 

두 번째 주요 파이썬 데이터 구조는 사전(Dictionary)입니다. 사전에서 알 수 있듯이 사전은 위치가 아닌 키를 사용하여 사전에있는 항목에 액세스 할 수 있다는 점에서 목록(List)과 다릅니다. 이 책의 뒷부분에서 사전을 구현하는 많은 방법이 있음을 알게 될 것입니다. 지금 주목해야 할 가장 중요한 점은 사전에 항목 가져 오기 및 항목 설정 작업은 O(1)입니다. 또 다른 중요한 사전 연산은 contains 연산입니다. 키가 사전에 있는지 여부를 확인하는 것도 O(1)입니다. 모든 사전 작업의 효율성은 표 3에 요약되어 있습니다. 사전 성능에 대한 한 가지 중요한 점은 우리가 표에서 제공하는 효율성은 평균적인 성능에 대한 것입니다. 드문 경우지만, contains, get item 및 set item 연산은 O(n) 성능으로 변질 될 수 있습니다. 이후 장에서 사전을 구현할 수있는 다양한 방법에 대해 이야기 할 것입니다.

operation	Big-O Efficiency
copy	O(n)
get item	O(1)
set item	O(1)
delete item	O(1)
contains (in)	O(1)
iteration	O(n)

마지막 성능 실험을 위해 목록과 사전에 모두 있는 contains 연산의 성능을 비교합니다. 이 과정에서 우리는 목록에 대한 contains 연산자가 O(n)이고 사전에 대한 contains 연산자가 O(1)인지 확인합니다. 이 두 가지를 비교하기 위해 사용할 실험은 간단합니다. 우리는 숫자의 범위를 가진 목록을 만들 것입니다. 그런 다음 무작위로 번호를 선택하고 번호가 목록에 있는지 확인합니다. 우리의 성과표가 정확하다면 목록이 더 커지면 하나의 숫자가 목록에 포함되어 있는지를 결정하는 데 더 오래 걸릴 것입니다.

숫자가 키로 등록된 사전에 대해 동일한 실험을 반복합니다. 이 실험에서 우리는 숫자가 사전에 있는지 여부를 결정하는 것이 훨씬 빠르지만 사전이 커지더라도 확인하는데 걸리는 시간은 일정하게 유지되어야합니다.

Listing 6에서는 이 비교를 구현 합니다. 정확히 동일한 작업인 number in container를 수행하고 있습니다. 차이점은 7 행의 x는 목록이고 9 행의 x는 사전입니다.

Listing 6

1 2 3 4 5 6 7 8 9 10 11

import timeit import random for i in range(10000,1000001,20000):     t = timeit.Timer("random.randrange(%d) in x"%i,                      "from __main__ import random,x")     x = list(range(i))     lst_time = t.timeit(number=1000)     x = {j:None for j in range(i)}     d_time = t.timeit(number=1000)     print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))

그림 4는 Listing 6을 실행한 결과를 요약한 것입니다. 사전이 지속적으로 빠르다는 것을 알 수 있습니다. 가장 작은 목록 크기인 10,000 개의 요소에 대해 사전은 목록보다 89.4 배 빠릅니다. 가장 큰 목록 크기인 990,000 개 요소의 사전은 11,603 배 빠릅니다! 또한 목록에있는 contains 연산자가 목록의 크기에 따라 선형 적으로 커지는 시간을 볼 수 있습니다. 이것은 목록에있는 contains 연산자가 O(n)이라는 주장을 검증합니다. 사전에 포함 연산자가 포함된 시간은 사전 크기가 커질 때도 일정하다는 것을 알 수 있습니다. 실제로 사전 크기가 10,000 인 경우 포함 작업에 0.004 밀리 초가 걸렸으며 사전 크기가 990,000 인 경우 0.004 밀리 초가 걸렸습니다.

파이썬은 진화하는 언어이기 때문에 항상 뒤에서 변화가 일어나고 있습니다. 파이썬 데이터 구조의 최신 정보는 파이썬 웹 사이트에서 찾을 수 있습니다. 이 글을 쓰는 시점에서 파이썬 위키에는 Time Complexity Wiki에서 찾을 수 있는 멋진 시간 복잡성 페이지가 있습니다.

Self Check

Q-4: Which of the list operations shown below is not O(1)?(A) list.pop(0)

(B) list.pop()

(C) list.append()

(D) list[10]

(E) all of the above are O(1)

Check MeCompare me

Q-5: Which of the dictionary operations shown below is O(1)?(A) 'x' in mydict

(B) del mydict['x']

(C) mydict['x'] == 10

(D) mydict['x'] = mydict['x'] + 1

(E) all of the above are O(1)

Check MeCompare me