효율적인 프로그램과 리스트

효율적인 프로그램을 작성하려면 사용하려는 문제에 대한 인식을 명확히 하고 사용하고자 하는 자료구조를 확실히 이해해야한다.

 

사실, 성능을 중요하게 생각해야 하는 코드작업에서는 어떤 데이터를 어떻게 다룰지, 어떤값을 인자로 넘길지 고민하고 그 상황에서 빠르게 작동하는 자료구조를 선택하는것이 성능에 큰 영향을 미친다.

파이썬에서 리스트와 튜플은 배열이라고 하는 자료구조의 한 종류다. C에서 흔하게 배웠지만 배열은 어떤 정해진 내재적 순서에따라 데이터를 나열해둔 것이다. 이렇게 순서가 정해져 있다는 점에 주목하자. 순서가 정해져 있다면 배열 내 특정 위치에 있는 데이터를 O(1)만에 접근 할 수 있다. 

 

배열을 만들기 위해서는 먼저 시스템 메모리 블록을 할당한다. 다양한 자료구조 (리스트 등)들은 모두 마찬가지 이다. 

 

이때 각 블록의 segmentation에는 실제 데이터를 가리키는 포인터가 있고 해당 포인터는 정수 크기를 갖는다.

메모리 블록의 할당은 커널에서 이루어 지는데 커널에서 N개의 연속된 메모리 section을 요청한다.

파이썬의 리스트는 동적으로 생성되기 때문에 마지막 블록에는 길이는 저장하는 포인터가 있음을 명심하자. 그러면 N-1만큼의 공간에 자료를 저장할 수 있다.

리스트에서 특정 값을 찾기 위해서는 어떤 값이 리스트의 몇번째 칸에 있는지만 알면된다. 모든 데이터는 리스트에 담기는 것으로 인해 같은 크기를 점유 한다.(포인터) 그러므로 데이터 의 종류는 알 필요 없다. 

 

만약 배열의 어떤 항목에 들어 있는 ex) 7 인 경우에 시작하는 위치에서 7번째 칸을 찾아 포인터를 따라가면 된다. 항목을 읽기 위해서는 시작 포인터의 위치 + 검색하고자 하는 위치만큼 이동하면 된다. 

 

리스트 선형탐색

 

import timeit


def linear_search(num, stack):
    for i, item in enumerate(stack):
        if item == num:
            return i
    return -1

순서가 알려져 있지 않은 경우에 특정 항목을 찾기 위해서는 탐색을 수행해야 한다. 위 코드는 가장 기본적으로 순차적으로 탐색하는 linear search 이다.

 

이 알고리즘은 최악의 경우 O(n)시간 복잡도를 갖는다. 리스트의 끝에서 찾고자 하는 값을 못찾는 경우이다. 

 

이를 개선하기 위해서는 값이 메모리에 저장되는 방식을 알거나 각 포인터가 어떤 순서로 정렬되어 있는지를 알아야 한다. 이는 dictionary와 Set의 특징과도 같다. 

 

만약 값이 크기 순이라면 O(n)-> O(log n)으로 줄일수 있다. 

 

 

이진 탐색

def binary_search(num, stack):
    imin, imax = 0, len(stack)
    while True:
        if imin >= imax:
            return -1
        midpoint = (imin + imax) // 2
        if stack[midpoint] > num:
            imax = midpoint
        elif stack[midpoint] < num:
            imin = midpoint + 1
        else:
            return midpoint

파이썬 리스트는 정렬 알고리즘을 내장하고 있는데 Tim 정렬을 사용한다. 최적의 경우 O(n), 최악의 경우 O(n log n)의 시간 복잡도를 갖는다. 

 

리스트를 정렬하고 나면 평균적으로 O(log n)을 갖는 이진 탐색을 통해 항목을 찾는다. 이진 탐색은 가운데 값과 비교하는 방법이다. 

 

이경우는 잠재적으로 무거울수 있는 다른 자료구조에 의지하지 않고 리스트에서 항목을 찾을 수 있다. 리스트가 정렬된 뎡우에는 이진 탐색이 가장 최선일 수 있다.