mySlice := make([]uint32, 0, 4294967290)// ... // Sort the slice sort.Slice(mySlice, func(i, j int) bool { x := mySlice[i] y := mySlice[j] return x < y })刪除切片重復(fù)項(xiàng)的最快方法是什么？如何利用切片已排序的事實(shí)？更新我想出了這個(gè)：func RemoveDuplicates(s []uint32) { if len(s) < 2 { return } tmp := make([]uint32, 0, len(s)) for i := uint32(0); i < uint32(len(s)); i++ { // If current is not equal to next then store the current if s[i] != s[i+1] { tmp = append(tmp, s[i]) } } // The last must be stored // Note that if it was repeated, the duplicates are NOT stored before tmp = append(tmp, s[len(s)-1]) // Modify original slice s = nil s = append(s, tmp...)}有什么錯(cuò)誤嗎？有什么錯(cuò)誤嗎？有什么方法可以改進(jìn)嗎？更新如@mh-cbon 所指出的，正確的循環(huán)最大值應(yīng)為：i < uint32(len(s)) - 1for i := uint32(0); i < uint32(len(s)) - 1; i++ {
2 回答
隔江千里
TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超10個(gè)贊
不是關(guān)于最快的答案，而是關(guān)于使用Go語(yǔ)言來(lái)優(yōu)化一段代碼的方法的逐步回答。
有關(guān)什么是最快的非常正式的見(jiàn)解，請(qǐng)參閱 https://stackoverflow.com/a/6072100/4466350
您的代碼有問(wèn)題。始終編寫(xiě)測(cè)試。
一、讓我們用寫(xiě)一個(gè)主
package main
import (
"math/rand"
"sort"
)
func main() {
}
func randSlice(max int) (ret []uint32) {
// we should check that max does not exceed maxUINT32
ret = make([]uint32, 0, max)
r := rand.New(rand.NewSource(99))
for i := 0; i < max; i++ {
ret = append(ret, uint32(r.Intn(max)))
}
sort.Slice(ret, func(i, j int) bool {
return ret[i] < ret[j]
})
return
}
func dedup1(s []uint32) []uint32 {
if len(s) < 2 {
return s
}
tmp := make([]uint32, 0, len(s))
for i := uint32(0); i < uint32(len(s)); i++ {
// If current is not equal to next then store the current
if s[i] != s[i+1] {
tmp = append(tmp, s[i])
}
}
// The last must be stored
// Note that if it was repeated, the duplicates are NOT stored before
tmp = append(tmp, s[len(s)-1])
// Modify original slice
s = nil
s = append(s, tmp...)
return s
}
以及隨附的測(cè)試
package main
import "testing"
func TestDedup1(t *testing.T) {
s := randSlice(10)
res := dedup1(s)
uniq := map[uint32]bool{}
for _, r := range res {
_, ok := uniq[r]
if ok {
t.Fatalf("found duplicates\ninput=%#v\nresult=%#v\n", s, res)
}
uniq[r] = true
}
}
運(yùn)行這個(gè)我們得到
$ go test -v .
=== RUN TestDedup1
--- FAIL: TestDedup1 (0.00s)
panic: runtime error: index out of range [10] with length 10 [recovered]
panic: runtime error: index out of range [10] with length 10
goroutine 18 [running]:
testing.tRunner.func1.1(0x536680, 0xc0000da040)
/home/mh-cbon/.gvm/gos/go1.15.2/src/testing/testing.go:1076 +0x30d
testing.tRunner.func1(0xc000082600)
/home/mh-cbon/.gvm/gos/go1.15.2/src/testing/testing.go:1079 +0x41a
panic(0x536680, 0xc0000da040)
/home/mh-cbon/.gvm/gos/go1.15.2/src/runtime/panic.go:969 +0x175
test/d/dup.dedup1(0xc000094060, 0xa, 0xa, 0xa, 0x6124a0, 0xc00003c770)
/home/mh-cbon/gow/src/test/d/dup/main.go:32 +0x248
test/d/dup.TestDedup1(0xc000082600)
/home/mh-cbon/gow/src/test/d/dup/main_test.go:7 +0x70
testing.tRunner(0xc000082600, 0x54fbf0)
/home/mh-cbon/.gvm/gos/go1.15.2/src/testing/testing.go:1127 +0xef
created by testing.(*T).Run
/home/mh-cbon/.gvm/gos/go1.15.2/src/testing/testing.go:1178 +0x386
FAIL test/d/dup 0.006s
FAIL
我們通過(guò)適當(dāng)?shù)貦z查切片邊界來(lái)解決此問(wèn)題。
在 中，將此條件更改為 ，或者更好的是，將迭代最大值減少 1dedup1if s[i] != s[i+1] {if i+1 < uint32(len(s)) && s[i] != s[i+1] {for i := uint32(0); i < uint32(len(s))-1; i++ {
接下來(lái)，編寫(xiě)一個(gè)函數(shù)來(lái)生成具有隨機(jī)重復(fù)項(xiàng)的切片。
func randSliceWithDups(max int) (ret []uint32) {
ret = randSlice(max / 2)
ret = append(ret, ret...)
sort.Slice(ret, func(i, j int) bool {
return ret[i] < ret[j]
})
return
}
寫(xiě)入獲取切片，例如randSliceWithDups(50)[0 0 1 1 2 2 3 3 3 3 4 4 5 5 5 5 6 6 6 6 7 7 8 8 9 9 9 9 12 12 13 13 18 18 18 18 18 18 19 19 20 20 20 20 21 21 22 22 24 24]
再次更新測(cè)試
func TestDedup1_with_dups(t *testing.T) {
s := randSliceWithDups(10)
res := dedup1(s)
uniq := map[uint32]bool{}
for _, r := range res {
_, ok := uniq[r]
if ok {
t.Fatalf("found duplicates\ninput=%#v\nresult=%#v\n", s, res)
}
uniq[r] = true
}
}
接下來(lái)，添加一個(gè)基準(zhǔn)測(cè)試;它將幫助我們發(fā)現(xiàn)性能問(wèn)題并隨著時(shí)間的推移保持性能。
func BenchmarkDedup1_1000(b *testing.B) {
s := randSliceWithDups(100)
b.ResetTimer()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
_ = dedup1(s)
}
}
運(yùn)行這個(gè)我們得到：
$ go test -v . -bench=.
=== RUN TestDedup1
--- PASS: TestDedup1 (0.00s)
=== RUN TestDedup1_with_dups
--- PASS: TestDedup1_with_dups (0.00s)
goos: linux
goarch: amd64
pkg: test/d/dup
BenchmarkDedup1_1000
BenchmarkDedup1_1000-4 172087 6353 ns/op 5504 B/op 2 allocs/op
PASS
ok test/d/dup 1.174s
讓我們陳述一下，每個(gè)人都發(fā)現(xiàn)閱讀你的初始代碼，甚至沒(méi)有編寫(xiě)你正在分配的基準(zhǔn)測(cè)試。
這就提出了一個(gè)問(wèn)題，即確定是否允許您就地修改輸入切片。如果您可以將其更改到位，我們可能會(huì)利用這一點(diǎn)來(lái)防止該分配并加快您的程序。
一種從頭開(kāi)始編寫(xiě)的解決方案（考慮在網(wǎng)站等極客網(wǎng)站上搜索普遍接受的解決方案），是迭代切片并維護(hù)下一個(gè)要寫(xiě)入的位置的索引。找到非重復(fù)項(xiàng)時(shí)，將非重復(fù)項(xiàng)保存到此最后一個(gè)位置，然后將該索引遞增 1。最后，將切片向上返回為遞增索引的值。
func dedup2(s []uint32) []uint32 {
if len(s) < 2 {
return s
}
var e int
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
continue
}
s[e] = s[i]
e++
}
return s[:e]
}
同樣，添加測(cè)試和工作臺(tái)，并檢查結(jié)果。
func TestDedup2(t *testing.T) {
s := randSlice(10)
res := dedup2(s)
uniq := map[uint32]bool{}
for _, r := range res {
_, ok := uniq[r]
if ok {
t.Fatalf("found duplicates\ninput=%#v\nresult=%#v\n", s, res)
}
uniq[r] = true
}
}
func TestDedup2_with_dups(t *testing.T) {
s := randSliceWithDups(10)
res := dedup2(s)
uniq := map[uint32]bool{}
for _, r := range res {
_, ok := uniq[r]
if ok {
t.Fatalf("found duplicates\ninput=%#v\nresult=%#v\n", s, res)
}
uniq[r] = true
}
}
func BenchmarkDedup2_1000(b *testing.B) {
s := randSliceWithDups(100)
b.ResetTimer()
b.ReportAllocs()
for i := 0; i < b.N; i++ {
_ = dedup2(s)
}
}
其產(chǎn)生：
$ go test -v . -bench=.
=== RUN TestDedup1
--- PASS: TestDedup1 (0.00s)
=== RUN TestDedup1_with_dups
--- PASS: TestDedup1_with_dups (0.00s)
=== RUN TestDedup2
--- PASS: TestDedup2 (0.00s)
=== RUN TestDedup2_with_dups
--- PASS: TestDedup2_with_dups (0.00s)
goos: linux
goarch: amd64
pkg: test/d/dup
BenchmarkDedup1_1000
BenchmarkDedup1_1000-4 1764574 673 ns/op 544 B/op 2 allocs/op
BenchmarkDedup2_1000
BenchmarkDedup2_1000-4 7758907 152 ns/op 0 B/op 0 allocs/op
PASS
ok test/d/dup 3.224s
4倍的改進(jìn)！涼！下一步是什么？接下來(lái)是找到一個(gè)更好的算法，它產(chǎn)生更少的執(zhí)行，更少的查找等等。
不過(guò)，最后一個(gè)版本包含一個(gè)錯(cuò)誤！你發(fā)現(xiàn)它了嗎？
請(qǐng)參閱此測(cè)試，它比另一個(gè)測(cè)試更好，因?yàn)樗灰蕾囉陔S機(jī)數(shù)，而是依賴于具有強(qiáng)相等性檢查的靜態(tài)值。使用這些類型的測(cè)試，您可以定制輸入以檢查細(xì)粒度情況。
func TestDedup2_static(t *testing.T) {
type expectation struct {
input []uint32
want []uint32
}
expectations := []expectation{
expectation{
input: []uint32{0, 0, 1, 2, 3, 3, 3, 4, 4, 5},
want: []uint32{0, 1, 2, 3, 4, 5},
},
expectation{
input: []uint32{0, 1, 2, 3, 3, 3, 4, 4, 5},
want: []uint32{0, 1, 2, 3, 4, 5},
},
}
for _, e := range expectations {
res := dedup2(e.input)
if !reflect.DeepEqual(res, e.want) {
t.Fatalf("invlaid result, wanted=%#v\ngot=%#v\n", e.want, res)
}
}
}
它使用表驅(qū)動(dòng)器測(cè)試，如 https://dave.cheney.net/2013/06/09/writing-table-driven-tests-in-go 中所述
讓我們解決這個(gè)問(wèn)題：
func dedup2(s []uint32) []uint32 {
if len(s) < 2 {
return s
}
var e int = 1
for i := 1; i < len(s); i++ {
if s[i] == s[i-1] {
continue
}
s[e] = s[i]
e++
}
return s[:e]
}
炎炎設(shè)計(jì)
TA貢獻(xiàn)1808條經(jīng)驗(yàn) 獲得超4個(gè)贊
要?jiǎng)h除切片的重復(fù)元素，您可以創(chuàng)建一個(gè)映射并將切片值指定為映射的鍵，然后循環(huán)訪問(wèn)映射并將鍵值附加到新切片。下面是相同邏輯的代碼：
package main
import (
"fmt"
"sort"
)
func removeDupe(slc []int) []int {
var tmpSlice []int
chkMap := make(map[int]bool)
for _, val := range slc {
chkMap[val] = true
}
for k, _ := range chkMap {
tmpSlice = append(tmpSlice, k)
}
sort.Ints(tmpSlice)
return tmpSlice
}
func main() {
mySlice := []int{1, 2, 3, 4, 5, 1, 2, 3, 9, 0}
formattedSlice := removeDupe(mySlice)
fmt.Println(formattedSlice)
}
輸出：
[0 1 2 3 4 5 9]
- 2 回答
- 0 關(guān)注
- 113 瀏覽
添加回答
舉報(bào)
0/150
提交
取消