Java - PriorityQueue보다 빠른 것을 찾고 있습니다.

Question

많은 양의 데이터에서 Java를 사용하고 있습니다.

는 INT 키 (게터 & 족)와 이중 WEIGHT 함유

실제로 난 작은 클래스 (요소)가 [I는 가능한 문제를 단순화하기 위해 시도].

파일에서 이러한 개체를 많이 읽고 나는 가장 (가장 무게가 나가는) M 개체를 얻어야합니다.

사실 저는 두 요소를 비교하기 위해 작성된 Comparator와 함께 PriorityQueue를 사용하고 있지만 작동하지만 속도가 너무 느립니다.

빠른 방법을 알고 있습니까? M은 다음 계산 시간을 많이 낭비 할 수있는 모든 요소를 ​​정렬, 적당히 작은 경우

는

Answer 1

힙 기반 우선 순위 큐는이 문제에 대한 좋은 데이터 구조입니다. 온 전성 검사와 마찬가지로 큐를 올바르게 사용하고 있는지 확인하십시오.

가장 높은 가중치 항목을 원하면 최소- 큐 —을 사용하십시오. 여기서 힙의 맨은 가장 작은 항목입니다. 모든 항목을 최대 대기열에 추가하고 완료되면 상단의 M 항목을 검사하는 것이 효율적이지 않습니다.

각 항목에 대해 큐에 M 개 미만의 항목이 있으면 현재 항목을 추가하십시오. 그렇지 않으면 힙 맨 위를 들여다보십시오. 현재 항목보다 작 으면이를 버리고 현재 항목을 대신 추가하십시오. 그렇지 않으면 현재 항목을 버립니다. 모든 항목이 처리되면 큐에 M 가장 중요한 항목이 포함됩니다.

일부 힙에는 힙의 맨 위를 바꿀 수있는 바로 가기 API가 있지만 Java의 Queue은 그렇지 않습니다. 그럼에도 불구하고, 빅 O의 복잡성은 동일합니다.

Answer 2

감사드립니다. 우선 순위 큐 (예 : 힙, 맨 위에있는 최소 요소)에있는 첫 번째 M 개의 객체 만 넣고 나머지 요소에 대해 반복 할 수 있습니다. 요소가 힙의 상단보다 클 때마다 top을 제거하고 new를 푸시합니다 요소를 힙에 넣습니다.

또는 전체 배열을 한 번 반복하여 더 큰 값을 가진 M 개 이상의 개체가 있음을 확인할 수있는 통계 임계 값을 찾을 수 있습니다 (예 : 값이 여러 개인 경우). 정상적으로 배포 됨). 그런 다음 더 큰 값을 갖는 모든 요소로 정렬을 제한 할 수 있습니다.

Answer 3

@Tnay : 비교를 수행하지 않을 점이 있습니다. 불행히도, 예제 코드는 여전히 하나를 수행합니다. 이 문제 해결 : 또한

public int compare(ListElement i, ListElement j) { 
    return i.getValue() - j.getValue(); 
} 

를, 어느 쪽도없는 당신, 나 빅스는 방법들이 0을 반환하지 않습니다 때문에 이후, 매우 까다로운 버그 일부 정렬 알고리즘에 문제가 될 수있다, 엄격하게 정확 비교 다른 구현으로 전환 한 경우에만 나타납니다. the Java docs 가입일

:

구현자가 모든 X 및 Y에 대한 그 SGN (비교 (X, Y)) == -sgn (X)과 비교 (Y 등)를 확인한다.

이것은 상당한 일정 속도 향상을 가져올 수도 있고하지 않을 수도 있습니다. 이것을 erickson의 솔루션과 결합하면 M의 크기에 따라 더 빨리 수행하기가 어려울 것입니다. M이 매우 큰 경우 가장 효율적인 해결책은 아마 배열에 Java의 내장 qsort를 사용하여 모든 요소를 ​​정렬하고 결국 배열의 한쪽 끝을 잘라내는 것입니다.

Answer 4

n 개의 항목 중 top-m을 얻기위한 복잡성을 제공하는 "heap top의 peek"알고리즘 외에도 다음과 같은 두 가지 솔루션이 있습니다.

해결 방법 1 : 피보나치 힙을 사용하십시오.

JDK의 PriorityQueue 구현은 균형 잡힌 바이너리 힙입니다. Fibonacci heap 구현에서 더 많은 성능을 끌어낼 수 있어야합니다. 이진 힙에 삽입하는 동안 힙 크기에 복잡성 Ω (log n)이있는 동안 상각 시간 상각이 상각됩니다. 모든 요소에 대해이를 수행한다면 Ω (n log n)에있게됩니다. Fib 힙을 사용하여 n 개의 항목 중 top-m을 찾는 것은 복잡성 O (n + m log n)을 갖는다. 이를 힙에 m 요소 만 삽입하라는 제안과 결합하면 O (n + m log m)이됩니다.이 시간은 얻을 수있는 선형 시간에 가깝습니다.

해결 방법 2 : 목록을 M 번 탐색합니다.

O (n) 시간의 집합에서 k 번째로 큰 요소를 가져올 수 있어야합니다. 모든 것을 목록으로 읽고 다음을 수행하십시오.

kthLargest(k, xs) 
    Pick a random pivot element p from the list 
    (the first one will do if your list is already random). 
    Go over the set once and group it into two lists. 
    Left: smaller than p. 
    Right: Larger or equal to p. 
    If the Right list is shorter than k, return kthLargest(k - right.size, Left) 
    If the Right list is longer than k, return kthLargest(k, right) 
    Otherwise, return p. 

그러면 O (n) 시간이됩니다. 그 m 번 실행하면 시간이 O (nm)의 집합에서 top-m 개체를 얻을 수 있어야합니다. n은 충분히 큰 n 및 충분히 작은 m에 대해 n log n보다 엄격하게 작습니다. 예를 들어, 상위 10 개 항목을 100 만 개가 넘는 항목을 가져 오는 데는 이진 힙 우선 순위 대기열을 사용하는 것의 절반이 소요되며 다른 모든 사항은 동일합니다.