ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2.7. Dictionaries
    번역/Problem Solving with Algorithms and Data 2017. 10. 28. 14:43
    반응형

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


    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) 성능으로 변질 될 수 있습니다. 이후 장에서 사전을 구현할 수있는 다양한 방법에 대해 이야기 할 것입니다.

    operationBig-O Efficiency
    copyO(n)
    get itemO(1)
    set itemO(1)
    delete itemO(1)
    contains (in)O(1)
    iterationO(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


    반응형

    '번역 > Problem Solving with Algorithms and Data' 카테고리의 다른 글

    2.9. Key Terms  (0) 2017.10.28
    2.8. Summary  (0) 2017.10.28
    2.6. Lists  (0) 2017.10.28
    2.5. Performance of Python Data Structures  (0) 2017.10.28
    2.4. An Anagram Detaction Example  (0) 2017.10.28

    댓글

Designed by Tistory.