배열내에서 N번째로 가장 작은(또는 큰) 원소값 찾기

오랜만에 글을 좀 올려보게 되었네요. 얼마전에 IDL Datapoint 블로그에 "Finding the Nth ordered element in a large array"라는 제목의 글이 올라왔었습니다. 주제는 어떤 배열내의 원소값들을 올림 또는 내림 차순으로 순서매김(Sorting)을 한 다음에 N번째에 해당되는 원소값을 찾는 효율적인 방법에 관한 내용입니다. 그리고 이 글과 관련해서 IDL계의 고수들 중 한 분인 Michael Galloy 선생께서 "내가 더 효율적인 방법을 갖고 있다"라는 댓글을 달고 본인이 개발한 코드를 소개하기도 하였는데요. 이 내용들을 정리해서 올려볼까 합니다.

원래 이와 같은 작업을 하는 방법 자체는 간단합니다. 배열에 대하여 소팅(Sorting)을 먼저 수행한 다음, 원하는 번째에 해당되는 값을 찾기만 하면 됩니다. 그래서 다음과 같은 IDL 코드로 쉽게 해결이 가능합니다.

function ordinal_1, array, N

 compile_opt idl2,logical_predicate

 s = sort(array)

 return, array[s[N]]

end

그런데 이 코드를 활용해서 5000X5000의 크기를 갖는 배열내에서 123456번째로 작은 값을 찾는 작업을 다음과 같은 방법으로 시도해보면, 값은 잘 찾아지는데 시간이 좀 걸립니다. 컴퓨터 사양에 따라 다르겠지만 지금 이 글을 작성하고 있는 제 구닥다리 컴에서는 약 5.6초 정도가 걸리더군요. 결코 짧은 시간은 아닙니다. 만약 이런 작업을 반복적으로 수행해야 하는 경우라면 누적되는 소요시간이 엄청날 수도 있습니다.

IDL> a = total(read_image(filepath('ohare.jpg',subdir=['examples','data'])),1)

IDL> tic & x = ordinal_1(a, 123456) & toc & print, x

이렇게 시간이 많이 걸리는 근본적인 이유는 소팅(Sorting)이란 작업 자체에 소요되는 시간이 상당하기 때문입니다. 그래서 좀 더 효율적인 방법으로 제시될 수 있는 것이 바로 MEDIAN 함수를 잘 활용하는 방법인데요. IDL Datapoint 블로그의 원문에는 코드의 내용이 다 나와있지만 여기서는 내용을 그대로 보여드리지는 않고 그냥 코드(ordinal_2)만 첨부하겠습니다. 하여간 이 코드를 사용해서 같은 작업을 다음과 같이 수행해보면 소요시간이 상당히 단축되는 것을 확인할 수 있습니다. 제가 해보니까 1초 정도 걸리더군요. 즉 5배 이상의 성능 향상이 있습니다. 꽤 괜찮은 편이죠.

IDL> tic & x = ordinal_2(a, 123456) & toc & print, x

그런데 이 글에 대하여 Michael Galloy 선생께서 "내가 HISTOGRAM 기반의 좀 더 효율적인 해결책을 갖고 있다"라는 댓글을 달고 관련 내용에 대한 링크를 함께 올리셨더군요. 실제 그 코드의 내용을 보면 HISTOGRAM 함수를 적절히 사용하여 효율을 높이는 방식으로 코딩이 되어 있는데, 이 파일도 제가 함께 첨부해놓았습니다. 그리고 다음과 같은 방식으로 테스트를 해본 결과, 위의 ordinal_2보다도 빠르게 실행이 되더군요. 제가 해보니까 0.46초 정도가 걸려서 약 두 배 정도의 성능 향상이 있는 것으로 확인이 되었습니다. 처음에 소개된 ordinal_1과 비교하면 10배 이상의 성능 향상이 있다는 얘기가 됩니다. 이 정도면 아주 훌륭한 셈입니다.

tic & x = mg_n_smallest(a, 123456) & toc & print, x[123455]

지금까지 언급된 IDL 코드들 및 관련 게시물 원문 링크를 아래에 함께 올려봅니다.

ordinal_1.pro

ordinal_2.pro

mg_n_smallest.pro

IDL Datapoint 블로그의 원문 링크

Michael Galloy 블로그의 원문 링크

ordinal_1.pro

0.0MB

mg_n_smallest.pro

0.0MB

ordinal_2.pro

0.0MB