알고리즘

• 제네릭 프로그래밍
• 크리스마스 강연
• P-NP
• Big O
• Viterbi algorithm
• Hidden Markov Model(HMM)
• String Manipulation
  • Aho Corasick
• 무작위성
• 기타
• 링크

제네릭 프로그래밍

제네릭 프로그래밍이란 대부분의 일반적인 설정에서 효율 저하 없이 작동할 수 있도록 알고리즘과 자료구조를 설계하는 데 초점을 맞춘 프로그래밍에 대한 접근법이다. (알고리즘 산책, 2015)

크리스마스 강연

2008년, 나는 1826년 마이클 패러데이가 첫 연사로 나선 왕립 연구소 크리스마스 강연(Royal Institution Christmas Lectures)의 180번째 연사로 선발되는 행운을 누렸다. 2008년 당시 나의 강연은 컴퓨터과학이란 주제로 진행된 최초의 강연이었다. 강연을 준비하며 컴퓨터과학을 일반 대중에게 설명할 방법을 고심하느라 많은 시간을 쏟았지만, 활용할 자료가 거의 없고 이런 필요를 다루는 대중 서적 또한 거의 전무하다는 사실을 깨달았다. 따라서 금번 맥코믹의 새 책 출간은 내겐 더욱 환영할 만한 일이다. (미래를 바꾼 아홉 가지 알고리즘, 2011)

크리스 비숍이 추천사에서 언급한 2008년 강연 영상

P-NP

• P: Polynomial Time 다항식 시간 동안 ‘답을 해결할 수^{can provide an answer} 있는’ 문제. 해결 문제.
• NP: Non-deterministic Polynomial Time 다항식 시간 동안 ‘주어진 답이 맞는지 확인할 수^{can be verified} 있는’ 문제. 검산 문제.

NP는 하나의 경우에 대해서 옳은지 그른지 보는 것이고, P는 해답이 되는 경우를 찾을 때 까지 모든 경우에 대해 옳고 그름을 따지는 것. P-NP 문제의 가장 중요한 쟁점은 수학적 귀납법으로 경우의 수를 P의 영역으로 넣을 수 있는지의 여부를 묻는 것으로 볼 수 있다. 대표적인 예로, 정렬 문제의 경우 경우의 수가 \(n!\) 이지만, 이미 수학적 귀납법으로 \(O(n^2)\) 나아가 \(O(n\log{n})\)으로 수렴된 바 있다. ref

A polynomial is a linear combination of terms that look like Constant * x^k. On the opposite, exponential means something like k^x, where in both case k is a constant and x is a variable. ref

Big O

Big-O 표기법은 다음 수식으로 표현될 수 있다.

O(f(n)) = s + C * f(n) + t

s는 작업 준비 시간이고, C는 비례 상수, t는 작업 정리 시간이다. 어떤 알고리즘에는 s, C, t들이 굉장히 큰 값일 수 있는데, 그런 경우 s+t가 C*f(n)을 압도할 수 있다. (전문가를 위한 C++, 2011)

Viterbi algorithm

mini example를 구현했다. \delta_3 의 값이 A, B 모두 잘못되어 있으며, (5) 수식이 잘못 표기되어 있다.

알고리즘을 Python으로 구현했을때, brute force 방식으로 전부 계산했을때 맥북 기준 30초가 넘어간다. DP를 적용해 max_delta_tr를 구하여 \psi를 위한 max 값을 기억하며 풀 경우 7초가 걸렸다.

성능 개선을 위해 동일한 알고리즘을 C++로 구현해봤는데, 65초로 훨씬 늦다. CPU 사용률은 100%를 넘지 못하며 이는 Python도 마찬가지다. 동일한 100%인데 일반적인 기대와 달리 심각한 성능 차이가 난다.

동일한 알고리즘을 Java로 구현하면 3초대에 실행된다. time값은 6.5초 정도가 출력된다.

6.46s user 1.17s system 167% cpu 4.561 total

Java는 별도 처리를 하지 않았음에도 불구하고 CPU 사용률이 180%를 넘어간다. CPU 코어를 고르게 활용하는 것으로 보이며 일부 null 처리를 하여 계산 횟수도 C++에 비해 조금 적긴 하나 이 부분이 중요한 것 같진 않다.

Java가 가장 빠르고 Python, C++ 순이다. 일반적으로 가장 빠를 것으로 예상되는 C++가 비교가 무색할 정도로 성능이 낮다. 멀티 쓰레딩으로 개선이 될 것으로 보이나 아쉽게도 시도 해보진 못했다.

Viterbi는 단순 행렬 연산의 반복이다. 논문과 달리 stack underflow를 방지하기 위해 log로 합산했으며, 0 일때도 이후 계산을 잇기 위해 라플라스 스무딩 처리를 했다.

C++에서 std::map을 std::unordered_map으로 바꾸는 것만으로 한 문장에 7.38s가 걸리던 것을 2.55s로 줄일 수 있었다. 34% 수준으로 줄었으므로, 위 결과는 22s가 될 것으로 예상된다. 물론 그래도 느리기 때문에 좀 더 최적화는 필요하다.

Hidden Markov Model(HMM)

HMM은 1960년대 후반 Leonard E. Baum의 통계 논문에서 사용. 1970년대 중반 음성 인식에서 처음 적용.

1. 관찰 결과 시퀀스가 나타날 확률(Evaluation)
2. 관찰 결과 시퀀스를 보고 은닉 상태의 시퀀스 찾기(Decoding), HMM의 핵심. Most common decoding algorithms for HMMs is the Viterbi.

¹

String Manipulation

Aho Corasick

아호 코라식 알고리즘은 finite set of strings의 요소를 찾는 일종의 사전-매칭 알고리즘으로, 동시에 모든 문자열을 찾는다.

문자열은 중복 순열^{Permutations with repetition}이므로 \({k^n}\) 가 가능하다. (k elements, length n) 모든 위치에 가능하므로 문장의 길이인 (256 - 패턴 길이 n) * 패턴의 갯수 1,000,000개를 분자로 하여 \({k^n}\) 분모로 나누면 매칭 확률을 구할 수 있다. C++구현에 버그가 있었고 직접 패치했다.

첫 실행시 트라이^tries를 메모리에 읽어들이는 시간이 다소 걸리지만 이후 문장 부터는 비교가 필요 없을 정도로 빠른 성능을 보여준다. 대부분의 문장이 1~2ms 이내에 처리된다.

무작위성

가상의 동전 던지기를 수백만 번 했을 때의 결과처럼 편향이 없고 패턴이 나타나지 않는 난수를 컴퓨터나 기계장치로 만들어내는 것은 극히 어렵다. (뉴욕타임스 수학, 2013, 1988년 기사) 도널드 커누스의 책 『The Art of Computer Programming』 에서도 random에 대해 여러 챕터를 할애한다.

기타

DNA 프로파일링은 복잡함으로 인해 Approximation Algorithm 근사 알고리즘 사용 (넘버스, 2017)

링크

알고리즘 링크

Last Modified: 2021/07/09 11:35:13