我編寫了這個(gè)函數(shù)uniq，它接受 s 的排序切片int并返回刪除了重復(fù)項(xiàng)的切片：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具有相同的結(jié)果：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]}這兩個(gè)函數(shù)之間的唯一區(qū)別是，在 中，我不是每次都uniq2切片x 和直接訪問，而是保存到一個(gè)變量 并在每次移動(dòng)切片時(shí)遞減它。len(x)len(x)l我認(rèn)為這uniq2會(huì)比uniq 因?yàn)閘en(x)不再稱為迭代要快一點(diǎn)，但實(shí)際上，它慢得莫名其妙。通過這個(gè)生成隨機(jī)排序切片并調(diào)用uniq/ uniq21000 次的測(cè)試，我在 Linux 上運(yùn)行它：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 秒。為什么我將切片長(zhǎng)度保存到變量的地方比我直接調(diào)用的地方uniq2慢得多？uniqlen不應(yīng)該稍微快點(diǎn)嗎？
1 回答
慕婉清6462132
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超2個(gè)贊
您期望大致相同的執(zhí)行時(shí)間，因?yàn)槟J(rèn)為它們做大致相同的事情。
這兩個(gè)函數(shù)之間的唯一區(qū)別是，在 中，我不是每次都
uniq2切片x和直接訪問，而是保存到一個(gè)變量并在每次移動(dòng)切片時(shí)遞減它。len(x)len(x)l
這是錯(cuò)誤的。
第一個(gè)版本：
copy(x[i:], x[i+1:]) x = x[:len(x)-1]
第二個(gè)是：
copy(x[i:], x[i+1:]) l--
第一個(gè)區(qū)別是第一個(gè)分配（復(fù)制）一個(gè)切片頭，它是一個(gè)reflect.SliceHeader值，是 3 個(gè)整數(shù)（在 64 位架構(gòu)上為 24 字節(jié)），同時(shí)l--進(jìn)行簡(jiǎn)單的遞減，速度要快得多。
但主要區(qū)別并非源于此。主要區(qū)別在于，由于第一個(gè)版本更改了x切片（標(biāo)頭、包括的長(zhǎng)度），您最終復(fù)制的元素越來越少，而第二個(gè)版本沒有更改x，并且總是復(fù)制到切片的末尾。x[i+1:]相當(dāng)于x[x+1:len(x)].
為了演示，假設(shè)您傳遞了一個(gè)長(zhǎng)度為 10 且所有元素都相等的切片。第一個(gè)版本將首先復(fù)制 9 個(gè)元素，然后是 8 個(gè)，然后是 7 個(gè)等。第二個(gè)版本將首先復(fù)制 9 個(gè)元素，然后再?gòu)?fù)制 9 個(gè)，然后再?gòu)?fù)制 9 個(gè)，依此類推。
讓我們修改您的函數(shù)以計(jì)算復(fù)制元素的數(shù)量：
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]
}
測(cè)試它：
uniq(make([]int, 1000))
uniq2(make([]int, 1000))
輸出是：
uniq copied 499500 elements
uniq2 copied 998001 elements
uniq2()復(fù)制兩倍的元素！
如果我們用隨機(jī)切片測(cè)試它：
uniq(genSlice())
uniq2(genSlice())
輸出是：
uniq copied 7956671 elements
uniq2 copied 11900262 elements
同樣，uniq2()復(fù)制大約 1.5 倍的元素?。ǖ@在很大程度上取決于隨機(jī)數(shù)。）
嘗試Go Playground上的示例。
“修復(fù)”是修改uniq2()復(fù)制直到l：
copy(x[i:], x[i+1:l])
l--
通過這種“適當(dāng)”的改變，性能大致相同。
- 1 回答
- 0 關(guān)注
- 113 瀏覽
添加回答
舉報(bào)
0/150
提交
取消