태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
2018.11.04 14:00


[실용주의 프로그래머] 알고리즘의 속도


big o notation, big o notation 단점, code profiler, combinatoric, Divide And Conquer, logn, nlogn, o(c^n), o(log(n)), o(n), o(nlog(n)), o(n^2), premature optimization, [실용주의 프로그래머] 알고리즘의 속도 (#32), 겹친 반복문, 라이브러리 성능, 리소스 big o notation, 반씩 잘라 나가기, 상식, 성급한 최적화, 입력의 크기, 조합적, 직접 실행 그래프, 추정을 테스트하라, 코드 프로파일러


-

실용주의 프로그래머가 거의 날마다 사용하는 추정이 있다.

알고리즘이 사용하는 자원, 곧 시간, 프로세서, 메모리 등등을 추정하는 것이 그것이다.

대문자 O 표기법(big O notation)이라고 불리는 근사값을 기록하는 방식을 이용하면 답을 찾을 수 있는 경우가 많다.



-

일반적으로 입력의 크기는 알고리즘에 영향을 준다. 입력의 크기가 클수록, 알고리즘의 수행시간이 길어지거나 사용하는 메모리 양이 늘어난다.



-

알고리즘과 시간의 상관관계가 선형적이라면(늘어나는 시간이 입력값과 비례한다면) 큰 상관이 없다.

그러나 알고리즘은 대개 선형적이지 않다.

선형보다 더 적은 경우도 있지만, 훨씬 많은 경우도 많다.



-

우리는 반복문이나 재귀 호출을 담고 있는 코드를 작성할때면 언제나 무의식적으로 수행시간과 메모리 요구량을 계산한다는 것을 깨달았다. 이것은 정식 계산이 아니고 주어진 환경에서 우리가 무리한 일을 하는 것은 아닌지 재빨리 확인해 보는 것에 가깝다.

상세한 분석을 해야 할 때는 O( ) 표기법이 쓸모 있다.



-

O( ) 표기법은 근사값을 다루기 위한 수학적 방법이다.

O 가 “… 차수로(order of)” 를 뜻한다고 생각하면 좋다.



-

O( ) 표기법은 우리가 측정하는 것(시간, 메모리, 기타 등등)의 상한값을 정하는 표기법이다.

상당히 복잡한 O ( ) 가 만들어지는 경우도 있는데, n 이 커질수록 가장 큰 차수에 비하면 다른 차수는 무시해도 될 정도이기 때문에, 관습적으로 최상위 차수를 제외한 다른 모든 차수는 제거하며, 상수 곱수도 표시하지 않는다.

이것이 O ( ) 표기법의 약점 가운데 하나이기도 하다.


어떤 O(n^2) 알고리즘이 다른 O(n^2) 알고리즘보다 천 배나 느릴지도 모르지만, 표기법으로는 그 사실을 알 수 없다.



-

O( ) 표기법은 시간에만 적용되지 않으며, 알고리즘이 사용하는 다른 어떤 자원(resource)을 나타낼 때도 이 표기법을 이용할 수 있다. 예를 들어, 메모리 소비를 모델링하는 데도 O( ) 표기법은 쓸모 있다.



-

상식을 이용해서 수많은 간단한 알고리즘들의 차수를 추정할 수 있다.


간단한 반복문(loop)

    간단한 반복문 하나가 1부터 n 까지 돌아간다면, 이 알고리즘이 O(n)일 가능성이 높다.


겹친 반복문

    반복문 안에 또 반복문이 들어 있다면, 알고리즘은 O(m X n) 이 되며, 여기서 m 과 n 은 두 반복문의 반복 횟수이다.

    이런 알고리즘은 O(n^2) 이 되기 쉽다.


반씩 잘라 나가기

    반복문을 돌 때마다 작업 대상의 수를 반으로 줄여 나가는 알고리즘이라면, 대수적 알고리즘, 즉 O(log(n)) 이 될 가능성이 높다.


나눠서 정복하기(divide and conquer)

    입력 데이터를 나눠서 각 반쪽에서 독립적으로 작업한 다음, 결과를 합치는 알고리즘은 O(nlog(n)) 이 될 수 있다.

    

조합적(combinatoric)

    알고리즘이 항목의 순열을 다루기 시작하면 거의 대부분의 수행시간은 걷잡을 수 없을 정도로 늘어난다.

    순열에는 factorial 이 관련되기 때문이다.

    이런 종류의 알고리즘의 수행시간을 줄이기 위해 휴리스틱이 동원되기도 한다.

    이런 것들은 O(C^n) 이 되곤 한다.



-

대개는 회사 안에서 정렬 루틴을 작성하는 데 시간을 많이 쓰게 되지는 않는다.

이미 나와 있는 라이브러리에 들어있는 정렬 루틴이 아마(상당한 노력을 들이지 않는 한) 여러분이 작성하는 것보다 성능이 좋을 것이다.



-

입력값의 숫자 값이 한정되어 있다면, 그 코드를 실행하는 데 시간이 얼마나 걸릴지 알 수 있다.

숫자가 외부 요인에 따라 달라진다면, 잠시 작업을 멈추고 커다란 수가 들어왔을 경우, 수행시간이나 메모리 소비에 어떤 영향을 미칠지 생각해 보는 것이 좋다.



-

여러분 알고리즘의 차수를 추정하라.



-

잠재적인 문제를 해결하기 위해 할 수 있는 몇 가지 방법이 있다.

O(n^2) 알고리즘이 있다면 O(nlog(n)) 으로 줄이기 위해 나누어 정복하는 divide and conquer 방법을 찾을 수 있는지 시도해본다.



-

코드의 실행시간이 얼마나 될지, 또는 메모리를 얼마나 사용할지 확실하지 않다면, 입력 레코드의 수나 혹은 런타임에 영향을 줄 것이라고 생각되는 어떤 요소든 바꾸어 가면서 직접 실행해보라. 그런 다음 결과를 그래프로 그려본다.

얼마 후면 그래프 선이 어떤 모양인지 감을 잡을 수 있을 것이다.

위로 솟아 올라가는 커브인가, 직선인가, 아니면 입력의 규모가 커질수록 기울기가 작아지는가? 점을 세번이나 네 번 정도만 찍어 보면 대략적인 답이 나올 것이다.






-

어떤 일을 하는 코드인지 코드 자체에 대해서도 생각해보라.

입력값 n 이 작을 경우, 단순한 O(n^2) 코드가 복잡한 O(nlog(n)) 코드보다 더 좋은 성능을 내기도 한다.

O(nlog(n)) 알고리즘에 무거운 내부 반복문이 들어있는 경우라면 특히 더 그러하다.



-

입력 데이터 집합이 작을 때는 수행시간이 선형적으로 증가하다가도, 수백만 개의 레코드를 입력하면 시스템이 버벅이기 시작하면서 갑자기 수행시간이 길어지기도 한다.

임의로 생성한 입력 키들로 정렬 루틴을 테스트하곤 했다면, 이미 정렬된 입력을 넣는 순간 놀라게 되는 일이 생길지도 모른다.

실용주의 프로그래머는 이론적 기반과 실무적 기반을 모두 고려하려고 노력한다.

추정을 이미 했다고 하더라도, 현장에서 실제 데이터를 입력받아 돌아가는 코드의 수행시간만이 정말로 의미있는 수치다.



-

여러분의 추정을 테스트하라.



-

정확하게 시간 재는 일이 어렵다면, 코드 프로파일러(code profiler)를 사용해서 알고리즘이 돌아갈 때 실행되는 각 단계의 반복 횟수를 센 다음, 입력값의 규모를 바꿔 가면서 나오는 값을 그래프로 그린다.



-

적당한 알고리즘을 선택할 때도 실용적이어야 할 필요가 있다.

가장 빠른 알고리즘이 언제나 가장 좋은 알고리즘은 아니다.

입력값의 규모가 작다면 단순한 삽입 정렬도 퀵정렬과 비슷한 성능을 내준다.

그러나 삽입 정렬을 작성하고 디버깅하는 데 걸리는 시간은 퀵정렬보다 적다.



-

성급한 최적화(premature optimization)을 조심하라.

어떤 알고리즘을 개선하느라 여러분의 귀중한 시간을 투자하기 전에 그 알고리즘이 정말로 병목인지 먼저 확실히 해두는 것은 언제나 좋은 생각이다.




댓글을 달아 주세요


Posted by 돼지왕왕돼지