2.6. Lists

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

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. 

파이썬 디자이너는 목록(List) 데이터 구조를 구현할 때 많은 선택권이 있었습니다. 이들 각각의 선택 사항은 얼마나 빠른 목록 조작이 수행 되는지에 영향을 줄 수 있습니다. 사람들이 올바른 선택을 하도록 돕기 위해 사람들이 가장 일반적으로 목록 데이터 구조를 사용하는 방법을 살펴 보았고 목록 작성을 최적화하여 가장 일반적인 작업이 매우 빨라졌습니다. 물론 그들은 또한 덜 일반적인 작업을 빠르게 하려고 했지만 트레이드 오프가 이루어져야 할 때 일반적이지 않은 작업의 성능이 보다 일반적인 작업에 유리하게 종종 희생되었습니다.

일반적인 두 가지 작업은 인덱싱 및 인덱스 위치 지정입니다. 이러한 작업은 목록의 크기에 관계없이 동일한 시간이 소요됩니다. 이와 같은 연산이 리스트의 크기와 독립적일 때 그들은 O(1)입니다.

또 다른 매우 일반적인 프로그래밍 작업은 목록을 확장하는 것입니다. 긴 목록을 만드는 방법에는 두 가지가 있습니다. append 메서드 또는 연결 연산자를 사용할 수 있습니다. append 메소드는 O(1)입니다. 그러나 연결 연산자는 O(k)입니다. 여기서 k는 연결될 목록의 크기입니다. 작업에 적합한 도구를 선택하여 자신의 프로그램을 보다 효율적으로 만들 수 있으므로 알고 있어야 합니다.

n을 0으로 시작하는 목록을 생성하는 4 가지 방법을 살펴 보겠습니다. 먼저 for 루프를 시도하고 연결을 통해 목록을 만든 다음 연결이 아닌 추가를 사용합니다. 다음에는 list comprehension을 사용하여 list를 생성해 봅니다. 그리고 마지막으로 list 생성자에 대한 호출로 래핑 된 range 함수를 사용하여 가장 분명한 방법으로 시도 할 것입니다. Listing 3은 우리의 목록을 네 가지 다른 방법으로 만드는 코드입니다.

Listing 3

def test1():

    l = []

    for i in range(1000):

        l = l + [i]

def test2():

    l = []

    for i in range(1000):

        l.append(i)

def test3():

    l = [i for i in range(1000)]

def test4():

    l = list(range(1000))

각 함수가 실행되는 데 걸리는 시간을 파악하기 위해 Python의 timeit 모듈을 사용합니다. timeit 모듈은 Python 개발자가 일관된 환경에서 기능을 실행하고 운영 체제에서 가능한 한 비슷한 타이밍 메커니즘을 사용하여 플랫폼 간 타이밍 측정을 수행 할 수 있도록 설계되었습니다.

timeit을 사용하려면 매개 변수가 두 개의 Python 문인 Timer 객체를 만듭니다. 첫번째 매개 변수는 당신이 원하는 파이썬 문입니다. 두 번째 매개 변수는 테스트를 설정하기 위해 한 번 실행되는 명령문입니다. 그런 다음 timeit 모듈은 명령문을 몇 번 실행하는 데 걸리는 시간을 측정합니다. 기본적으로 timeit은 명령문을 백만 번 실행하려고 시도합니다. 완료되면 총 시간(초)을 나타내는 부동 소수점 값으로 시간을 반환합니다. 그러나 이 명령문을 백만 번 실행하므로 결과를 마이크로 초 단위로 읽으면 테스트를 한 번만 실행할 수 있습니다. number라는 이름의 매개 변수를 timeit에 전달하여 테스트 문이 실행된 횟수를 지정할 수 있습니다. 다음 세션에서는 각 테스트 기능을 1000 번 실행하는 데 걸리는 시간을 보여줍니다.

t1 = Timer("test1()", "from __main__ import test1")

print("concat ",t1.timeit(number=1000), "milliseconds")

t2 = Timer("test2()", "from __main__ import test2")

print("append ",t2.timeit(number=1000), "milliseconds")

t3 = Timer("test3()", "from __main__ import test3")

print("comprehension ",t3.timeit(number=1000), "milliseconds")

t4 = Timer("test4()", "from __main__ import test4")

print("list range ",t4.timeit(number=1000), "milliseconds")

concat  6.54352807999 milliseconds

append  0.306292057037 milliseconds

comprehension  0.147661924362 milliseconds

list range  0.0655000209808 milliseconds

위의 실험에서 우리가 타이밍을 내리고 있다는 말은 test1(), test2() 등의 함수 호출입니다. setup 문은 매우 이상하게 보일 수 있으므로 자세히 살펴 보겠습니다. from, import 문에 익숙 할 수도 있지만, 대개 Python 프로그램 파일의 시작 부분에서 사용됩니다. 이 경우 from __main__ import test1문은 test1 함수를 __main__ 네임 스페이스에서  timeit이 타이밍 실험을 위해 설정한 네임 스페이스로 가져옵니다.  timeit 모듈은 예상치 못한 방식으로 함수의 성능을 저해 할 수 있는 사용자가 만든 임의의 이탈 변수에 의해 정리된 환경에서 타이밍 테스트를 실행 하려고 하기 때문에 이 작업을 수행합니다.

위의 실험에서 0.30 밀리 초의 추가 작업은 6.54 밀리 초의 연결보다 훨씬 빠릅니다. 위의 실험에서 목록을 만드는 두 가지 추가 방법에 대한 시간도 보여줍니다. range와 list comprehension에 대한 호출과 함께 리스트 생성자를 사용합니다. List comprehension은 append 연산이 있는 for 루프보다 두 배 빠릅니다.

이 작은 실험에 대한 마지막 관찰은 위에서 볼 수 있는 모든 시간에 실제로 테스트 함수를 호출하기 위한 오버 헤드가 포함된다는 것입니다. 그러나 함수 호출의 오버 헤드는 네 가지 경우 모두 동일하다고 가정 할 수 있으므로 여전히 연산의 의미있는 비교를 얻습니다. 따라서 연결 작업에 6.54 밀리 초가 걸리지만 연결 테스트 기능에는 6.54 밀리 초가 걸리는 것은 정확하지 않습니다. 연습으로 빈 함수를 호출하고 위 숫자에서 빠지는 시간을 테스트 할 수 있습니다.

이제 성능을 구체적으로 측정하는 방법을 살펴 보았습니다. 표 2를 보면 모든 기본 목록 작업의 Big-O 효율성을 확인할 수 있습니다. 표 2를 주의 깊게 생각하면 pop에 대한 두 가지 다른 시간에 대해 궁금해 할 것입니다. pop이 리스트의 끝에서 호출 될 때 O(1)을 취합니다. 그러나 pop이 리스트의 첫 번째 요소 또는 중간의 어디에서든지 호출되면 O(n)입니다. 그 이유는 파이썬이 리스트를 구현하는 방법에 있습니다. 항목이 목록 앞에서 가져온 경우 Python의 구현에서 목록의 다른 모든 요소는 시작 위치로 한 위치 앞으로 이동합니다. 이것은 당신에게 어리석은 것처럼 보일지도 모르지만, 표 2를 보면이 구현이 색인 연산을 O(1)로 할 수 있음을 알 수 있습니다. 이것은 파이썬 구현자가 생각했던 것과 좋은 결과였습니다.

Operation	Big-O Efficiency
index []	O(1)
index assignment	O(1)
append	O(1)
pop()	O(1)
pop(i)	O(n)
insert(i,item)	O(n)
del operator	O(n)
iteration	O(n)
contains (in)	O(n)
get slice [x:y]	O(k)
del slice	O(n)
set slice	O(n+k)
reverse	O(n)
concatenate	O(k)
sort	O(n log n)
multiply	O(nk)

이 성능 차이를 보여주는 방법으로 timeit 모듈을 사용하여 또 다른 실험을 해보죠. 우리의 목표는 프로그램이 목록의 끝에서 튀어 나오면 알려진 크기의 목록에서 pop 작업의 성능을 확인하고, 프로그램이 목록의 시작 부분에서 튀어 나오면 다시 확인할 수 있게 하는 것입니다. 우리는 또한 이 시간을 다른 크기의 목록으로 측정하기를 원할 것입니다. 우리는 목록의 끝에서 튀어 나오는 데 필요한 시간은 목록의 크기가 커지더라도 일정하게 유지되는 반면 목록의 시작 부분부터 튀어 나오는 시간은 목록이 커질수록 계속 증가 할 것이라고 예상합니다.

Listing 4는 pop의 두 가지 사용법 사이의 차이점을 측정하려는 시도입니다. 이 첫 번째 예에서 알 수 있듯이, 끝에서 튀어나오는데는 0.0003 밀리 초가 걸리고, 처음부터 튀어나오는데는 4.82 밀리 초가 걸립니다. 2 백만개 요소의 목록은 16,000의 요소입니다.

Listing 4에 주목해야 할 몇 가지 사항이 있습니다. 첫 번째 문장은 from __main__ import x입니다. 함수를 정의하지는 않았지만 테스트에서 list 객체 x를 사용할 수 있기를 원합니다. 이 방법을 사용하면 단일 pop 구문을 시간만보고 단일 작업의 시간을 가장 정확하게 측정 할 수 있습니다. 타이머가 1000 번 반복되기 때문에 목록의 크기가 루프를 통해 매번 1 씩 감소한다는 것을 지적하는 것도 중요합니다. 그러나 초기 목록의 크기가 200 만 개이기 때문에 전체 크기를 0.05% 만 줄입니다.

Listing 4

popzero = timeit.Timer("x.pop(0)",

                       "from __main__ import x")

popend = timeit.Timer("x.pop()",

                      "from __main__ import x")

x = list(range(2000000))

popzero.timeit(number=1000)

4.8213560581207275

x = list(range(2000000))

popend.timeit(number=1000)

0.0003161430358886719

첫 번째 테스트에서는 pop(0)이 실제로 pop()보다 느리다는 것을 보여 주지만 pop(0)은 O(n) 인 반면 pop()은 O(1)이라는 주장을 검증하지 않습니다. 이 주장을 검증하기 위해 우리는 다양한 범위의 목록 크기에서 두 가지 호출의 성능을 조사해야합니다. Listing 5는 이 테스트를 구현 한 것이다.

Listing 5

popzero = Timer("x.pop(0)",

                "from __main__ import x")

popend = Timer("x.pop()",

               "from __main__ import x")

print("pop(0)   pop()")

for i in range(1000000,100000001,1000000):

    x = list(range(i))

    pt = popend.timeit(number=1000)

    x = list(range(i))

    pz = popzero.timeit(number=1000)

    print("%15.5f, %15.5f" %(pz,pt))

그림 3은 우리 실험의 결과를 보여줍니다. 리스트가 길어질수록 pop(0)에 걸리는 시간도 늘어나고 pop에 걸리는 시간은 매우 평탄하게 유지되는 것을 볼 수 있습니다. 이것은 정확히 우리가 O(n) 및 O(1) 알고리즘에서 볼 것으로 예상되는 것입니다.

우리의 작은 실험에서 오류의 일부 원인은 우리가 코드를 느리게 할 수도있는 측정하는 컴퓨터에 다른 프로세스가 실행되고 있다는 사실을 포함합니다. 그래서 우리가 컴퓨터에서 일어나는 다른 일을 최소화하려고 노력하더라도 시간에 약간의 변화가있을 것입니다. 그렇기 때문에 첫 번째 장소에서 루프가 테스트를 1 천 번 실행하여 통계를 신뢰할 수있는 충분한 정보를 통계적으로 수집합니다.