这是线性搜索实现真正有用吗？ [英] Is this linear search implementation actually useful?

问题描述

在事项计算我发现了这个有趣的线性搜索实现（它实际上是我的Java实现; - ））：

In Matters Computational I found this interesting linear search implementation (it's actually my Java implementation ;-)):

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;
}

基本上，它采用的是定点，这是搜索的价值，让你总能找到的价值，并没有检查数组边界。的最后一个元素被存储在临时变量，然后哨兵被放置在最后的位置。当值被发现（记住，它总是由于哨兵发现），原始元素恢复和索引进行检查，如果它再presents的最后一个索引，是不等于搜索值。如果是这样的话，-1（NOT_CONTAINED）返回，否则该索引。

It basically uses a sentinel, which is the searched for value, so that you always find the value and don't have to check for array boundaries. The last element is stored in a temp variable, and then the sentinel is placed at the last position. When the value is found (remember, it is always found due to the sentinel), the original element is restored and the index is checked if it represents the last index and is unequal to the searched for value. If that's the case, -1 (NOT_CONTAINED) is returned, otherwise the index.

当我发现这个实现真正聪明的，我不知道它实际上是有用的。对于小数组，它似乎总是慢，对于大数组似乎只更快时，未找到该值。任何想法？

While I found this implementation really clever, I wonder if it is actually useful. For small arrays, it seems to be always slower, and for large arrays it only seems to be faster when the value is not found. Any ideas?

修改

在最初的实现是用C ++编写，这样可以有所作为。

The original implementation was written in C++, so that could make a difference.

推荐答案

它不是线程安全的，例如，你可以失去你的 A（高）价值具有后的第一个第二个线程开始发生了变化 A（高）到键，所以将记录键到 TMP ，并完成了第一个线程恢复后 A（高） 到其原始值。第二个线程将恢复 A（高）来它第一次看到，这是第一个线程的键。

It's not thread-safe, for example, you can lose your a[high] value through having a second thread start after the first has changed a[high] to key, so will record key to tmp, and finish after the first thread has restored a[high] to its original value. The second thread will restore a[high] to what it first saw, which was the first thread's key.

这也是在Java中没有用的，因为JVM将包括边界阵列上的检查，所以你的while循环检查你不会过去阵列的啦。

It's also not useful in java, since the JVM will include bounds checks on your array, so your while loop is checking that you're not going past the end of your array anyway.

这篇关于这是线性搜索实现真正有用吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！