为什么通过堆数据结构进行线性搜索比遍历树更快？

Question

在下面的代码中，

indexOfSlow

在我的测试用例中比

indexOf

慢了大约 17 倍，尽管前者比后者做的比较少。

这是为什么？

（我的直觉是

indexOf

的卓越性能是由于顺序数组访问具有例如缓存优势 - 但我想确定）

我机器的性能数据：

| elementCount | indexOf msec | indexOfSlow msec | slow/fast |
|--------------+--------------+------------------+-----------|
|        10000 |           41 |              852 |        21 |
|        20000 |          232 |             3387 |        15 |
|        30000 |          375 |             6642 |        18 |
|        40000 |          710 |            12699 |        18 |
|        50000 |         1197 |            19182 |        16 |
|--------------+--------------+------------------+-----------|
|      average |              |                  |      17.6 |

注意Java的

PriorityQueue.indexOf()

和我的

indexOf

很相似，所以它不会像我的

indexOfSlow

一样尝试走树和提前停止。

class Heap<T extends Comparable<T>> {

    public static void main(String[] args) {
        int elementCount = 50_000;

        final List<Integer> elements = new ArrayList<>(elementCount);
        for (int i = 0; i < elementCount; i++)
            elements.add(i);

        for (int j = 0; j < 3; j++) {
            final var heap = new Heap<Integer>();
            for (int i : elements)
                heap.add(i);
            assert heap.peek() == 0;
            final long nanoBefore = System.nanoTime();
            for (int i = elementCount; i > 0; i--)
                heap.indexOf(i - 1);
//                heap.indexOfSlow(i - 1);
            final long nanoAfter = System.nanoTime();
            if (j > 0) // discard first round as warmup
                System.out.println("Time taken: " + (nanoAfter - nanoBefore) / 1_000_000 + " msec");
        }
    }

    private final ArrayList<T> list = new ArrayList<>();

    public T peek() {
        return list.isEmpty() ? null : list.get(0);
    }

    private void siftUp(int i, T value) {
        while (i > 0) {
            int parentI = (i - 1) / 2;
            final T parentValue = list.get(parentI);
            if (parentValue.compareTo(value) <= 0)
                return;
            list.set(parentI, value);
            list.set(i, parentValue);
            i = parentI;
        }
    }

    public void add(T value) {
        list.add(value);
        siftUp(list.size() - 1, value);
    }

    public int indexOf(T value) {
        final int size = list.size();
        if (size > 0) {
            for (int i = 0; i < list.size(); i++) {
                if (value.compareTo(list.get(i)) == 0)
                    return i;
            }
        }
        return -1;
    }

    public int indexOfSlow(T value) {
        final int size = list.size();
        if (size > 0) {
            Queue<Integer> childrenToVisit = new LinkedList<>();
            childrenToVisit.add(0);
            while (!childrenToVisit.isEmpty()) {
                int i = childrenToVisit.poll();
                final int cmp = list.get(i).compareTo(value);
                if (cmp == 0)
                    return i;
                if (cmp > 0)
                    continue;
                int rightChildIdx = (i + 1) * 2;
                int leftChildIdx = rightChildIdx - 1;
                if (leftChildIdx < size)
                    childrenToVisit.add(leftChildIdx);
                if (rightChildIdx < size)
                    childrenToVisit.add(rightChildIdx);
            }
        }
        return -1;
    }

}