golang处理大数据切片去重的算法该怎么写比较高效

Question

我这里准备用go对一个数据量在百万左右的slice进行去重处理，我目前的思路是如下代码：

RemoveDuplicate函数为普通的单线程去重函数。

RemoveDuplicateMultiThread为多线程去重函数，在RemoveDuplicateMultiThread中，我把需要去重的切片list按照CPU核心数量（我的电脑是双核四线程，所以我写死在代码中为4）平均切分，然后依次发射4个goroutine，参数带上之前切分好的四个slice，goroutine中分别对这4个slice进行去重，然后再把结果发送到channel上，最后RemoveDuplicateMultiThread里面channel把所有结果获取完之后再合并。

但是我这个思路只能在重复数据很小，并且要求不是非常严谨的情况下才有用，如果切割之后的四个切片里面互相有重复数据，还是无法实现去重，感觉这算法有点问题，谁能帮忙看看怎么改进一下啊

而且我在实际测试的时候发现CPU占用率最高为75%而不是100%，这是为什么呢？Windows任务管理器里面看到该go进程的线程数为6，这能说明什么呢？

操作系统：Windows 7 64bit，CPU：i5-4210M，8G内存

func RemoveDuplicate(list []string, ret chan []string) {
    var x []string = []string{}
    for _, i := range list {
        if len(x) == 0 {
            x = append(x, i)
        } else {
            for k, v := range x {
                if i == v {
                    break
                }
                if k == len(x)-1 {
                    x = append(x, i)
                }
            }
        }
    }
    //return x
    ret <- x
}

func RemoveDuplicateMultiThread(list []string) (ret []string) {
    listQueue := make(chan []string)
    var listList [4][]string
    listLen := len(list)
    sliceLen := int(listLen / 4)
    lastSliceLen := listLen % 4
    var start, end int
    for i := 0; i < 4-1; i++ {
        start = i * sliceLen
        end = (i + 1) * sliceLen
        listList[i] = list[start:end]
    }
    listList[4-1] = list[:lastSliceLen]
    for i := 0; i < 4-1; i++ {
        go RemoveDuplicate(listList[i], listQueue)
    }
    ret = <-listQueue
    ret = append(ret, ret...)
    return ret
}

Answer 1

可以使用空间换时间的方式，多定义一个map来判断元素是否重复

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    arr := gen()
    fmt.Println(len(arr))

    resArr := removeDuplicate(arr)
    fmt.Println(len(resArr))
}

// 模拟生成一百万随机数
func gen() []int {
    start := time.Now()
    arr := make([]int, 1000000)
    s := rand.NewSource(time.Now().UnixNano() + rand.Int63n(9999))
    r := rand.New(s)
    for i := 0; i < 1000000; i++ {
        arr[i] = r.Intn(1000000)
    }

    fmt.Println("gen time:", fmt.Sprintf("%vms", (time.Now().UnixNano()-start.UnixNano())/1e+6))
    return arr
}

// 去重
func removeDuplicate(arr []int) []int {
    start := time.Now()

    resArr := make([]int, 0)
    tmpMap := make(map[int]interface{})
    for _, val := range arr {
        if _, ok := tmpMap[val]; !ok {
            resArr = append(resArr, val)
            tmpMap[val] = struct{}{}
        }
    }

    fmt.Println("removeDuplicate time:", fmt.Sprintf("%vms", (time.Now().UnixNano()-start.UnixNano())/1e+6))
    return resArr
}

如果使用多线程方式，需要注意map的不安全问题。