使用哨兵进行线性搜索有什么意义？

Question

我的目标是理解为什么采用哨兵线性查找比使用标准线性查找更受青睐。

#include <stdio.h>

int linearSearch(int array[], int length) {
    int elementToSearch;
    printf("Insert the element to be searched: ");
    scanf("%d", &elementToSearch);

    for (int i = 0; i < length; i++) {
        if (array[i] == elementToSearch) {
            return i; // I found the position of the element requested
        }
    }
    return -1; // The element to be searched is not in the array
}

int main() {
    int myArray[] = {2, 4, 9, 2, 9, 10};
    int myArrayLength = 6;
    linearSearch(myArray, myArrayLength);
    return 0;
}

维基百科提到:

另一种减少开销的方法是消除循环索引的所有检查。这可以通过将所需的项本身作为哨兵值插入到列表末尾来实现。

如果我使用哨兵实现线性搜索，我必须：

array[length + 1] = elementToSearch;

尽管如此，一旦找到要搜索的元素，循环就会停止检查数组的元素。使用哨兵进行线性搜索有什么意义呢？

- anon

---

这太荒谬了 - 这个问题已经包含了答案：“减少开销的另一种方法是消除对循环索引的所有检查。” - Karoly Horvath

使用哨兵的关键在于确定要搜索的值，使得该值总是位于数组末尾，并且无需检查任何数组边界。 - t0mm13b

Answer 1

标准的线性搜索会遍历所有元素，在每次检查数组索引时检查是否已达到最后一个元素。就像你的代码所做的那样。

for (int i = 0; i < length; i++) {
    if (array[i] == elementToSearch) {
        return i; // I found the position of the element requested
    }
}

然而，哨兵搜索的思想是将要搜索的元素放在最后，跳过数组索引搜索，这样每次迭代就可以减少一次比较。

while(a[i] != element)
    i++;

- Haris

Answer 2

首先，让我们将您的示例转换为使用哨兵的解决方案。

#include <stdio.h>

int linearSearch(int array[], int length, int elementToSearch) {
    int i = 0;
    array[length] = elementToSearch;
    while (array[i] != elementToSearch) {
        i++;
    }
    return i;
}

int main() {
    int myArray[] = {2, 4, 9, 2, 9, 10, -1};
    int myArrayLength = 6;
    int mySearch = 9;
    printf("result is %d\n", linearSearch(myArray, myArrayLength, mySearch));
    return 0;
}

注意，数组现在在末尾有一个额外的插槽来容纳哨兵值。(如果我们不这样做，写入到array[length]的行为是未定义的。)

---

哨兵方法的目的是减少每个循环迭代执行的测试次数。比较：

    // Original
    for (int i = 0; i < length; i++) {
        if (array[i] == elementToSearch) {
            return i; 
        }
    }
    return -1;

    // New 
    while (array[i] != elementToSearch) {
        i++;
    }
    return i;

在第一版中，代码对于每个循环迭代都会测试i和array[i]。在第二版中，不再测试i。

对于大型数组，性能差别可能很明显。

但是，它的劣势是什么？

1. 当未找到值时，结果不同;-1与length。
2. 我们必须使数组变得更大以容纳哨兵值。(如果我们没有做好工作，我们就有可能破坏堆栈或堆上的东西。疼！)
3. 数组不能只读。我们必须能够更新它。
4. 如果多个线程搜索不同元素的同一个数组，这将无法工作。

- Stephen C

---

是的...好的...未定义。 - Stephen C

Answer 3

使用哨兵值可以删除变量i及其相应的检查和增加。在您的线性搜索中，循环如下所示。

for (int i = 0; i < length; i++) {
    if (array[i] == elementToSearch) {
        return i; // I found the position of the element requested
    }
}

因此，变量 i 在循环的每次迭代中被引入、初始化、比较、增加并用于计算数组中的下一个元素。

如果将搜索的值传递给函数，则实际上该函数有三个参数。

int linearSearch(int array[], int length, int value) {
//...

使用哨兵值，可以将函数重写为以下方式。

int * linearSearch( int array[], int value ) 
{
    while ( *array != value ) ++array;

    return array;
}

在调用程序内部，您可以通过以下方式检查数组是否具有以下值

int *target = linearSearch( array, value );

int index = target == array + size - 1 ? -1 : target - array; 

- Vlad from Moscow

Answer 4

如果您将要搜索的值追加到数组末尾，那么与使用具有初始化、条件和增量的for循环相比，您可以使用更简单的循环。

while (array[i++] != elementToSearch)
    ;

然后循环条件是检查您搜索的值，这意味着在循环内执行的代码更少。

- Some programmer dude

---

此外，它还将减少一次比较。 - Haris

Answer 5

如果您添加要搜索的值，则可以在每个循环中减少一次比较，从而缩短运行时间。可能看起来像for(i = 0;;i++) if(array[i] == elementToSearch) return i;。

- blitz

Answer 6

重点是你可以将for循环转换为while/repeat循环。注意每次都在检查i < length。如果你转换它，

do {
} while (array[i++] != elementToSearch);

那么你就不必进行额外的检查了。（在这种情况下，数组长度现在增加了一个）

- ergonaut

Answer 7

虽然哨兵方法似乎可以在循环的每次迭代中节省一些周期，但这种方法并不是一个好主意：

• 数组必须定义一个额外的插槽，并将其长度传递为比定义长度少1，这会令人困惑且容易出错；
• 数组必须是可修改的；
• 如果搜索函数修改数组以设置哨兵值，则构成了可能令人困惑和意外的副作用；
• 带有哨兵的搜索函数不能用于数组的一部分；
• 哨兵方法本质上不是线程安全的：在2个不同的线程中搜索相同的数组值将无法工作，而从多个线程中搜索常量只读数组则没有问题；
• 优点很小，仅适用于大型数组。如果此搜索成为性能瓶颈，则应该不使用线性扫描。您可以对数组进行排序并使用二进制搜索，或者可以使用哈希表。
• 针对现代CPU的优化编译器可以生成代码，其中两个比较将同时执行，因此不会产生任何开销；

通常来说，搜索功能不应该具有副作用。最小惊讶原则是一个很好的例子。

- chqrlie