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

Python django

예전에 개인적인 호기심으로 잠깐 만저본 django.

이번에도 호기심 차원에서 조금 더 만져보고 있다. 전에 기억이 하나도 안나서 아예 처음부터 하는 기분인데, 참 잘 만들어진 것 같다.

생산성이 수십배 오르는게 당연하겠구나.

Python lambda function 과 unittest

수학식이 좀 많이 나오는 것 같은 문제를 풀다보니 아래와 같은 함수를 만들 일이 생겼습니다.

    def getFunction(self, c1, c2):
        x1 = c1[0]; y1 = c1[1]
        x2 = c2[0]; y2 = c2[1]
        if x1 == x2:
            return (lambda x,y: x1)
        if y1 == y2:
            return (lambda x,y: y1)
        return (lambda x,y: (y1-y2)/(x1-x2)*x + y1 - (y1-y2) / (x1-x2)*x1)

두 점을 지나는 직선을 구하는 함수로 함수 자체를 리턴시키기 위해 lambda를 사용했습니다.

보통 TDD를 하기에 TestCase를 만들긴 했는데, 생각보다 고민이 되더군요-

"기대값을 뭘해야 하지?"

종이에 쓰는경우면 쉽습니다.

가령 (0,0), (1,1)을 지나는 함수 f(x)는 이렇게 되겠죠.

f(x) = x

unittest에 넣는다고 치면(당연히 안되지만)

assertEquals(f(x) = x, getFunction((0,0), (1,1)))

과 같은 포멧이 될텐데 기대값에 f(x) = x 와 같은 형태는 둘 수 없습니다.

String 으로 뽑아도 당연히 저렇게 나타나지 않구요-

일단 대안으로는 기대함수(편의상)에 값을 넣었을 때 올바르게 나오는지 검사하도록 했습니다.

다음과 같네요.

        # y = 2*x function

        F = Treasure().getFunction((0,0), (1,2))

        self.assertEquals(0, F(0,2))

        self.assertEquals(2, F(1,2))

        self.assertEquals(10, F(5,10))

대략 적으로 검출은 되는데, 영 찝찝합니다.

뭔가 lambda function 을 unittest에서 적절하게 검출하는 방법이 있으면 좋을 것 같습니다.

검색을 좀 해보니 eval을 만들어 string으로 비교하는 방법도 있는 것 같은데, 이정도가 최선일까요? 고민해봐야겠네요 ㅎ

정리

정리를 그렇게 잘하지는 못하는 것 같습니다.

블로그도 그렇고 메모도 그렇고.

그래도 일단 쓰는게 안쓰는 것보단 좋겠져.