java - 为什么哨兵搜索比线性搜索慢？

Question

我决定减少在数组中查找元素所需的比较次数。在这里，我们将列表的最后一个元素替换为搜索元素本身，并运行 while 循环以查看列表中是否存在搜索元素的任何副本，并在找到搜索元素后立即退出循环。请参阅代码片段进行说明。

import java.util.Random;

public class Search {

    public static void main(String[] args) {
        int n = 10000000;
        int key = 10000;
        int[] arr = generateRandomSize(n);
        long start = System.nanoTime();
        int find = sentinels(arr, key);
        long end = System.nanoTime();
        System.out.println(find);
        System.out.println(end - start);

        arr = generateRandomSize(n);
        start = System.nanoTime();
        find = linear(arr, key);
        end = System.nanoTime();
        System.out.println(find);
        System.out.println(end - start);
    }

    public static int[] generateRandomSize(int n) {
        int[] arr = new int[n];
        Random rand = new Random();

        for (int i = 0; i < n; ++i) {
            arr[i] = rand.nextInt(5000);
        }

        return arr;
    }

    public static int linear(int[] a, int key) {
        for(int i = 0; i < a.length; ++i) {
            if (a[i] == key) {
                return i;
            }
        }

        return -1;
    }

    public static int sentinels(int[] a, int key) {
        int n = a.length;
        int last = a[n-1];
        a[n-1] = key;

        int i = 0;
        while (a[i] != key) {
            ++i;
        }
        a[n-1] = last;
        if ((i < n - 1) || a[n-1] == key ) {
            return i;
        }

        return -1;
    }

}

因此，使用哨兵搜索，我们不会像 i < arr.length 这样进行 10000000 次比较。但为什么线性搜索总是表现出更好的性能？

Answer 1

您必须查看字节码，甚至更深入地查看从中产生了什么热点。但我很确定这个说法是不正确的:

using sentinel search we are not doing 10000000 comparisons like i < arr.length

为什么？因为当你访问 a[i] , i必须进行边界检查。另一方面，在线性情况下，优化器可以推断它可以省略边界检查，因为它“知道”i>=0。 (因为循环结构)还有 i<arr.length因为它已经在循环条件下进行了测试。

因此哨兵方法只会增加开销。

这让我想起了大约 20 年前我做的一个智能 C++ 优化(称为“模板元编程”和“表达式模板”)，它导致更快的执行时间(以更长的编译时间为代价)，并且之后下一个编译器版本发布后，我发现新版本能够优化原始源代码以生成完全相同的程序集 - 简而言之，我宁愿以不同的方式使用我的时间并留在更具可读性(=更易于维护)的版本的代码。