删除已排序 Go 切片重复项的最快方法

Question

 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        })删除切片重复项的最快方法是什么？如何利用切片已排序的事实？更新我想出了这个：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...)}有什么错误吗？有什么错误吗？有什么方法可以改进吗？更新如@mh-cbon 所指出的，正确的循环最大值应为：i < uint32(len(s)) - 1for i := uint32(0); i < uint32(len(s)) - 1; i++ {

Answer 1

不是关于最快的答案，而是关于使用Go语言来优化一段代码的方法的逐步回答。

有关什么是最快的非常正式的见解，请参阅 https://stackoverflow.com/a/6072100/4466350

您的代码有问题。始终编写测试。

一、让我们用写一个主

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

}

以及随附的测试

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

    }

}

运行这个我们得到

$ 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

我们通过适当地检查切片边界来解决此问题。

在 中，将此条件更改为 ，或者更好的是，将迭代最大值减少 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++ {

接下来，编写一个函数来生成具有随机重复项的切片。

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

}

写入获取切片，例如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]

再次更新测试

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

    }

}

接下来，添加一个基准测试;它将帮助我们发现性能问题并随着时间的推移保持性能。

func BenchmarkDedup1_1000(b *testing.B) {

    s := randSliceWithDups(100)

    b.ResetTimer()

    b.ReportAllocs()

    for i := 0; i < b.N; i++ {

        _ = dedup1(s)

    }

}

运行这个我们得到：

$ 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

让我们陈述一下，每个人都发现阅读你的初始代码，甚至没有编写你正在分配的基准测试。

这就提出了一个问题，即确定是否允许您就地修改输入切片。如果您可以将其更改到位，我们可能会利用这一点来防止该分配并加快您的程序。

一种从头开始编写的解决方案（考虑在网站等极客网站上搜索普遍接受的解决方案），是迭代切片并维护下一个要写入的位置的索引。找到非重复项时，将非重复项保存到此最后一个位置，然后将该索引递增 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]

}

同样，添加测试和工作台，并检查结果。

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)

    }

}

其产生：

$ 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倍的改进！凉！下一步是什么？接下来是找到一个更好的算法，它产生更少的执行，更少的查找等等。

不过，最后一个版本包含一个错误！你发现它了吗？

请参阅此测试，它比另一个测试更好，因为它不依赖于随机数，而是依赖于具有强相等性检查的静态值。使用这些类型的测试，您可以定制输入以检查细粒度情况。

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)

        }

    }

}

它使用表驱动器测试，如 https://dave.cheney.net/2013/06/09/writing-table-driven-tests-in-go 中所述

让我们解决这个问题：

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]

}

Answer 2

要删除切片的重复元素，您可以创建一个映射并将切片值指定为映射的键，然后循环访问映射并将键值附加到新切片。下面是相同逻辑的代码：

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]