那些遇到过的问题

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

use*_*291 0 sorting duplicates go 

    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
        })
Run Code Online (Sandbox Code Playgroud)

删除切片重复项的最快方法是什么？

我如何利用切片已经排序的事实？

更新

我想出了这个：

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...)
}
Run Code Online (Sandbox Code Playgroud)

有什么错误吗？有什么错误吗？有什么办法改善吗？

更新

正如 @mh-cbon 所指出的，正确的循环最大值应该是i < uint32(len(s)) - 1：

for i := uint32(0); i < uint32(len(s)) - 1; i++ {
Run Code Online (Sandbox Code Playgroud)

小智 7

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

有关最快的非常正式的见解，请参阅/sf/answers/425047031/

你的代码有问题。总是写一个测试。

首先，让我们写一个main

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
}
Run Code Online (Sandbox Code Playgroud)

以及附带的测试

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
    }
}
Run Code Online (Sandbox Code Playgroud)

运行这个我们得到

$ 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
Run Code Online (Sandbox Code Playgroud)

我们通过适当检查切片边界来修复此问题。

在 中dedup1，将此条件更改if s[i] != s[i+1] {为if i+1 < uint32(len(s)) && s[i] != s[i+1] {，或者更好的是，将迭代最大值减少 1for i := uint32(0); i < uint32(len(s))-1; i++ {

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

$ 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
Run Code Online (Sandbox Code Playgroud)

写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 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
}
Run Code Online (Sandbox Code Playgroud)

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

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
    }
}
Run Code Online (Sandbox Code Playgroud)

运行这个我们得到：

$ 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
Run Code Online (Sandbox Code Playgroud)

让我们声明一个明显的事实，每个人都发现阅读您的初始代码，甚至没有编写您正在分配的基准。

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

一种从头开始编写的解决方案（考虑在 geekforgeeks 等网站上搜索普遍接受的解决方案）是迭代切片并维护下一个要写入的位置的索引。当找到非重复项时，将非重复项保存到最后一个位置，然后将该索引增加 1。最后，将切片返回到递增索引的值。

func BenchmarkDedup1_1000(b *testing.B) {
    s := randSliceWithDups(100)
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        _ = dedup1(s)
    }
}
Run Code Online (Sandbox Code Playgroud)

再次添加测试和工作台，并检查结果。

$ 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
Run Code Online (Sandbox Code Playgroud)

其产量：

$ 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
Run Code Online (Sandbox Code Playgroud)

4 倍改进！凉爽的 ！下一步是什么 ？接下来是找到一种更好的算法，它可以减少执行次数、查找次数等。

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

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

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]
}
Run Code Online (Sandbox Code Playgroud)

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

让我们解决这个问题：

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)
    }
}
Run Code Online (Sandbox Code Playgroud)

归档时间：

查看次数：

5941 次

最近记录：

2 年，6 月 前
用于删除字符串数组中重复项的最佳算法 8
更多相关链接
相关归档
什么是go语言IDE支持的状态？ 15
基于对象属性排序数组 - Javascript 13
cgo如何处理信号？ 9
按插入顺序检索核心数据实体 4
使用 Golang SDK 不会过期的 S3 对象 4
在MatLAB中从数组中获得最接近零的值？ 3
最快的无条件排序算法 3
解析负载与“无服务器调用本地”不同，与在 APIGateway 后面部署时不同 3
Flutter DataTable 中的列值排序 3
仅删除Mysql中的重复记录 1
难疑归档
如何重命名本地Git分支？ 8033
为什么我不应该在PHP中使用mysql_*函数？ 2432
忽略已提交到Git存储库的文件 2429
为什么我的JavaScript在所请求的资源上出现"No'Access-Control-Allow-Origin'标头"错误,当Postman没有？ 2320
.prop()vs .attr() 2249
如何在不安装Ms Office的情况下在C#中创建Excel(.XLS和.XLSX)文件？ 1804
单击div到底层元素 1500
你如何存放未跟踪的文件？ 1287
处理"java.lang.OutOfMemoryError:PermGen space"错误 1215
如何在Java中创建通用数组？ 1045