Go中的切片元素访问复杂性是什么？

Question

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

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

并且平均长度s大于后缀的长度.因此,这表明如果切片更大,访问元素需要更长的时间？

功能是:

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
}

更新:重现结果install fetch使用带有大型语料库的go-porterstemmer fork(我使用440mb文件).

Answer 1

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

正如您所料,以下基准测试表明,平均读取切片的第二个元素与平均读取切片的第2691个元素之间没有区别,13439773 ns/op与13460864 ns/op之间的904,061个字节切片元素.两个基准测试都使用相同的基础数据阵列.索引的索引是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功能.

包字节

func HasSuffix

func HasSuffix(s, suffix []byte) bool

HasSuffix测试字节切片s是否以后缀结尾.