取topN不同算法的实现的性能差别

背景

最近在实现一个需求，需要对大量数据中排序出前N，最暴力的方法肯定是直接全量排序。这里很明显是可以不用全量排序的，取前N，我们自然而然可以想到一个算法——堆排序。
一开始自己先写好了一版，后来想起，这个完全可以交给AI来实现，在好奇心的驱使下，于是我让ChatGPT实现了一个topN的算法，于是有了这篇文章。

测试

以下只将对项目业务进行简化：直接排序一个int数组，长度100w，排出top 1w，模拟100次。
测试在原始数组不同情况下，各个实现的实际耗时。

public class MyTest {
    private static int totalCount = 100_0000;//总数量
    private static int rankSize = 10000;//排行榜长度
    private static int batch = 100;//测试次数

    public static void main(String[] args) {
        List<Integer> values = new ArrayList<>();
        for (int i = 0; i < totalCount; i++) {
            values.add(i);
        }
        //默认递增
        Collections.shuffle(values);//打乱顺序
        //Collections.reverse(values);//递减顺序
        topN_NiuMa(values);
        topN_ChatGPT(values);
        topN_BruteForce(values);

    }

    //牛马版
    private static void topN_NiuMa(List<Integer> values) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < batch; i++) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(rankSize);
            for (Integer value : values) {
                queue.offer(value);
                if (queue.size() > rankSize) {
                    queue.poll();
                }
            }
        }
        long endTime = System.currentTimeMillis();
        long cost = endTime - startTime;
        System.out.println("牛  马  版（100次）：" + cost + " ms");
    }

    //ChatGPT版
    private static void topN_ChatGPT(List<Integer> values) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < batch; i++) {
            PriorityQueue<Integer> queue = new PriorityQueue<>(rankSize);
            for (Integer value : values) {
                if (queue.size() < rankSize) {
                    queue.offer(value);
                } else if (value > queue.peek()) {
                    queue.poll();
                    queue.offer(value);
                }
            }
        }
        long endTime = System.currentTimeMillis();
        long cost = endTime - startTime;
        System.out.println("ChatGPT版（100次）：" + cost + " ms");
    }

    //暴力版
    public static void topN_BruteForce(List<Integer> values) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < batch; i++) {
            List<Integer> values1 = new ArrayList<>(values);
            Collections.sort(values1, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return Integer.compare(o2, o1);
                }
            });
        }

        long endTime = System.currentTimeMillis();
        long cost = endTime - startTime;
        System.out.println("暴  力  版（100次）：" + cost + " ms");

    }
}

结果

待排数据递增（与目标相反）

牛 马 版（100次）：8977 ms
ChatGPT版（100次）：8874 ms
暴 力 版（100次）：377 ms

待排数据递减（与目标相同）

牛 马 版（100次）：9342 ms
ChatGPT版（100次）：516 ms
暴 力 版（100次）：338 ms

待排数据随机（符合实际情况）

牛 马 版（100次）：13355 ms
ChatGPT版（100次）：2539 ms
暴 力 版（100次）：19483 ms

结论

暴力版，在原始数据有序的情况下，表现出惊人的性能，这里得益于java底层对排序算法的优化。
牛马版，在原始数据有序的情况下表现略微优于完全无序的情况，但总体表现不佳。
ChatGPT，在原始数据与目标顺序形的情况下表现良好，原始数据与目标数据相反时，表现较差，原始数据无序的情况下表现最优，这也是最正统的topN算法的实现。
在实际生产环境中，正统的topN算法是有不错的表现的。