JavaArrays.sort[副本]

Question

正如我所想的那样，我一直在解决一个算法问题并找到了解决方案。但没想到我遇到了一个奇怪的问题。

让我们假设我在英特尔第11代处理器java 8/17上有以下代码（两者都有）：

import java.util.Arrays;
import java.util.concurrent.ThreadLocalRandom;

public class DistanceYandex{
    static class Elem implements Comparable<Elem>{
        int value;
        int index;
        long dist;
        public Elem(int value, int index){
            this.value = value;
            this.index = index;
        }

        @Override
        public int compareTo(Elem o){
            return Integer.compare(value, o.value);
        }
    }
    public static void main(String[] args){
        int n = 300_000;
        int k = 3_000;
        Elem[] elems = new Elem[n];
        for(int i = 0; i < n; i++){
            elems[i] = new Elem(ThreadLocalRandom.current().nextInt(), i);
        }
        solve(n, k, elems);
    }
    private static void solve(int n, int k, Elem[] elems){
        Arrays.sort(elems); // interesting line
        long time = System.nanoTime();

        for(int i = 0; i < n; i++){
            elems[i].dist = findDistForIth(elems, i, k);
        }
//        i omit output, because it's irrelevant
//        Arrays.sort(elems, Comparator.comparingInt(elem -> elem.index));
//        System.out.print(elems[0].dist);
//        for(int i = 1; i < n; i++){
//            System.out.print(" " + elems[i].dist);
//        }
        System.out.println((System.nanoTime() - time)/1_000_000_000.0);
    }

    private static long findDistForIth(Elem[] elems, int i, int k){
        int midElem = elems[i].value;
        int left = i - 1;
        int right = i + 1;
        long dist = 0;
        for(int j = 0; j < k; j++){
            if(left < 0){
                dist += elems[right++].value - midElem;
            }else if(right >= elems.length){
                dist += midElem - elems[left--].value;
            }else{
                int leftAdd = midElem - elems[left].value;
                int rightAdd = elems[right].value - midElem;
                if(leftAdd < rightAdd){
                    dist+=leftAdd;
                    left--;
                }else{
                    dist+=rightAdd;
                    right++;
                }
            }
        }
        return dist;
    }
}

把你的眼睛指向解决函数。

在这里我们有一个简单的解决方案，调用函数 findDistForIth n 次并测量所需的时间（我不使用 JMH，因为我的问题的测试html" target="_blank">系统使用简单的一次性时间测量）。在捕获开始时间之前，它使用内置的 Arrays.sort 函数按自然顺序对数组进行排序。

正如您所注意到的，测量的时间不包括数组排序的时间。此外，函数findDisdiForIth的行为并不取决于输入数组是否排序（它主要去第三个其他分支）。但是如果我用Arrays.sort注释掉一行，我会得到更快的执行速度：而不是大约7.3秒，大约需要1.6秒。快了4倍多！

我不明白这是怎么回事。

我想也许是gc在这里搞砸了，我试图将我给jvm的内存增加到2gb（-Xmx2048M -Xms2048M）。没帮助。

我试图将显式比较器作为第二个参数传递给< code>Arrays.sort

我启动了分析器(Intellij Profiler)

但这并没有给我多少信息。。。

我尝试将它直接构建到.jar并通过javacmd启动（在通过intellij启动之前）。这也无济于事。

有人知道怎么回事吗？

这个问题也在在线编译器中重复出现：https://onlinegdb.com/MPyNIknB8T

Answer 1

可能需要使用红黑树排序算法对数据进行排序，该算法在SortedSet数组中实现。排序使用mergesort排序算法，该算法适用于少量数据