这种线性搜索实现真的有用吗？

Question

在Matters Computational中我发现了这个有趣的线性搜索实现(它实际上是我的Java实现;-)):

public static int linearSearch(int[] a, int key) {
    int high = a.length - 1;
    int tmp  = a[high];

    // put a sentinel at the end of the array   
    a[high] = key;

    int i = 0;

    while (a[i] != key) {
        i++;
    }

    // restore original value
    a[high] = tmp;

    if (i == high && key != tmp) {
        return NOT_CONTAINED;
    }

    return i;
}

它基本上使用了一个sentinel,它是搜索的值,因此您总是可以找到该值,而不必检查数组边界.最后一个元素存储在temp变量中,然后将sentinel放在最后一个位置.当找到该值时(记住,它总是由于sentinel而找到),原始元素将被恢复,并且如果它代表最后一个索引并且与搜索的值不相等则检查索引.如果是这种情况,则返回-1(NOT_CONTAINED),否则返回索引.

虽然我发现这个实现非常聪明,但我想知道它是否真的有用.对于小型数组,它似乎总是较慢,而对于大型数组,当找不到该值时,它似乎更快.有任何想法吗？

编辑

最初的实现是用C++编写的,所以这可能会有所不同.

Answer 1

它不是线程安全的,例如,你可以a[high]通过在第一个线程更改a[high]为第二个线程之后开始丢失你的值key,因此将记录key到tmp,并在第一个线程恢复a[high]到其原始值之后完成.第二个线程将恢复a[high]到它第一次看到的内容,这是第一个线程key.

它在java中也没用,因为JVM将在你的数组上包含边界检查,因此你的while循环检查你是否还没有超越数组的末尾.

Answer 2

你有没有注意到它的速度增加？没有

你会注意到缺乏可读性吗？是

您是否会注意到可能导致并发问题的不必要的数组突变？是

过早优化是万恶之源.

Answer 3

似乎没有特别有用.这里的"创新"只是通过将其与匹配测试相结合来摆脱迭代测试.如今,现代处理器在迭代检查上花费了0倍的时间(所有计算和分支都与匹配测试代码并行完成).

在任何情况下,二进制搜索都会在大型数组上启动此代码,并且在小型数组上具有可比性.线性搜索是20世纪60年代.