算法中的哨兵

在地面上有200个箱子连续排列着，现在需要看一下前面100个箱子中有没有苹果。一般情况下，会怎么做呢？

下面用代码来模拟一下。

package main

import (
    "fmt"
)

func main() {
    s := make([]int, 200)

    for i := 0; i < 100; i++ {
        if s[i] == -1 {
            fmt.Println("苹果")
            break
        }
    }
}

如代码所示，我们需要从第1个箱子开始找，每打开一个箱子都要判断一下该箱子是不是前100个，然后再看看里面有没有苹果(-1)。一切都那么自然，但有没有更好的办法呢？

每次都打开箱子看看里面有没有苹果，这应该是不能省略的步骤；至于判断箱子是不是前100个，我们可以在前100个的位置划条边界，但似乎还是没有什么改变，还是要每次看一下是不是到了边界。再想想，每次打开箱子都要看一下有没有苹果，如果看到苹果就会停止，这就有文章可作了。我们就在第101个箱子里面放一下苹果，这样在第101个箱子就必然会停止找箱子，只要在找到苹果之后看了下苹果所在的箱子是不是第101个箱子就行了。

package main

import (
    "fmt"
)

func main() {
    s := make([]int, 200)
    s[100] = -1

    for i := 0; ; i++ {
        if s[i] == -1 {
            if i != 100 {
                fmt.Println("苹果")
            }
            break
        }
    }
}

以上代码每次循环都少了判断i < 100，取而代之的是在找到苹果(-1)后再判断i != 100。以上的s[100] = -1就是哨兵，哨兵守卫着代码的边界，避免了越界的可能。哨兵的存在，意味着程序可以大大减少执行时间。

package main

import (
    "fmt"
    "time"
)

func main() {
    s := make([]int, 100000000)

    t1 := time.Now().UnixNano()
    for i := 0; i < len(s); i++ {
        if s[i] == -1 {
            fmt.Println("苹果")
            break
        }
    }
    t2 := time.Now().UnixNano()
    fmt.Println(t2 - t1)

    s2 := append(s, -1)
    t3 := time.Now().UnixNano()
    for i := 0; ; i++ {
        if s2[i] == -1 {
            if i != len(s) {
                fmt.Println("苹果")
            }
            break
        }
    }
    t4 := time.Now().UnixNano()
    fmt.Println(t4 - t3)
}

$ go run main.go
706820000
260953000

哨兵，哨兵，你真了不得。

William A

算法中的哨兵

Search

Table of Contents