잘 알려진 소팅 방법중에 max sorting이란게 있습니다. 

정렬되지 않은 데이터 n건을 소팅해서 상위 m건만 쓰려고 할 때, 

솔직히 전부 소팅할 필요가 없죠. 

그래서 사이즈가 m인 버킷을 만들고

n건의 데이터를 한번 스캔해서 필요한 m건의 소팅된 데이터를 얻는 소팅 알고리즘입니다. 

방법은 아주 간단합니다. 사이즈가 5인 버킷에 예를 들어

12, 6, 3 

이렇게 3건 들어가 있다고 할 때, 

n건 데이터에서 다음 데이터 값이 '5'이면 

'3'을 한칸 밀고 그 자리에 넣으면 됩니다. 

이런 연산을 하려면 '5'가 들어갈 위치를 순차탐색을 하던가 이진탐색을 해서 찾아낸 다음

그 위치에 insert하면 됩니다. (배열인 경우 memmove를 쓰면 되죠)

이런 알고리즘은 가끔 

document - terms 매트릭스에서 문서간 유사도를 계산하는데

어떤 하나의 문서와 가장 유사한 상위 m개의 문서를 찾아내는데도 쓰입니다. 

방법은 max-sorting되 비슷합니다. 그래서 저는 이걸 

max-clustering이라고 부르기로 했어요. 

document - terms 매트릭스는 사실  term의 존재유무를 bi setting으로 표현하는 bitmap을 가지는 node의 배열 정도가 될겁니다. 

linked list도 좋구요. 

또, 이 node는 각각 현재 node와 가장 유사한 다른 노드들 상위 m개를 저장할 수 있는 버킷을 가지고 있어야 합니다. 

이런 구조상에서 max-clustering 알고리즘을 구현하게되면

처리 시간은 대략 

n개의 node들간의 유사도 계산 횟수 = ( ( n * ( n + 1 ) )  / 2 )

두개의 node 사이의 유사도 계산 시간 = a

두개의 node에 대해서 각각 서로간의 max-sorting 시간 = 2*b

위 수치들을 전부 곱한 값 정도 걸리게 됩니다. 

약 1만개의 node에 대해서 상위 10개 정도 유사한 node들을 계산할 때, 대략 100초 정도 걸리게 되네요. 

좀더 빠르게 하고 싶지만, 일단 작업을 끝내니 귀찮아졌습니다. -_-;