go - 如何分组然后在 Go 中将 slice 与重复值合并

Question

对不起，这是我的第一个 Stackoverflow 问题，因此，除了一些帮助之外，任何关于我可以做些什么来改进它的提示/建议都会很棒。

---

问题:

我有一个 slice ，我试图根据特定标准将其分组为更小的 slice 。然后我需要将新创建的 slice 相互合并，如果它们在 slice 中包含任何相同的值。 (本质上，将具有“重叠”值的 slice 附加在一起)。

关于这个问题的一些补充说明:

• 在大多数情况下，原始 slice 中的项目数可能在 1-50 之间，异常值很少超过 100。

• 分组后，“内部” slice 的大小将介于 1-10 个值之间。

• 性能是一个因素，因为此操作将作为网络服务的一部分运行，其中单个请求将执行此操作 20 多次，并且在高峰期每分钟可能有许多(数百至数千)个请求次。但是，代码的清晰度也很重要。

• 我的实现是使用整数，最终的实现会有更复杂的结构，虽然我正在考虑制作一个映射，然后根据键使用下面显示的实现。 这是个好主意吗？

我已将问题分解为几个步骤:

1. 根据标准(初始分组阶段)创建包含值分组的二维 slice
2. 尝试合并包含重复值的 slice 。

---

我遇到了两个问题:

首先，我认为我的实现可能无法很好地扩展，因为它往往有一些嵌套循环(但是，这些循环将在小片段上迭代，所以这可能没问题)

其次，我的实现需要在最后执行额外的步骤来删除重复值，理想情况下我们应该删除它。

---

输入:[ 100, 150, 300, 350, 600, 700 ]预期输出: [[100 150 300 350] [600 700]]

这与 slice 中至少一个其他值在 150 个单位以内的分组值的“选择标准”有关。

和代码 ( Go Playground link ) :

package main

import (
    "fmt"
    "sort"
)

func filter(vs []int, f func(int) bool) []int {
    vsf := make([]int, 0)
    for _, v := range vs {
        if f(v) {
            vsf = append(vsf, v)
        }
    }
    return vsf
}

func unique(intSlice []int) []int {
    keys := make(map[int]bool)
    list := []int{} 
    for _, entry := range intSlice {
        if _, value := keys[entry]; !value {
            keys[entry] = true
            list = append(list, entry)
        }
    }    
    return list
}

func contains(intSlice []int, searchInt int) bool {
    for _, value := range intSlice {
        if value == searchInt {
            return true
        }
    }
    return false
}

func compare(a, b []int) bool {
    if len(a) != len(b) {
        return false
    }

    if (a == nil) != (b == nil) {
        return false
    }

    b = b[:len(a)] 
    for i, v := range a {
        if v != b[i] { 
            return false
        }
    }

    return true
}



func main() {
    fmt.Println("phase 1 - initial grouping")
    s := []int{100, 150, 300, 350, 600, 700}
    g := make([][]int, 0)

    // phase 1
    for _, v := range s {
        t := filter(s, func(i int) bool { return i - v >= -150 && i - v <= 150 })
        for _, v1 := range t {
            t1 := filter(s, func(i int) bool { return i - v1 >= -150 && i - v1 <= 150})
            t = unique(append(t, t1...))
            sort.Ints(t)
        }

        g = append(g, t)
        fmt.Println(g)
    }
    // phase 2
    fmt.Println("phase 2 - merge in place")

    for i, tf := range g {
        for _, death := range tf {
            if i < len(g) - 1 && contains(g[i+1], death) {
                g[i+1] = unique(append(g[i], g[i+1]...))
                g = g[i+1:] 
            } else if i == len(g) - 1 {
                fmt.Println(g[i], g[i-1])
                // do some cleanup to make sure the last two items of the array don't include duplicates
                if compare(g[i-1], g[i]) {
                    g = g[:i]
                }
            }
        }
        fmt.Println(i, g)
    }
}

Answer 1

不确定您实际上在问什么，而且问题没有完全定义。所以这里有一个更高效的版本

如果输入未排序且输出顺序很重要，那么这是一个糟糕的解决方案。

这是 ( on Play )

package main

import (
    "fmt"
)

// Input: [ 100, 150, 300, 350, 600, 700 ] Expected Output: [[100 150 300 350] [600 700]]

func main() {
    input := []int{100, 150, 300, 350, 600, 700}

    fmt.Println("Input:", input)
    fmt.Println("Output:", groupWithin150(input))
}

func groupWithin150(ints []int) [][]int {
    var ret [][]int
    // Your example input was sorted, if the inputs aren't actually sorted, then uncomment this
    // sort.Ints(ints)
    var group []int
    for idx, i := range ints {
        if idx > 0 && i-150 > group[len(group)-1] {
            ret = append(ret, group)
            group = make([]int, 0)
        }
        group = append(group, i)
    }
    if len(group) > 0 {
        ret = append(ret, group)
    }
    return ret
}