Priority Queue와 전체 데이터 중 상위 n 개 선택하기
프로그래밍을 하다보면 가끔은 이런 문제에 직면합니다. 문제는 다음과 같습니다.
- 전체 데이터 중에서 상위 100개를 고르는 경우.
- 전체 데이터 중에서 100번째 데이터의 값을 알아야 하는 경우.
가장 단순한 답은, 전체 데이터를 정렬(sorting)한 후, 상위 100개를 순서대로 찾으면 됩니다. 전체 데이터 수가 작을 때는 어떤 방법을 써도 별 문제가 없습니다. 문제는 전체 데이터의 갯수가 매우 큰 경우입니다. 대략 1억개 정도라고 가정해 보겠습니다.
정렬에 n x log2(n) 정도의 시간이 걸립니다.
1억 x log2(1억) 정도의 시간이 걸리죠. 대략 27억 (= 1억 x 27) 정도의 시간이 걸리는군요.
다른 방법을 살펴보겠습니다.
어떤 자료 구조(data structure)가 있어서 자동으로 100개의 데이터를 관리해 준다고 가정합니다. 이 자료 구조는 새로운 데이터를 넣으면 100개 안에 해당하는지 아닌지를 판단해서 관리합니다. 그 시간이 얼마나 걸릴지는 모르겠지만, DT라고 하겠습니다.
그럼, 이런 데이터 구조를 이용한다면 시간이 얼마나 걸릴까요?
쉽죠. 1억 x DT입니다.
이런 수치가 나오는 이유는 다음과 같습니다.
1억은 모든 데이터의 갯수입니다. 그러니까, 모든 데이터를 최소한 한번은 봐야 한다는 뜻입니다.
DT는 하나의 데이터가 100번째 안에 드느냐 아니냐를 판단하기 위한 시간입니다.
즉, 1억개의 데이터를 다 보면서, 각각이 100번째 안에 드느냐 아니냐를 판단하는 시간이죠.
이제는 DT가 27보다 작냐 크냐만 알면 됩니다.
1. 어레이 (array) 사용
제일 단순한 방법은 그냥 어레이로 100개의 데이터를 관리하는 것입니다.
즉, 100개 크기의 어레이을 만든 후, 데이터가 들어올 때마다, 이 테이터가 100개 안에 들어오는가 아닌가를 판단하는 것이죠.
기존의 100개의 데이터 범위에 들어오면, 그 데이터를 넣고, 가장 작은 데이터를 버리면 됩니다.
안 들어오면, 즉 100등안에 들어오지 않으면 그냥 그 데이터를 버리면 됩니다.
한 번 계산해 볼까요.
100개의 데이터에서 그 데이터가 들어오는지를 판단하려면 1번만 비교하면 됩니다.
즉, 가장 작은 데이터보다 크냐 작냐만 판단하면 됩니다.
그 데이터가 작으면 그냥 버리면 됩니다. 하지만, 크다면...
기존의 데이터 중 가장 작은 것을 버리기고, 그 새로운 데이터를 적당한 위치에 넣어야 합니다.
그 시간은, log2(100) - 1 + 50이 걸립니다.
log2(100) - 1 은 그 데이터를 위치를 찾는 binary search의 평균 시간입니다.
50은 그 위치가 결정됐을 때, 그 뒤의 데이터를 쭈욱 밀어내는 평균 시간입니다.
평균이니까, 50번이 합리적입니다. 즉, 운이 좋으면, 1개의 데이터만 옮기면 되고, 운이 나쁘면 100개를 다 밀어야 하겠죠.
여기서, 100개를 밀어내는데 평균이 50이라면, 검색에서의 평균은 왜 log2(100) - 1 일까요?
그건 binary search의 특성때문에 그렇습니다.
1번에 데이터를 찾을 확율을 1/100입니다. 2번에 데이터를 찾을 확율은 2/100이고, 3번에 데이터를 찾을 확율은 4/100입니다.
이렇게 해서, 각 확율과 비교횟수를 곱해서 평균을 내면, 대략 log2(100) - 1이 됩니다. log2(100) / 2 가 아니라는 것이죠.
어레이에서 새로운 데이터를 중간에 삽입할 때 뒤의 데이터를 밀어내지 않고는 제대로 된 어레이를 유지할 수 없습니다.
예를 들어, 5개짜리 어레이를 보겠습니다. 내용은 다음과 같습니다.
50 40 30 20 10
여기에 45라는 데이터가 들어오면,
50 45 40 30 20 으로 만들어야 합니다. 그러려면, 45는 기존의 40자리에 들어가야 하고, 그 뒤로는 쭈욱 밀려서 데이터가 들어가야 합니다.
log2(100)은 대략 7입니다. 그럼, log2(100) - 1 + 50은 56이 되겠네요.
이 값은 27보다 두배 정도 큽니다.
즉, 이 방법은 정열해서 그냥 상위 100개를 고르는 방식보다 2배 정도 느리다는 것이죠.
다른 좋은 방법이 없을까요?
2. 링크드 리스트 (Linked List) 사용
링크드 리스트를 고려해 볼 수 있지만, 이 자료구조는 새로운 데이터의 추가 및 삭제는 용이합니다만 검색(search)에는 취약한 구조입니다. 링크드 리스트에서 원하는 데이터를 찾는 시간은 그 크기에 비례합니다. 그래서, 결국 DT는 평균적으로 50의 값을 갖습니다.
3. Heap 사용
Heap이라는 데이터 구조를 살펴보겠습니다. 여기서, heap은 Java에서의 메모리 덩어리나 C/C++에서 프로그래머가 정의한 데이터 영역을 의미하는게 아닙니다. 아래 그림은 heap의 젼형적인 형태입니다. 가장 위의 테이터가 가장 큽니다. 좌우의 데이터는 작습니다.이런 특징을 갖고 있습니다.
이 데이터 구조는 새로운 데이터를 적절한 위치에 넣을 때 시간이 log2(n) 밖에 걸리지 않습니다.
이 구조를 사용한다면, 1억개의 데이터에 대하여,
1억 x log2(100) 만의 시간이 걸려서, 100개의 상위 데이터를 고를 수 있습니다.
1억 x log2(100) 은 대충 1억 x 7입니다.
정렬하는 방식보다도 3~4배 정도 빠릅니다.
4. 다른 방법
다른 방법 하나는, 1억개의 데이터 중에서 가장 큰수를 고르는 것입니다. 그 다음에는 2번째로 큰 수를 고르고, 그 다음에는 3번째로 큰 수를 고르고, 이렇게 해서 100개의 데이터를 고르는 것입니다.
이 방식은, 1억 + (1억 - 1) + (1억 - 2) + ... + (1억 - 99) 의 비교가 필요합니다.
대충 계산하면, 100억 - 5000 이 됩니다. 대충 100억이 되는군요.
이슈 1
이 포스팅에서의 자료 구조 비교에는 이슈가 있습니다. 단위 operation에 대한 비용(cost) 계산이 빠져있습니다. 즉, 검색에서 비교하는 오퍼레이션 1개와 어레이에서 데이터를 옮기는 한개의 오퍼레이션이 같은 비용(시간)이라는 가정을 하고 있습니다.
이슈 2
이건 알고리즘, 자료 구조와 다른 이슈입니다.
어떤 데이터 구조를 사용하던지 간에, 잘 정리된 API는 의미를 갖습니다.
즉, 내부의 자료구조로 무엇을 사용하던, 아래의 API로 분리하여 개발을 하는 건 좋은 개발 습관이 될 것입니다.
void add(int data)
int[] get100()
실제로, add()의 구현 부분에서 어레이를 사용하던, 링크드 리스트를 사용하던, 힙을 사용하던, 외부에서 add()를 사용하는 방식에는 변화가 없게 됩니다.
- 전체 데이터 중에서 상위 100개를 고르는 경우.
- 전체 데이터 중에서 100번째 데이터의 값을 알아야 하는 경우.
가장 단순한 답은, 전체 데이터를 정렬(sorting)한 후, 상위 100개를 순서대로 찾으면 됩니다. 전체 데이터 수가 작을 때는 어떤 방법을 써도 별 문제가 없습니다. 문제는 전체 데이터의 갯수가 매우 큰 경우입니다. 대략 1억개 정도라고 가정해 보겠습니다.
정렬에 n x log2(n) 정도의 시간이 걸립니다.
1억 x log2(1억) 정도의 시간이 걸리죠. 대략 27억 (= 1억 x 27) 정도의 시간이 걸리는군요.
다른 방법을 살펴보겠습니다.
어떤 자료 구조(data structure)가 있어서 자동으로 100개의 데이터를 관리해 준다고 가정합니다. 이 자료 구조는 새로운 데이터를 넣으면 100개 안에 해당하는지 아닌지를 판단해서 관리합니다. 그 시간이 얼마나 걸릴지는 모르겠지만, DT라고 하겠습니다.
그럼, 이런 데이터 구조를 이용한다면 시간이 얼마나 걸릴까요?
쉽죠. 1억 x DT입니다.
이런 수치가 나오는 이유는 다음과 같습니다.
1억은 모든 데이터의 갯수입니다. 그러니까, 모든 데이터를 최소한 한번은 봐야 한다는 뜻입니다.
DT는 하나의 데이터가 100번째 안에 드느냐 아니냐를 판단하기 위한 시간입니다.
즉, 1억개의 데이터를 다 보면서, 각각이 100번째 안에 드느냐 아니냐를 판단하는 시간이죠.
이제는 DT가 27보다 작냐 크냐만 알면 됩니다.
1. 어레이 (array) 사용
제일 단순한 방법은 그냥 어레이로 100개의 데이터를 관리하는 것입니다.
즉, 100개 크기의 어레이을 만든 후, 데이터가 들어올 때마다, 이 테이터가 100개 안에 들어오는가 아닌가를 판단하는 것이죠.
기존의 100개의 데이터 범위에 들어오면, 그 데이터를 넣고, 가장 작은 데이터를 버리면 됩니다.
안 들어오면, 즉 100등안에 들어오지 않으면 그냥 그 데이터를 버리면 됩니다.
한 번 계산해 볼까요.
100개의 데이터에서 그 데이터가 들어오는지를 판단하려면 1번만 비교하면 됩니다.
즉, 가장 작은 데이터보다 크냐 작냐만 판단하면 됩니다.
그 데이터가 작으면 그냥 버리면 됩니다. 하지만, 크다면...
기존의 데이터 중 가장 작은 것을 버리기고, 그 새로운 데이터를 적당한 위치에 넣어야 합니다.
그 시간은, log2(100) - 1 + 50이 걸립니다.
log2(100) - 1 은 그 데이터를 위치를 찾는 binary search의 평균 시간입니다.
50은 그 위치가 결정됐을 때, 그 뒤의 데이터를 쭈욱 밀어내는 평균 시간입니다.
평균이니까, 50번이 합리적입니다. 즉, 운이 좋으면, 1개의 데이터만 옮기면 되고, 운이 나쁘면 100개를 다 밀어야 하겠죠.
여기서, 100개를 밀어내는데 평균이 50이라면, 검색에서의 평균은 왜 log2(100) - 1 일까요?
그건 binary search의 특성때문에 그렇습니다.
1번에 데이터를 찾을 확율을 1/100입니다. 2번에 데이터를 찾을 확율은 2/100이고, 3번에 데이터를 찾을 확율은 4/100입니다.
이렇게 해서, 각 확율과 비교횟수를 곱해서 평균을 내면, 대략 log2(100) - 1이 됩니다. log2(100) / 2 가 아니라는 것이죠.
어레이에서 새로운 데이터를 중간에 삽입할 때 뒤의 데이터를 밀어내지 않고는 제대로 된 어레이를 유지할 수 없습니다.
예를 들어, 5개짜리 어레이를 보겠습니다. 내용은 다음과 같습니다.
50 40 30 20 10
여기에 45라는 데이터가 들어오면,
50 45 40 30 20 으로 만들어야 합니다. 그러려면, 45는 기존의 40자리에 들어가야 하고, 그 뒤로는 쭈욱 밀려서 데이터가 들어가야 합니다.
log2(100)은 대략 7입니다. 그럼, log2(100) - 1 + 50은 56이 되겠네요.
이 값은 27보다 두배 정도 큽니다.
즉, 이 방법은 정열해서 그냥 상위 100개를 고르는 방식보다 2배 정도 느리다는 것이죠.
다른 좋은 방법이 없을까요?
2. 링크드 리스트 (Linked List) 사용
링크드 리스트를 고려해 볼 수 있지만, 이 자료구조는 새로운 데이터의 추가 및 삭제는 용이합니다만 검색(search)에는 취약한 구조입니다. 링크드 리스트에서 원하는 데이터를 찾는 시간은 그 크기에 비례합니다. 그래서, 결국 DT는 평균적으로 50의 값을 갖습니다.
3. Heap 사용
Heap이라는 데이터 구조를 살펴보겠습니다. 여기서, heap은 Java에서의 메모리 덩어리나 C/C++에서 프로그래머가 정의한 데이터 영역을 의미하는게 아닙니다. 아래 그림은 heap의 젼형적인 형태입니다. 가장 위의 테이터가 가장 큽니다. 좌우의 데이터는 작습니다.이런 특징을 갖고 있습니다.
이 데이터 구조는 새로운 데이터를 적절한 위치에 넣을 때 시간이 log2(n) 밖에 걸리지 않습니다.
이 구조를 사용한다면, 1억개의 데이터에 대하여,
1억 x log2(100) 만의 시간이 걸려서, 100개의 상위 데이터를 고를 수 있습니다.
1억 x log2(100) 은 대충 1억 x 7입니다.
정렬하는 방식보다도 3~4배 정도 빠릅니다.
4. 다른 방법
다른 방법 하나는, 1억개의 데이터 중에서 가장 큰수를 고르는 것입니다. 그 다음에는 2번째로 큰 수를 고르고, 그 다음에는 3번째로 큰 수를 고르고, 이렇게 해서 100개의 데이터를 고르는 것입니다.
이 방식은, 1억 + (1억 - 1) + (1억 - 2) + ... + (1억 - 99) 의 비교가 필요합니다.
대충 계산하면, 100억 - 5000 이 됩니다. 대충 100억이 되는군요.
이슈 1
이 포스팅에서의 자료 구조 비교에는 이슈가 있습니다. 단위 operation에 대한 비용(cost) 계산이 빠져있습니다. 즉, 검색에서 비교하는 오퍼레이션 1개와 어레이에서 데이터를 옮기는 한개의 오퍼레이션이 같은 비용(시간)이라는 가정을 하고 있습니다.
이슈 2
이건 알고리즘, 자료 구조와 다른 이슈입니다.
어떤 데이터 구조를 사용하던지 간에, 잘 정리된 API는 의미를 갖습니다.
즉, 내부의 자료구조로 무엇을 사용하던, 아래의 API로 분리하여 개발을 하는 건 좋은 개발 습관이 될 것입니다.
void add(int data)
int[] get100()
실제로, add()의 구현 부분에서 어레이를 사용하던, 링크드 리스트를 사용하던, 힙을 사용하던, 외부에서 add()를 사용하는 방식에는 변화가 없게 됩니다.
댓글