J2H's Blog: 5월 2016

2016년 5월 12일 목요일

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 주세요 :)

2016년 5월 10일 화요일

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

2016년 5월 2일 월요일

Python django

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

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

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