Python decorator와 wrapt 에 관하여

https://codewithoutrules.com/2017/08/10/python-decorators/?utm_source=newsletter_mailer&utm_medium=email&utm_campaign=weekly

를 의역(?)을 간단히 했습니다. 아직 다 정리한 것은 아니고 또 잘못된 내용이 있을 수 있으니 원문을 참고해주세요 :)

-----

Python decorator는 결점이 있지만 매우 유용합니다.

코드를 쓰기 쉽고 좀 더 읽기 쉽게 만들지만 ‘데코레이티드 된 코드를 호출하는 프로그래머’가 use case를 만드는 것을 방해합니다.

파이썬 프로그래머라면 이 포스트를 통해 왜 decorator가 있는지, 그리고 그것의 한계를 어떻게 상쇄하는지 배울 수 있습니다.

그리고 파이썬 프로그래머가 아니라도, 다른 코드에서 이하의 명심할 내용들이 되었으면 합니다.

왜 Decorator가 존재하는가: 코드를 만들고(authoring) 읽기




프로그래밍 언어는 다음의 4가지 청중을 만족해야 합니다.


소스코드가 돌아가는 컴퓨터
소스코드를 작성한 프로그래머(The author)
소스코드를 미래에 읽을 사람(A future reader)
자신의 함수나 클래스스의 코드를 쓰면서 프로그래머 이를 호출할 프로그래머(A future caller)






Python decorator는 이중 Auther와 readers를 위해 생성되었으나, Caller에 대해서는 그렇지 않습니다.



Decorator가 하는 것과 어떻게 이것이 author와 가독성에 좋은지 알아봅시다.



Java의 synchronized keyword를 Emulate한다고 생각해 봅시다. 당신은 Class의 Method가 Lock이 걸려서 한번에 한개의 Thread만 Call하여 실행하는 것을 원합니다.



아래의 코드를 따라서 synchronized 함수가 새로 어떻게 만들고 주어진 것을 감싸서 교체하는지 확인합시다.

{코드}

이 코드를 통해 synchronized는 다음과 같이 사용될 수 있습니다.

{코드}

Author에게는 이는 문제가 많은 사용법입니다. “Add”를 두번 써야 하기에 오타가 생길 가능 수 있습니다.

Reader는 Add()가 시작이 아닌 끝에 synchronized 된다고 알게됩니다.

Python은 그러므로 Decorator syntax를 제공하고, 이를 통해 아래와 같이 더 간결하게 만들 수 있습니다.

{코드}




Decorators가 실패하는 시점: 코드를 부를때




Decorator의 문제는 Decorated Function(Decorator가 적용된 함수)의 호출을 원하는 Programmers의 요구를 만족시키지 못하는 것 입니다.

ExampleSynchronizedClass 의 User에게 당신은 Editor 나 IDE가 add의 docstring을 보이고, 적절한 signature를 발견하는 것을 원합니다.(?)

당신이 작성한 Documentation이나 코드로 부터 자동으로 생성된 API reference가 있으면 더 그렇죠.(?)



그런데 사실, signature, name dockstring과 같은 것을 얻는 것은 Wrapper function을 위함입니다.

{코드}

이것을 해결하기 위해 Python은 functools.wraps 라는 utility decorator를 제공하는데요, 이것은 wrapped fucntion의 name이나 docstring같은 attributes를 복사합니다.

Decorator의 구현을 변경해봅시다.

{코드}

그러면 우리는 더 좋은 help를 얻을 수 있죠.

{코드}

3.4 이전 버전의 Python의 signature는 아직 잘못되었습니다. 이것은 여전히 감싸진 함수가 아닌 Wrapper의 signature를 나타내죠.

만약 예전 버전의 Python을 지원하려고 한다면, 하나의 방법은 wrapt라는 3rd party library를 사용하는 것입니다.

functools.wraps대신 Wrapt 를 사용해서 Decorator를 다시 정의 해보죠.

{코드}

이를 사용해서 하위 버전 지원 뿐 아니라 약간의 간결함도 얻을 수 있습니다.




모든 Audiences 다루기


Functors.wraps와 wrapt의 trick을 쓰는 동안, 그들은 여전히 당신이 당신이 새 Decorator를 정의하는 모든 순간마다 그들을 사용하는 것을 기억하기를 원합니다.

아마 틀림없이 이는 Python 의 실수(?) 입니다. Library code가 이를 고치는 것에 의존하는 것 보다 더 좋은 것은 @ syntax를 python 언어 자신이 제공하는 것이죠.

당신이 library를 만들때, 혹은 심지어 programming language 를 디자인 할 때, 4가지의 audiences: The computer, authors, readers and callers를 지원하는 것은 언제나 가치있는 일입니다.

그리고 Decorator를 만드는 Python Programmer라면, wrapt를 사용하세요. 이는 caller와 reader를 더 행복하게 해줄 겁니다.

-----
뭔가 결론이 좀 이상하지만.. 여튼 도움이 되네요.

Django test에서 -s 옵션과 Encoding 문제

최근 직종을 변경하여 Django 를 공부하고 있습니다.

간단한 Test code를 돌리다가 우연히 발견한 문제가 있어 정리합니다.

다만, 끝까지 확인한 결론은 아니고 일종의 추측이 섞여 있으니 주의하세요.


문제: "manage.py test -s XXX" 와 같이 -s option을 주면 문제가 없는 Test case가 -s option을 빼면 에러가 발생.

우선 -s option이 하는 일은 이렇습니다.

-s, --nocapture       Don't capture stdout (any stdout output will be

                        printed immediately) [NOSE_NOCAPTURE]

stdout을 캡쳐하지 않는 옵션인데 이게 왜 영향을 주는 것일까요?

Test case의 문제 부분은 이렇습니다.

a = u'한글'
print(a.encode('utf8'))

그냥 유니코드를 프린트 하기 위한 문장으로 특별하지 않죠? (일반적으로 encode를 빼도 print가 알아서 잘해주지만 문제 발생을 위해 그냥 둡니다)

그런데 -s를 빼면 아래와 같은 에러가 발생합니다(일부 내용은 지웠습니다)

  File "***/lib/python2.7/site-packages/nose/plugins/capture.py", line 125, in _get_buffer

    return self._buf.getvalue()

  File "***Python.framework/Versions/2.7/lib/python2.7/StringIO.py", line 271, in getvalue

    self.buf += ''.join(self.buflist)

UnicodeDecodeError: 'ascii' codec can't decode byte 0xea in position 0: ordinal not in range(128)

StringIO가 문제군요-

알아보니 StringIO는 일종의 버퍼로 많이 쓰는데요, 유니코드 처리에도 문제가 없습니다.(cStringIO는 유니코드에 문제가 있습니다)

다만, 유니코드와 ascii가 섞일 경우가 문제가 생기는데요, 제가 생각하는 문제의 원인이 이 부분 입니다.

-s를 빼면 caputure를 위해 capture.py의 다음의 코드가 동작하는 것 같습니다.

    def start(self):

        self.stdout.append(sys.stdout)

self._buf = StringIO()

        sys.stdout = self._buf

문제는 기본 sys.stdout의 encoding이 ascii인 경우이고 제 경우 실제 기본 값이 ascii로 되어 있었습니다.

때문에 StringIO로 열어둔 스트림의 중간에 unicode와(제가 원하는 테스트코드의 인코딩) ascii(stdout의 기본 인코딩)이 섞이면서 상기와 같은 에러가 발생한다고 추측(!) 했습니다.

pdb까지 찍어서 확인하고 싶었지만, 왜인지 pdb를 붙이면 에러가 나고 또 원래 하려던 일도 아니기에 이정도 추정을 하고 본 글을 정리합니다.

구간 최소 트리(Range minimum query)

알고스팟의 MORDOR 풀기 위해 '구간 최소 트리'(이하 RMQ)를 구현했습니다.

RMQ에 관해서 간략하게 설명하자면,

'특정 구간에서 최소값은 무엇인가?' 에 대한 답을 구하기 위해 binary tree를 응용해서 최소값을 구할 수 있는 tree를 미리 구현하고 이를 활용하는 것입니다.

예를 들면 0~9까지 10개의 길이를 가지는 어떤 배열에서 다음의 질의(Query)에 답할 수 있습니다.

0~5 중 가장 작은 값은?
2~9 중 가장 작은 값은?

subarray의 min으로도 처리 할 수 있는데, subarray 생성시간 + min 연산시간(O(n)) 이 소모되는 반면, 이미 구성해둔 tree에서의 search 는 O(logn) 의 시간에 답을 구할 수 있습니다.

기본 원리는

1. 각 구간을 binary tree로 쪼갬
2. 각 구간 중 가장 작은 값을 저장

위의 예에서 다음과 같은 값들이 저장됩니다.

0~9: 가장 작은 값
0~4: 가장 작은 값, 5~9: 가장 작은 값
0~2: 가장 작은 값, 3~4: 가장 작은 값, 5~7: 가장 작은 값, 8~9: 가장 작은 값
각각의 leaf에는 자기 자신 저장

이와 같은 형태로 구성됩니다.

Query로 구간(Range)를 받으면, 생성된 Tree에서 어떤 Node가 필요한지를 알아낸 뒤에 그 중 가장 작은 값을 Return 합니다.
예에서 0~5라면 0~4의 최소 값를 저장한 노드와 5 (는 하나니까)노드가 필요합니다.
이 중 작은 값을 Return 하면 됩니다.

이런 알고리즘의 구현이 '알고리즘 문제해결 전략' 책에는 C로 되어 있는데, 그냥 Python 으로 옮겼습니다.

여기에는 Binary Tree 구현을 위해 Array를 사용했는데요, Left와 Right를 odd, even으로 mapping 시켰습니다. 비교적 꽉 찬 이진트리의 경우 이렇게 구현하는 것이 메모리를 좀 더 효율적으로 쓴다고 하니 참고하세요.

Array의 길이는 주어진 n과 가장 가까운 2의 제곱 수에 2를 곱한 만큼입니다.

가령 n = 6이면 가장 가까운 2의 제곱 수인 8(2^3) 에 2를 곱한 16입니다.

구현에서는 이것이 귀찮으므로 넉넉하게 계산했습니다.

#!/usr/bin/python
import sys

class RMQ(): #Range Minimum Query
    RMList = []
    length = 0

    def __init__(self, targetList):
        self.length = len(targetList)
        self.RMList = [""]*self.length*4
        self.init(targetList, 0, self.length-1, 1)

    def init(self, targetList, left, right, nodeIdx):
        if left == right:
            self.RMList[nodeIdx] = targetList[left]
            return targetList[left]

        mid = (left + right) / 2
        leftMin = self.init(targetList, left, mid, nodeIdx*2) # left idx is even number
        rightMin = self.init(targetList, mid+1, right, nodeIdx*2+1) # right idx is odd number
        self.RMList[nodeIdx] = min(leftMin, rightMin)
        return self.RMList[nodeIdx]

    def _query(self, left, right, nodeIdx, nodeLeft, nodeRight):
        if right < nodeLeft or nodeRight < left: return sys.maxint
        if left <= nodeLeft and nodeRight <= right: return self.RMList[nodeIdx]

        mid = (nodeLeft + nodeRight) / 2
        return min(self._query(left, right, nodeIdx*2, nodeLeft, mid),
                   self._query(left, right, nodeIdx*2 + 1, mid+1, nodeRight))

    def query(self, left, right):
        return self._query(left, right, 1, 0, self.length - 1)

책의 구현이 워낙 깔끔해서 더 수정할 부분은 없는 것 같습니다.

다만 이렇게 구현하고, 문제를 도전(!!!) 했으나 시간초과.......

보니까 C,C++,Java 만 문제를 풀었더군요-

pypy로도 안되는 것을 보면, 아무래도 Python 으로는 한계가 있는게 아닐까 싶습니다.

좀 더 빠르게 하는 방법이 있으면 생각해봐야죠-

N까지의 소수 검사할때 N의 제곱근(square root of N) 까지만 하는 이유

N까지의 소수 검사 관련 코드를 조금 더 빠르게 하는 여러가지 방법이 있습니다.

그중 이해하기 쉬운 테크닉(?) 중 하나가 N까지 검사하지 않고 N의 제곱근( square root of N) 까지만 검사하는 것인데요, 코드로 설명하면 다음과 같습니다.

def isPrime(n):
    if n == 1: return False
    if n == 2 or n == 3: return True
    if n%2 == 0: return False
    for i in xrange(3, int(n**0.5)+1, 2):
        if n%i == 0:
            return False
    return True

이것이 성립하는 이유가 좀 궁금해져서 알아보고 생각해봤습니다.

어떤 수 n이 1과 자신이 아닌 두 수의 곱으로 되어 있다고 생각해봅시다. (즉, 소수가 아님)

n = a*b 이고 n' 은 n 의 제곱근이라고 표현합시다.

여기서 만약,

a >= n' 이면, a*b = n = n'*n' 이므로 b<=n' 가 됩니다.

따라서 n' 까지만 검사를 하면 합성수를 이루는 a, b 중 작은 수(위에서는 b)까지는 충분히 체크할 수 있고, 합성수가 존재하지 않으면 소수라고 할 수 있습니다.

List에서 두 원소와 두 원소 사이의 길이를 합을 cost로 할때 최대값 구하기

간단한 문제 풀일이 있었습니다.

List가 있을 때,

value1 + value2 + abs(index(value1) - index(value2))

의 최대값을 구하는 문제!

그냥 전부 다 해보는 취지로 다음과 같이 처음에 접근했습니다.

    def oriSolution(self, A):
        r = -1000000001
        l = len(A)
        if l == 1: # length is 1
            return 0

        for P in range(l):
            for Q in range(P+1, l):
                t = A[P] + A[Q] + (Q-P)
                r = max(r, t)
        return r

특별할 부분은 없는데, O(n^2) (등차수열의 합이니 아마)의 연산비용이 나오는게 영 꺼림직 해서 고민을 좀 해봤습니다.

현재의 최대값인 r(그러고보니 변수 이름이 적절하지 않네요)을 갱신하는 알고리즘인데,

안쪽의 Loop를 생략 할 수 있는 case가 생길 것 같았습니다.

우선 cost는 위에 기술된 것처럼 A[P] + A[Q] + Q-P (항상 양수) 로 기술됩니다.

현재의 최대값이 만약 A[P] + A[Q] + Q-P 에 의해 갱신이 되는 경우에만 안쪽 loop가 유효 하겠죠.

때문에 이걸 생략 할 수 있는 case를 만들었습니다.

현재의 최대값을 curMax 라고 하면,

curMax <= A[P] + A[Q] + (Q-P) 이면 의미가 있습니다.

이는,

curMax - A[P] - (Q-P) <= A[Q] 

으로 표현이 가능한데요, 만약 Q를 확인하지 않아도 이를 만족하지 않음이 자명하다면 안쪽 loop는 생략해도 괜찮습니다.

이를 위해 최대값을 미리 구해둡니다. (max(A)인데 O(n)의 비용으로 구해집니다. 1번만 하면 되므로 그리 큰 비용은 아닙니다)

curMax - A[P] -(Q-P) 가 만약 리스트 전체에서 가장 큰 값보다 크다고 하면, 

즉, curMax - A[P] - (Q-P) > maxValue 이면

curMax - A[P] -(Q-P) <= A[Q]

는 언제나 틀립니다.

따라서 curMax - A[P] - (Q-P) > maxValue 인 경우는 안쪽 Q loop는 돌지 않아도 됩니다.

여기서 Q-P 계산에 Q 가 사용되어서 문제인데,

Q-P의 최대값은 List의 길이를 넘지 않으므로 그냥 l로 치환합니다. 이렇게 해도 논리적 흐름에는 영향이 없으므로 괜찮습니다.

코드는 이렇습니다.

    def betterSolution(self, A):

        r = -1000000001

        l = len(A)

        if l == 1: # length is 1

            return 0

        maxV = max(A)

        for P in xrange(l):

            if r - A[P] - l > maxV:

                continue

            for Q in xrange(P+1, l):

                t = A[P] + A[Q] + (Q-P)

                r = max(r, t)

        return r

별거 아닌 변화 같지만, random한 case에서 속도 향상이 유의미 하네요.

        A = []

        for _ in range(5000):

            A.append(random.randint(1,1000))

        startTime = time.time()

        self.assertTrue(P().betterSolution(A))

        print("{0}: {1}".format("Better", time.time() - startTime))

        startTime = time.time()

        self.assertTrue(P().oriSolution(A))

        print("{0}: {1}".format("Ori", time.time() - startTime))

        self.assertEquals(P().oriSolution(A), P().betterSolution(A))

와 같은 test code에서

Better: 0.205455064774

Ori: 1.86105298996

의 결과가 나오네요.

혹시 잘못생각한 부분이 있다면 comment 주세요 :)

jws rbtree 분석(작성중..)

Python 의 RBTree에 대해 파악하다 http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx 를 알게되었습니다.

유용한 내용이 많아 찬찬히 업데이트 합니다.

1. Left, Right 대신 0, 1

left, right 표현 대신 0, 1을 쓰는 저자의 코드도 흥미롭네요.

/* Classic binary search tree insertion */
struct cbt_node *cbt_insert(struct cbt_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else if (data < root->data)
    {
        root->left = cbt_insert(root->left, data);
    }
    else
    {
        root->right = cbt_insert(root->right, data);
    }

    return root;
}

/* Julienne Walker's binary search tree insertion */
struct jsw_node *jsw_insert(struct jsw_node *root, int data)
{
    if (root == NULL)
    {
        root = make_node(data);
    }
    else
    {
        int dir = root->data < data;

        root->link[dir] = jsw_insert(root->link[dir], data);
    }

    return root;
}

가독성을 조금 희생시킨 것 같지만 라인수를 많이 줄여줍니다. 내용을 이해한다면 사실 가독성이 많이 떨어진다고 하기도 애매하네요 ㅎㅎ

python에서도 무리 없이 써먹을 수 있을 것 같습니다.

가령

>>> (1>0) == (True)
True
>>> (1<0) == (False)
True
>>> (1>0) == (1)
True
>>> (1>0) == (0)
False
>>> (1<0) == (0)
True
>>> (1<0) == (1)
False

좋네요

Python 의 RBTree

손고리즘 스터디에서 재경님이 알려주시길 C++에서는 Map이 RBTree로 되어 있으나 python 은 RBTree 구현체가 없다고 합니다.

C/C++이랑 Python이 결속력(?)이 좋아서 특별히 안만든게 아닐까 하는 생각도 있지만, 뭐 일단 좀 의문이네요-

그래서인지 Tree 구현체가 많이 있는데, pip를 통해 쉽게 설치 할 수 있는 bintrees가 유용한 것 같습니다.

어떻게 RBTree를 구현했는지 코드를 좀 파악해야겠네요 :)

https://github.com/doctorpangloss/bintrees