Go删除切片中的重复元素

Go语言虽然包含丰富的标准库，但很多有用的函数还是要自己实现。今天我们要学习的是如何快速的删除切片中的重复元素。假设我们需要写一个函数实现用户ID切片元素去重。

方法1: Go安全方法

该方法在保持原切片不变的情况下很有用。创建一个新的切片只保存不同的元素。我们使用map的键来判别重复元素，map的值为空结构体不占内存。

func RemoveDuplicates(userIDs []int64) []int64 {
    // 只需要检查key，因此value使用空结构体，不占内存
    processed := make(map[int64]struct{})

    uniqUserIDs := make([]int64, 0)
    for _, uid := range userIDs {
        // 如果用户ID已经处理过，就跳过
        if _, ok := processed[uid]; ok {
            continue
        }

        // 将唯一的用户ID加到切片中
        uniqUserIDs = append(uniqUserIDs, uid)

        // 将用户ID标记为已存在
        processed[uid] = struct{}{}
    }

    return uniqUserIDs
}

方法2: 在原切片中移动元素

该方法能满足您的性能要求，并且可以修改原切片。首先对切片排序，然后通过两个迭代器：元素唯一迭代器和常规迭代器。通过一次遍历切片，返回一个包含不同元素的子切片。

import (
    "sort"
)

func RemoveDuplicatesInPlace(userIDs []int64) []int64 {
    // 如果有0或1个元素，则返回切片本身。
    if len(userIDs) < 2 {
        return userIDs
    }

    //  使切片升序排序
    sort.SliceStable(userIDs, func(i, j int) bool { return userIDs[i] < userIDs[j] })

    uniqPointer := 0

    for i := 1; i < len(userIDs); i++ {
        // 比较当前元素和唯一指针指向的元素
        //  如果它们不相同，则将项写入唯一指针的右侧。
        if userIDs[uniqPointer] != userIDs[i] {
            uniqPointer++
            userIDs[uniqPointer] = userIDs[i]
        }
    }

    return userIDs[:uniqPointer+1]
}

基准测试

让我们来测试这两种方法，看看它们在性能上有何不同。我们通过helper函数生成一个随机切片:

func generateSlice() []int64 {
    s := make([]int64, 0, l)

    for i := 0; i < 1_000_000; i++ {
        s = append(s, rand.Int63())
    }

    return s
}

基准测试代码：

func BenchmarkRemoveDuplicates(b *testing.B) {
    s := generateSlice()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        RemoveDuplicates(s)
    }
}

func BenchmarkRemoveDuplicatesInPlace(b *testing.B) {
    s := generateSlice()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        RemoveDuplicatesInPlace(s)
    }
}

1000个随机元素的测试结果：

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkRemoveDuplicates
BenchmarkRemoveDuplicates-8                14552         82441 ns/op       64115 B/op         76 allocs/op
BenchmarkRemoveDuplicatesInPlace
BenchmarkRemoveDuplicatesInPlace-8        238521          4852 ns/op          56 B/op          2 allocs/op

1000k个随机元素结果：

goos: darwin
goarch: amd64
cpu: Intel(R) Core(TM) i5-8257U CPU @ 1.40GHz
BenchmarkRemoveDuplicates
BenchmarkRemoveDuplicates-8                    6     169626486 ns/op    95007038 B/op      38356 allocs/op
BenchmarkRemoveDuplicatesInPlace
BenchmarkRemoveDuplicatesInPlace-8            82      13069547 ns/op          56 B/op          2 allocs/op

很明显第二种方法比第一种快了大概15倍，没有内存分配。第一次方法使用append函数会触发内存分配，元素拷贝影响效率。

总结

现在我们知道如何在Go切片中以不同的方式删除重复元素。根据您的项目和目标，您可以使用适合您需求的最佳方法。