我編寫了這個函數uniq，它接受 s 的排序切片int并返回刪除了重復項的切片：func uniq(x []int) []int { i := 0 for i < len(x)-1 { if x[i] == x[i+1] { copy(x[i:], x[i+1:]) x = x[:len(x)-1] } else { i++ } } return x}和uniq2，重寫uniq具有相同的結果：func uniq2(x []int) []int { i := 0 l := len(x) for i < l-1 { if x[i] == x[i+1] { copy(x[i:], x[i+1:]) l-- } else { i++ } } return x[:l]}這兩個函數之間的唯一區別是，在 中，我不是每次都uniq2切片x 和直接訪問，而是保存到一個變量 并在每次移動切片時遞減它。len(x)len(x)l我認為這uniq2會比uniq 因為len(x)不再稱為迭代要快一點，但實際上，它慢得莫名其妙。通過這個生成隨機排序切片并調用uniq/ uniq21000 次的測試，我在 Linux 上運行它：func main() { rand.Seed(time.Now().Unix()) for i := 0; i < 1000; i++ { _ = uniq(genSlice()) //_ = uniq2(genSlice()) }}func genSlice() []int { x := make([]int, 0, 1000) for num := 1; num <= 10; num++ { amount := rand.Intn(1000) for i := 0; i < amount; i++ { x = append(x, num) } } return x}$ go build uniq.go$ time ./uniquniq通常需要5--6秒才能完成。whileuniq2慢兩倍多，需要 12--15 秒。為什么我將切片長度保存到變量的地方比我直接調用的地方uniq2慢得多？uniqlen不應該稍微快點嗎？
1 回答
慕婉清6462132
TA貢獻1804條經驗 獲得超2個贊
您期望大致相同的執行時間，因為您認為它們做大致相同的事情。
這兩個函數之間的唯一區別是，在 中，我不是每次都
uniq2切片x和直接訪問，而是保存到一個變量并在每次移動切片時遞減它。len(x)len(x)l
這是錯誤的。
第一個版本：
copy(x[i:], x[i+1:]) x = x[:len(x)-1]
第二個是：
copy(x[i:], x[i+1:]) l--
第一個區別是第一個分配（復制）一個切片頭，它是一個reflect.SliceHeader值，是 3 個整數（在 64 位架構上為 24 字節），同時l--進行簡單的遞減，速度要快得多。
但主要區別并非源于此。主要區別在于，由于第一個版本更改了x切片（標頭、包括的長度），您最終復制的元素越來越少，而第二個版本沒有更改x，并且總是復制到切片的末尾。x[i+1:]相當于x[x+1:len(x)].
為了演示，假設您傳遞了一個長度為 10 且所有元素都相等的切片。第一個版本將首先復制 9 個元素，然后是 8 個，然后是 7 個等。第二個版本將首先復制 9 個元素，然后再復制 9 個，然后再復制 9 個，依此類推。
讓我們修改您的函數以計算復制元素的數量：
func uniq(x []int) []int {
count := 0
i := 0
for i < len(x)-1 {
if x[i] == x[i+1] {
count += copy(x[i:], x[i+1:])
x = x[:len(x)-1]
} else {
i++
}
}
fmt.Println("uniq copied", count, "elements")
return x
}
func uniq2(x []int) []int {
count := 0
i := 0
l := len(x)
for i < l-1 {
if x[i] == x[i+1] {
count += copy(x[i:], x[i+1:])
l--
} else {
i++
}
}
fmt.Println("uniq2 copied", count, "elements")
return x[:l]
}
測試它：
uniq(make([]int, 1000))
uniq2(make([]int, 1000))
輸出是：
uniq copied 499500 elements
uniq2 copied 998001 elements
uniq2()復制兩倍的元素！
如果我們用隨機切片測試它：
uniq(genSlice())
uniq2(genSlice())
輸出是：
uniq copied 7956671 elements
uniq2 copied 11900262 elements
同樣，uniq2()復制大約 1.5 倍的元素?。ǖ@在很大程度上取決于隨機數。）
嘗試Go Playground上的示例。
“修復”是修改uniq2()復制直到l：
copy(x[i:], x[i+1:l])
l--
通過這種“適當”的改變，性能大致相同。
- 1 回答
- 0 關注
- 106 瀏覽
添加回答
舉報
0/150
提交
取消