最も簡単な (最も効率的ではありませんが) 方法は、最後の 4 つの要素を含むサブ配列で配列をソートすることです。
サブ配列Arrays.sort()
をソートして取得するために使用できます。Arrays.copyOfRange()
int[] arr = new int[] {1232, -1221, 0, 345, 78, 99};
Arrays.sort(arr);
int[] top4 = Arrays.copyOfRange(arr, arr.length-4,arr.length);
System.out.println(Arrays.toString(top4));
より効率的な解決策として、上位 K 個の要素の最小ヒープを維持するか、選択アルゴリズムを使用して上位 4 番目の要素を見つけることができます。2 つのアプローチについては、このスレッドで説明しています。
選択アルゴリズムはO(n)
解決策を提供しますが、min-heap 解決策 (これは ですO(nlogK)
) の方がより良い定数を持つ必要があり、特に小さいk
場合はより高速になる可能性があります。
PS(編集):
4 つの要素の場合、ループを 4 回呼び出し、それぞれの最大値を見つける (そして各反復で古い最大値を -infinity に変更する) 方が、より「複雑な」アプローチよりも効率的であることがわかる場合があります。シーケンシャル読み取りであり、定数はかなり小さいです。k
もちろん、これはより大きなには当てはまりませんO(n^2)
。k->n
EDIT2: ベンチマーク:
楽しみのために、添付のコードでベンチマークを実行しました。結果は次のとおりです。
[naive, sort, heap] = [9032, 214902, 7531]
ナイーブとヒープはソートベースのアプローチよりもはるかに優れており、ナイーブはヒープベースよりもわずかに遅いことがわかります。ナイーブとヒープの差が統計的に有意かどうかを確認するためにウィルコクソン テストを行ったところ、P_Value は3.4573e-17
. これは、2 つのアプローチが「同一」である確率が 3.4573e-17 (非常に小さい) であることを意味します。このことから、ヒープベースのソリューションは、単純でソートするソリューションよりも優れたパフォーマンスを提供すると結論付けることができます(そして、経験的に証明しました!)。
添付ファイル: 私が使用したコード:
public static int[] findTopKNaive(int[] arr, int k) {
int[] res = new int[k];
for (int j = 0; j < k; j++) {
int max=Integer.MIN_VALUE, maxIdx = -1;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
maxIdx = i;
}
}
arr[maxIdx] = Integer.MIN_VALUE;
res[k-1-j] = max;
}
return res;
}
public static int[] findTopKSort(int[] arr, int k) {
Arrays.sort(arr);
return Arrays.copyOfRange(arr, arr.length-k,arr.length);
}
public static int[] findTopKHeap(int[] arr, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
for (int x : arr) {
if (pq.size() < k) pq.add(x);
else if (pq.peek() < x) {
pq.poll();
pq.add(x);
}
}
int[] res = new int[k];
for (int i =0; i < k; i++) res[i] = pq.poll();
return res;
}
public static int[] createRandomArray(int n, Random r) {
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = r.nextInt();
return arr;
}
public static void main(String... args) throws Exception {
Random r = new Random(1);
int k = 4;
int repeats = 200;
int n = 5000000;
long[][] results = new long[3][repeats];
for (int i = 0; i < repeats; i++) {
int[] arr = createRandomArray(n, r);
int[] myCopy;
myCopy = Arrays.copyOf(arr, n);
long start = System.currentTimeMillis();
findTopKNaive(myCopy, k);
results[0][i] = System.currentTimeMillis() - start;
myCopy = Arrays.copyOf(arr, n);
start = System.currentTimeMillis();
findTopKSort(myCopy, k);
results[1][i] = System.currentTimeMillis() - start;
myCopy = Arrays.copyOf(arr, n);
start = System.currentTimeMillis();
findTopKHeap(myCopy, k);
results[2][i] = System.currentTimeMillis() - start;
}
long[] sums = new long[3];
for (int i = 0; i < repeats; i++)
for (int j = 0; j < 3; j++)
sums[j] += results[j][i];
System.out.println(Arrays.toString(sums));
System.out.println("results for statistic test:");
for (int i = 0; i < repeats; i++) {
System.out.println(results[0][i] + " " + results[2][i]);
}
}