20180405

오늘의 일기
* 이전에 급하게 작성하느라 linear search로 작성한 코드를 red-black tree로 변경했더니 100배 넘게 빨라졌다. Red-black tree를 적용할 때 가장 고민이 되었던 점은 원하는 문제를 어떻게 red-black tree로 풀 것인가였다.
– 각 엔트리는 unique한 키 A를 갖고 있고, 동시에 B라는 값을 갖고 있다(non-unique).
– 각 엔트리는 삽입/삭제가 발생한다.
– 각 엔트리에 대해 B값 업데이트가 빈번하게 발생한다.
– B 값의 global minimum값을 찾아야 하는데, 엔트리가 아주 많아서 선형 탐색은 느리다.
해당 문제에서 A를 red-black tree의 key로 쓰자니 B의 global minimum을 찾을 때 결국 선형 탐색을 해야 한다는 점이 문제였고, B를 key로 쓰자니 중복 값이 있어서 삽입/삭제시에 찾기 어렵다는 점이 문제였다. 결국에는 A와 B를 동시에 key로 사용해 문제를 해결했다. 조금 high-level에서 본다면 A와 B를 함께 사용하는 새로운 자료형을 정의한 것이다. B를 사용해서 트리에 삽입하되, 원하는 값을 갖는 sub-tree를 찾은 뒤에는 A를 사용해서 다시 key를 탐색해나간다. 이렇게 하면 unique한 key를 사용해서 삽입/삭제할 수 있고, min 값을 찾을 때에는 left-most node를 따라가면 된다.

Advertisements
Posted in 1) Memo
3 comments on “20180405
  1. heartinpiece says:

    sorting 되어있는건 binary search를 해도 비슷한 효과가 있지 않을끄아?

    허태경아~~~~ 힘들드아 ㅋㅋㅋㅋㅋ

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Recent Posts
누적 방문자 수
  • 142,141 hits
%d bloggers like this: