컴퓨터비전 숙제로 Component와 Boundary를 구하는 프로그램을 짰다.
Equivalent Table에서 동등한 값들 중 가장 작은 값을 찾을 때, set 써서 동등한 거 보이는 데로 insert해버리고..
set이 내부적으로 정렬해주니.. 그냥 맨 앞에 값 불러다 쓰면 되고.. 참 편하긴 하다..
그치만 set이 내부적으로 정렬해주는 것 때문에 추가된 것만 따로 검색하지 않고 다시 앞에 있는 것부터 테이블을 검색해서 다시 추가해주도록 했으니 여기서는 시간이 마이너스.
그리고 생각해보면 Equivalent table을 pair의 vector처럼 썼으니.. 결국 multimap쓰면 될 걸 링크드리스트에 직접 때려넣어서 순차검색하도록 구현했으니 여기는 구현면에서 마이너스.
게다가 multimap쓰면 table안의 label에 대해서 정렬되니까 안에 이미 있는지 찾는 것도 더 빠를텐데.. 그러므로 시간상으로도 마이너스.
음.. 그치만 오늘은 고치기 싫으므로 또 마이너스..-_-
<아래부터 추가>
multimap 쓰는 것으로 수정. 간단하다. multimap 안에 있는지 검색을 리스트를 순차검색하던 것에서 equal_range를 쓰므로 내부에서 더 빨리 찾을 것으로 생각한다.
근
데 과연 equivalent table 같은 걸 multimap 식으로 생각해도 될까. multimap 은 “키”에 연관하므로,
equilvalent 짝 중에서 한가지가 키가 됨을 강제한다. 둘은 동등하므로 어떤 것이 키가 될 지 사실 정할 수 없다. 난
짝 중에서 큰 값을 키로 잡았지만.. 작은 값을 키로 잡으면 작은 값이 반복되므로(connectedness를 찾는 과정에서
euilvalent table의 작은 label은 동등한 것들이 계속 나올테니까) 내부에서 트리를 이용한다면, 잘 분포되지 않을
거라는 가정에서.. 잘 분포된 트리가 검색시 더 빠를테니까..
트리로 구성되어 있을 거라는 가정은 Bjarne
Stroustrup의 “The C++ Programming Language(C++ 프로그래밍 언어)” 특별판의 17.4.1.1의
“대개 map은 형태는 조금씩 다를지언정 거의 다 트리로 구현되기 때문에, 반복자 역시 트리 횡단으로 원소 집합을 돌아다닌다.”
라는 구절(한글판 기준)에서 가정한다. 실제 확인은? ..글쎄;;
equivalent table에서 label을
찾을 때는 짝 중 아무값이나 맞으면 그 pair의 다른 짝을 equivalent set에 넣어주어야 한다. 양 쪽 둘다 중에
아무거나 맞는 것을 찾아야 하므로 결국 equivalent table을 모두 검색하도록 만들었는데, 이 걸 어떻게 더 효율적으로
할 수 있는 방법 없으려나.. 항상 모든 걸 다 찾아야 할까…