从Java Array获得前四大值

Question

我试图从整数数组输入中找到前4个最大值.例如,对于给定的输入数组{1232,-1221,0,345,78,99}将返回{1232,345,99,78}作为前4个最大值.我用下面的方法解决了这个问题.但我仍然不满足于它的时间效率.当输入变大时,是否有机会更多地优化方法？任何线索都非常感谢.谢谢.

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;

}

Answer 1

最简单(尽管不是最有效)的方法是对包含最后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个元素.这个线程描述了这两种方法.

虽然选择算法提供了O(n)解决方案,但是最小堆解决方案(它O(nlogK))应该具有更好的常量,特别是对于小型解决方案k可能更快.

PS(编辑):

对于4个元素,您可能会发现调用循环4次,并在每个循环中找到最大值(并在每次迭代中将旧的最大值更改为-infinity)将比更"复杂"的方法更有效,因为它需要顺序读取并具有相当小的常量.这当然不适用于较大的k,并且衰变O(n^2)为k->n

EDIT2:基准测试:

为了好玩,我在附加的代码上运行了一个基准测试.结果是:

[naive, sort, heap] = [9032, 214902, 7531]

我们可以看到天真和堆比基于排序的方法好得多,并且天真比基于堆的稍微慢一些.我做了一个wilcoxon测试来检查天真和堆之间的差异是否具有统计显着性,并且我得到了一个P_Value 3.4573e-17.这意味着两种方法"相同"的概率是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]);
    }
}