arrays - Go 中的 slice 元素访问复杂度是多少？

Question

我认为它是 O(1)，但这是来自 pprof 输出:

140    140  176:    var lastSB byte = s[lenSMinusOne]
88     88   177:    var lastSuffixB byte = suffix[lenSuffixMinusOne]

并且 s 的平均长度大于后缀的长度。因此，这表明如果 slice 越大，访问元素所需的时间越长？

函数是:

func hasSuffix(s, suffix []byte) bool {

    lenSMinusOne      := len(s)      - 1
    lenSuffixMinusOne := len(suffix) - 1

    var lastSB byte = s[lenSMinusOne]
    var lastSuffixB byte = suffix[lenSuffixMinusOne]

    if lenSMinusOne < lenSuffixMinusOne {
        return false
    } else if lastSB != lastSuffixB {
        return false
    } else {
        for i := 0; i < lenSuffixMinusOne ; i++ {
               if suffix[i] != s[lenSMinusOne-lenSuffixMinusOne+i] {
                        return false
               }
        }
    }
    return true
}

更新:要重现结果，请安装 fetch使用 go-porterstemmer fork语料库很大(我用的是 440mb 的文件)。

Answer 1

pprof 在程序执行期间收集样本以照亮热点。使用 testing 包和 go test 运行基准测试。

如您所料，以下基准显示平均读取 slice 的第 2 个元素与平均读取 slice 的第 2691 个元素之间没有区别，13439773 ns/op 与 13460864 ns/op 904,061 字节 slice 元素。两个基准测试使用相同的底层数据数组。索引 slice 是 O(1)。

在您的示例中，您正在从两个具有不同访问模式(外循环与内循环)的不同底层数据数组中读取数据。在具有复杂内存管理和优化的现代处理器上，您不应期望得到相同的结果。

$ go version
go version devel +3ae7a530dd4e Sat Dec 28 09:37:54 2013 -0800 linux/amd64
$ go test -bench=IndexWord
904061 2 2690.8131199111563
testing: warning: no tests to run
PASS
BenchmarkIndexWordLong       100      13460864 ns/op
BenchmarkIndexWordShort      100      13439773 ns/op
ok      bench   7.814s
$

.

package main

import (
    "bytes"
    "fmt"
    "io/ioutil"
    "testing"
)

var (
    Words    [][]byte
    ShortLen = 2
)

func IndexWord(b *testing.B, words [][]byte) {
    b.ResetTimer()
    b.StartTimer()
    var char byte
    for i := 0; i < b.N; i++ {
        for _, word := range words {
            char = word[len(word)-1]
        }
    }
    _ = char
}

func BenchmarkIndexWordLong(b *testing.B) {
    words := make([][]byte, len(Words))
    for i, word := range Words {
        words[i] = word
    }
    IndexWord(b, words)
}

func BenchmarkIndexWordShort(b *testing.B) {
    words := make([][]byte, len(Words))
    for i, word := range Words {
        if len(word) > ShortLen {
            word = word[:ShortLen]
        }
        words[i] = word
    }
    IndexWord(b, words)
}

func init() {
    // The Complete Works of William Shakespeare
    // http://www.gutenberg.org/cache/epub/100/pg100.txt
    text, err := ioutil.ReadFile(`/home/peter/pg100.txt`)
    if err != nil {
        panic(err)
    }
    var n, short, long int64
    Words = bytes.Fields(text)
    for i, word := range Words {
        word = bytes.Repeat(word, 600) // Requires 4GB memory
        Words[i] = word
        n++
        long += int64(len(word))
        shortLen := ShortLen
        if len(word) < ShortLen {
            shortLen = len(word)
        }
        short += int64(shortLen)
    }
    fmt.Println(n, float64(short)/float64(len(Words)), float64(long)/float64(len(Words)))
}

---

你的 hasSuffix 函数的代码看起来像是从另一种语言直接移植过来的；它看起来不像是为 Go 编写的。这是我的重写。

func hasSuffix(s, suffix []byte) bool {
    if len(s) < len(suffix) {
        return false
    }
    s = s[len(s)-len(suffix):]
    for i, x := range suffix {
        if x != s[i] {
            return false
        }
    }
    return true
}

此外，Go 有一个 bytes.HasSuffix 函数。

Package bytes

func HasSuffix

func HasSuffix(s, suffix []byte) bool

HasSuffix tests whether the byte slice s ends with suffix.