파이썬 패턴 - 최적화 이야기

나에게 처음으로 떠오른 첫 번째 버전은 완전히 너무 쉬운 것이었다:

    def f1(list):
        string = ""
        for item in list:
            string = string + chr(item)
        return string

    def f2(list):
        return reduce(lambda string, item: string + chr(item), list, "")

내가 대답했다 "물론이야, 그렇지만 그것은 각 리스트 항목 당 함수 호출(람다함수)을 희생하고 그렇게 하는 거야, 그것은 더 느릴거라고 확신해, 왜냐하면 함수 호출 부담은 for 회돌이 부담보다 더 크기 때문이야".

(좋다, 그래서 나는 이미 그 비교를 수행하여 보았다. f2()는 f1()보다 60% 더 시간이 걸렸다. 그래서 거기에는 :-)

내 친구가 말했다, '흠, 나는 이것이 더 빠를 필요가 있어'. 내가 말했다, '좋아, 이 버전은 어때' :

    def f3(list):
        string = ""
        for character in map(chr, list):
            string = string + character
        return string

물론, 공간 대 시간은 잘 알려진 교환-관계이다, 그래서 첫 번째 이유는 우리를 놀라게 해서는 안된다, 그렇지만, 왜 두 개의 회돌이가 한 개보다 빠른건가? 두개의 이유가 있다.

첫째로, f1()에서, 내장 함수 chr()이 매 반복때 마다 탐색되어진다, 반면에 f3()에서는, 그것은 ( map()에 대한 인수로서) 한 번만 탐색될 뿐이다. 나는 내 친구에게 말했다. '이 탐색은 상대적으로 대가가 너무 비싸, 왜냐하면 파이썬의 동적 영역 규칙이 뜻하는 바는 그것이 현재 모듈의 전역 사전에서 탐색되어지고 (여기서는 실패했고), 그리고 나서 내장 함수의 사전에서 탐색되어진다(여기에서 발견되었어)는 것을 의미하기 때문이야. 더 나쁘게도, 사전 탐색이 성공적이지 못하면, 해쉬 연결 작업의 방식 때문에, (평균적으로) 성공적일 경우보다 약간 더 느려'.

f3()이 f1()보다 더 빠른 두 번째 이유는 chr(item)에 대한 호출이, 바이트코드 인터프리터에 의해서 실행될 때, map() 함수에 의해서 실행될 때보다도 아마 약간 더 느리다는 것이다 - 바이트코드 인터프리터는 각각의 호출 (load 'chr', load 'item', call)에 대하여 세 개의 바이트코드 지시어를 실행해야만 한다, 반면에 map() 함수는 그 모든 것을 C에서 실행한다.

이런고로 우리는 타협책을 고려해야 했는데, 그것은 공간을 추가로 낭비하지 않을 것이고, 반면에 chr() 함수를 찾는 속도를 높여 줄 것이다:

    def f4(list):
        string = ""
        lchr = chr
        for item in list:
            string = string + lchr(item)
        return string

여전히, 우리의 최고로 좋은 버전, f3()은 가장 쉬운 버전, f1()보다 겨우 두배 빠를 뿐이었다. 우리는 더 좋게 할 수 있을까?

내가 걱정한 것은 그 알고리즘의 2차 방정식 같은 행위가 우리를 괴롭힐 것이라는 것이었다. 지금까지, 우리는 256개의 정수를 테스트 데이타로 가지는 리스트를 사용해왔다, 왜냐하면 그것이 내 친구가 그 함수에 필요하다고 하는 것이었기 때문이었다. 그러나 이천개의 문자를 가지는 리스트에 적용된다면 어떻게 되나? 우리는 한번에 한 문자씩, 길고 긴 문자열을 연결해야 할 것이다. 충돌부담이라는 것을 고려하지 않고, 이런 방식으로 길이가 N인 리스트를 생성한다면, '1 + 2 + 3 + ... + (N-1)' 혹은 'N*(N-1)/2', 또는 '0.5*N**2 - 0.5*N'개의 문자열이 전체적으로 복사되어야만 한다는 것을 쉽게 알 수 있다. 이것 말고도, N개의 문자열 할당 처리가 있다, 그러나 충분히 큰 N 이라면, 'N**2'을 포함하는 단어가 대신하게 될 것이다. 실제로, (2048개의 항목을 가진) 8 배 긴 리스트라면, 이 함수들은 모두 8배 이상 시간이 걸린다; 실제로는, 16배에 가깝다. 나는 감히 64 배 길이의 리스트를 시도하지는 않았다.

알고리즘에서 이와 같은 2차 방정식류의 행위를 피하기 위한 일반적인 테크닉이 있다. 나는 정확하게 256개의 항목을 가지는 문자열들을 위하여 다음과 같이 코드를 하였다:

    def f5(list):
        string = ""
        for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
            s = ""
            for character in map(chr, list[i:i+16]):
                s = s + character
            string = string + s
        return string

결국, 나는 근본적으로 다른 접근을 시도하였다: 오직 내재된 회돌이만을 사용하는 것. 주목할 것은 그 전체 처리는 다음과 같이 기술될 수 있다는 것이다: chr()을 각각의 리스트 항목에 적용한다; 그리고는 그 결과로 나온 문자들을 연결한다. 우리는 이미 첫 번째 파트를 위해서 암시된 회돌이를 사용하였다: map(). 다행스럽게도, C 에서 구현된 그 문자열 모듈에는 약간의 문자열 연결 함수들이 있다.
특히나, string.joinfields(list_of_strings, delimiter)는, 구분자(delimiter)를 두 문자열 사이에 각각 위치시키고, 문자열의 리스트를 연결한다. 그 어느 것도 우리가, 그 빈 문자열을 구분자로 사용하여, 문자들의 리스트를 연결하는 것을 막을 수 없다 (그것은 파이썬에서 길이가 1 인 그저 단순한 문자열이다). 자 보라:

    import string
    def f6(list):
        return string.joinfields(map(chr, list), "")

그리고 승리자는...

    import array
    def f7(list):
        return array.array('b', list).tostring()

"그만", 내 친구가 말했다. "음의 배수로 가기전에 멈춰" - "이거면 내 프로그램에 충분하게 빨라". 나도 동감했다, 그렇지만 나는 또 하나 더 접근을 시도해 보고 싶었다: 그 전체 함수를 C 로 작성하는 것. 이것은 최소한으로 메모리를 요구할 것이다 (그것은 즉시 길이 N의 문자열을 할당할 것이다) 그리고 그의 범용성때문에, 그 배열 모듈에 있다고 내가 알고 있는 그 C코드에서 약간의 지시어들을 절약할 것이다. (그것은 1, 2, 그리고 4 바이트 크기의 정수를 지원한다). 그렇지만, 그것은 그 리스트로부터 그 항목들을 한번에 한개씩 추출해야만 하고, 그리고 그들로부터 그 C 정수를 추출해야만 하는 것을 피할 수 없을 것이다, 둘 다 모두 파이썬-C API에서 대단히 비용이 많이 드는 처리방법이다, 그래서 나는 f7()과 비교하여 기껏해야 미미한 속도 개선을 예상했다. (그러한 파이썬의 한-줄짜리 코드를 이용하는 것과 비교하여) 확장을 테스트하고 작성하는 노력이 있어야 한다면, 뿐만 아니라 비-표준 파이썬 확장에 의존적이라면, 나는 이 선택을 따르지 않기로 결정했다...

결 론

• 제 1 규칙 : 속도 병목현상이 증명되어 있을 때만 오직 최적화하라. 오직 최대한 안쪽의 회돌이만 최적화하라. (이 규칙은 파이썬에 독립적이다, 그러나 그것을 반복하여 말해도 손해가 아니다, 왜냐하면 그것은 많은 일을 절감해 줄 수 있기 때문이다. :-)
• 작은 것이 아름답다. 파이썬이 바이트코드 지령어들과 변수 탐색을 엄중히 요구한다면, 여분의 테스트를 추가하여 약간의 일을 절약하는 것은 별로 도움이 안된다.
• 내재된 처리방법을 사용하라. map()에 암시된 회돌이는 명시적인 for 회돌이보다 더 빠르다; 명시적인 회돌이 카운터를 가지고 있는 while 회돌이는 더욱 더 느리다.
• 여러분의 안쪽 회돌이에서 파이썬으로 씌여진 함수를 호출하는 것을 피하라. 이것에는 람다가 포함된다. 그 내부 회돌이를 라인안에 넣음으로써 많은 시간을 절약할 수 있다.
• 지역 변수는 전역변수보다 더 빠르다; 여러분이 회돌이 안에서 전역 상수를 사용한다면, 그것을 회돌이 안으로 들어오기 전에 지역 변수로 복사하라. 그리고 파이썬에서, (전역적인 혹은 내장된) 함수 이름은 또한 전역 상수들이다!
• map(), filter() 또는 reduce()를 사용하여 명시적인 for 회돌이를 대치하라, 그러나 오직 여러분이 내장 함수만을 사용할 수 있다면: 내장함수와 함께하는 map은 for 회돌이를 이긴다, 그러나 라인-안 코드를 가진 for 회돌이는 람다 함수를 가진 map를 이긴다!
• 여러분의 알고리즘에서 이차함수적인 행위가 있는지를 점검하라. 그러나 더욱 복잡한 알고리즘은 오직 거대한 N 에서만 이익이 있다는 것을 주목하라 - 작은 N에 대하여는, 그 복잡함이 별 이익이 없다. 우리의 경우에 있어서, 그 더욱 단순한 버전이 여전히 약간 더 빠를 정도로 256은 충분히 작다고 판명되었다. 여러분의 마일리지(측정치)는 변할 것이다 - 이것은 연구해 볼 가치가 있다.
• 그리고 마지막으로 그러나 결코 작지 않은 것: 데이타를 수집하라. 파이썬의 뛰어난 프로파일 모듈은 즉시 여러분의 코드에서 병목을 보여줄 수 있다. 만약 여러분이 다른 버전의 알고리즘을 고려하고 있다면, time.clock() 함수를 사용하여 그것을 탄탄한 회돌이 안에서 테스트하라.

    import time
    def timing(f, n, a):
        print f.__name__,
        r = range(n)
        t1 = time.clock()
        for i in r:
            f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
        t2 = time.clock()
        print round(t2-t1, 3)

끝맺는 말

그러나 이번에는, 그것은 상대적으로 충돌부담이 적었다. 두 개의 후보자가 있는데, 확실한 후보자는:

    def g1(string):
        return map(ord, string)

    import array
    def g2(string):
        return array.array('b', string).tolist()

예제 코드

• timing f1() through f7()
• timing g1() and g2()