5

整数配列入力から上位 4 つの最大値を見つけようとしています。たとえば、指定された入力配列 {1232, -1221, 0, 345, 78, 99} に対して、上位 4 つの最大値として {1232, 345, 99, 78} が返されます。以下の方法で要件を解決しました。しかし、私はまだその時間効率に満足していません. 入力が大きくなるにつれて、メソッドをさらに最適化する機会はありますか? 手がかりは本当にありがたいです。ありがとうございました。

public int[] findTopFourMax(int[] input) {
int[] topFourList = { Integer.MIN_VALUE, Integer.MIN_VALUE, Integer.MIN_VALUE,       Integer.MIN_VALUE };
for (int current : input) {
    if (current > topFourList[0]) {
        topFourList[3] = topFourList[2];
        topFourList[2] = topFourList[1];
        topFourList[1] = topFourList[0];
        topFourList[0] = current;
    } else if (current > topFourList[1]) {
        topFourList[3] = topFourList[2];
        topFourList[2] = topFourList[1];
        topFourList[1] = current;
    } else if (current > topFourList[2]) {
        topFourList[3] = topFourList[2];
        topFourList[2] = current;
    } else if (current > topFourList[3]) {
        topFourList[3] = current;
    }
}
return topFourList;

}

4

6 に答える 6

13

最も簡単な (最も効率的ではありませんが) 方法は、最後の 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]);
    }
}
于 2013-01-02T13:01:16.137 に答える
2

Peter Lawrey によるこの回答を確認してください。基本的には、配列を実行し、各要素を a に追加しSortedSet、各反復で最小の要素を削除してサイズを 4 に維持するという考え方です。このプロセスは、配列を完全にソートするための典型的な O(n logn) および O(n 2 ) の最悪のケースと比較して、最悪のケースでも O(n) です。

final List<Integer> input = new ArrayList(Arrays.asList(1232, -1221, 0, 345, 78, 99));
final NavigableSet<Integer> topFour = new TreeSet<>();
for (int i : input) {
  topFour.add(i);
  if (topFour.size() > 4) topFour.remove(topFour.first());
}
System.out.println(topFour);
于 2013-01-02T13:10:03.353 に答える
1

最も簡単な方法は、配列を並べ替えて、最初と最後の 4 つの要素を取得することです。

最終的に、最大 4 つのエントリはどこにでもある可能性があるため、何をするにしても、配列全体を読み取る必要があり、それは O(n) 操作になります。

于 2013-01-02T13:01:26.727 に答える
1

配列の並べ替えに関する前述の説明は、本当に最も簡単な方法を提供しますが、実際には最も効率的ではありません。

コレクション内の k 番目に大きい/小さい値を見つけるために、QuickSort (Quickselect) のバリエーションを使用できます。

http://en.wikipedia.org/wiki/Selection_algorithm

正しく実装すると、O(n) 時間で k 番目に大きいものを取得できます。

基本的には、ピボットを使用してクイックソートのように分割し、各反復後のピボット位置を必要な位置 (この場合は 4 つ) と比較します。等しい場合は位置を返します。そうでない場合は、アルゴリズムを入力の正しい半分に適用します。 .

k 番目に大きい値のインデックスが見つかったら、単純に配列を再度反復処理して、より下位の値を取得できますinput[k]

ちょうど 4 つ必要なため、これはやり過ぎかもしれませんが、これが最も一般的な方法です。

メモリをあまり気にしない場合は、上位/下位の X 値を保持する Bounded PriorityQueue を使用して、単純にすべてをキューに挿入することもできます。残っているのは、あなたが興味を持っている値です。

于 2013-01-02T13:03:10.520 に答える
1

Sort : 配列をソートし、最後の 4 つの要素を取得します

Min Heap :これに対する最も簡単な解決策は、最大サイズ 4の最小ヒープを維持することです。

このソリューションの複雑さは O(nlogk) です。ここで、n は要素の数、k は必要な要素の数です。

Priority Queue :この質問の実装PriorityQueueで説明されているように、固定サイズとカスタム コンパレータを使用して を作成できます。

選択アルゴリズム :選択アルゴリズムを使用できます。(nk) 番目の最大要素を見つけて、この要素よりも高いすべての要素を返すことができますが、実装が難しくなります。最適なケースの複雑さ: O(n)

于 2013-01-02T13:15:17.400 に答える
-1
float a[] = {1.0f,3.0f,5.0f,6.0f,7.0f,10.0f,11.0f,3.2f,4.0f};

float first =0.0f;
float second=0.0f;
float third =0.0f;
for (int i=0; i<a.length; i++){
    if(first < a[i]){
        first=a[i];
    }
}
System.out.println("first largest is "+first);
for (int j=0; j<a.length; j++){
    if(a[j] <first && a[j] > second){
        second = a[j];
    }
}
System.out.println("second largest is "+second);
for (int k=0;k<a.length; k++){
    if(a[k]<second && a[k]>third){
        third =a[k];
    }
}
System.out.println("third largest is "+third);
于 2014-08-06T22:10:08.493 に答える