Attribution/Share Alike 2.0 license몇일 전(어제였나?^^;) 친구에게도 했던 말이다.
일반적으로 귀차니즘에 의해 코딩을 하게 되면 복잡도가 O(n)이 되는 것 같다.
왜? 속도에 신경을 안쓰니까.
linkedlist도 신경안쓰고 짜면 원소 추가의 속도가 O(n)이 되버린다.
이걸 원소 나열이나 검색과 같이 사용한다면.. O(n^2)이 되버리니 끔찍하다.
그렇다면 어떻게 속도를 빠르게 할 수 있을까?
마지막 노드 뒤에 값을 추가하고 싶으면 처음부터 마지막 노드를 찾을 게 아니라 마지막 노드를 미리 저장해놓는것이다.
그러면 마지막까지 가지 않아도 되니 O(1)의 속도가 나온다.
즉, 현재 상태를 저장하는 방법이 있다는 것이다.
(전혀 쌩뚱맞은데다가 비유가 되지 않는 말이겠지만.. 프로그램이 실행 될 때 레지스터 값 등의 context를 저장한 뒤 context switching을 통하여 다중 프로세스를 실행하기도 한다. 이렇게 저장하듯이 자주 사용되는 데이터들의 값을 backup해놓으면 속도가 향상된다는것이다. 아무래도 이건 비유가 엉성하다 -ㅅ-)
김상형-API프로그래밍 #2 책을 보면, 당근이라는 프로그램을 만들면서 속도에 대한 이야기가 나온다.
글꼴 정보를 얻기 위해 연산하는 overhead가 매우 크므로 이것을 배열에 저장해두면 몇 KB를 소비하면서 속도는 굉장히 빨라진다고. (책에서 아마 5배 빨라진다고 했던 것 같다.)
sin도 마찬가지로, sin값을 미리 구해놓으면 CPU입장에서 손이 많이가는 float연산을 줄일 수 있으니 많이 빨리질 수 있다.
그냥 볼 땐 정말 당연하지만.. 실제로 코딩할 때 간단한 루틴임에도 불구하고 O(1)의 속도를 보장하지 못한다면..
게다가 자주 사용되는 루틴이라면.. O(n^3) 이상이 될지도 모른다.
문득 O(1)이 될 수 있는 O(n) 코드를 보면서 적는다. API나 함수는 잘 생각해보고 짜자.
일반적으로 귀차니즘에 의해 코딩을 하게 되면 복잡도가 O(n)이 되는 것 같다.
왜? 속도에 신경을 안쓰니까.
linkedlist도 신경안쓰고 짜면 원소 추가의 속도가 O(n)이 되버린다.
이걸 원소 나열이나 검색과 같이 사용한다면.. O(n^2)이 되버리니 끔찍하다.
그렇다면 어떻게 속도를 빠르게 할 수 있을까?
마지막 노드 뒤에 값을 추가하고 싶으면 처음부터 마지막 노드를 찾을 게 아니라 마지막 노드를 미리 저장해놓는것이다.
그러면 마지막까지 가지 않아도 되니 O(1)의 속도가 나온다.
즉, 현재 상태를 저장하는 방법이 있다는 것이다.
(전혀 쌩뚱맞은데다가 비유가 되지 않는 말이겠지만.. 프로그램이 실행 될 때 레지스터 값 등의 context를 저장한 뒤 context switching을 통하여 다중 프로세스를 실행하기도 한다. 이렇게 저장하듯이 자주 사용되는 데이터들의 값을 backup해놓으면 속도가 향상된다는것이다. 아무래도 이건 비유가 엉성하다 -ㅅ-)
김상형-API프로그래밍 #2 책을 보면, 당근이라는 프로그램을 만들면서 속도에 대한 이야기가 나온다.
글꼴 정보를 얻기 위해 연산하는 overhead가 매우 크므로 이것을 배열에 저장해두면 몇 KB를 소비하면서 속도는 굉장히 빨라진다고. (책에서 아마 5배 빨라진다고 했던 것 같다.)
sin도 마찬가지로, sin값을 미리 구해놓으면 CPU입장에서 손이 많이가는 float연산을 줄일 수 있으니 많이 빨리질 수 있다.
그냥 볼 땐 정말 당연하지만.. 실제로 코딩할 때 간단한 루틴임에도 불구하고 O(1)의 속도를 보장하지 못한다면..
게다가 자주 사용되는 루틴이라면.. O(n^3) 이상이 될지도 모른다.
문득 O(1)이 될 수 있는 O(n) 코드를 보면서 적는다. API나 함수는 잘 생각해보고 짜자.
