java - 尝试在 Go 中实现 Java Guava sets.difference

Question

Java Guava Sets.difference 行为:

Known = ["v1","v2"]; Incoming = ["v2","v3","v4"]

incoming = ["v2","v3","v4"]; knownUpdated = ["v2"]

Sets.difference(Known, Incoming) = v1 (To be removed)

Sets.difference(incoming, knownUpdated) = v3,v4 (To be added)

我在 Go 中尝试的是给出以下区别:

Output := [v1 v3 v4] (known, Incoming) 

func Difference(slice1 []string, slice2 []string) []string {
    var diff []string

    for i := 0; i < 2; i++ {
        for _, s1 := range slice1 {
            found := false
            for _, s2 := range slice2 {
                if s1 == s2 {
                    found = true
                    break
                }
            }

            if !found {
                diff = append(diff, s1)
            }
        }
        if i == 0 {
            slice1, slice2 = slice2, slice1
        }
    }

    return diff
}

它给出了对称差异，但我需要 Guava sets.difference 的行为。我知道我的功能有问题。摘自public static Sets.SetView difference(Set set1, Set set2)的guava文档:返回的set包含了set1包含，set2不包含的所有元素

Answer 1

最直接且易于理解的解决方案是使用映射 - 如果您仅使用键而丢弃值，它们与许多其他集合实现共享相似的属性 (O(1) 查找 * ，唯一键，无序)。在这一点上，它实际上是微不足道的:

func Difference(slice1 []string, slice2 []string) []string {
    // Create proper "set" (Maps have unordered pairs and the keys are unique;
    // lookup to check whether value is present is O(1), similar to other
    // implementations)
    m := make(map[string]struct{}, len(slice1))
    for _, el := range slice1 {
        m[el] = struct{}{}
    }

    // Remove values from slice1 present in slice2
    for _, el := range slice2 {
        delete(m, el)
    }

    // Note that res will be non-deterministic: the order of iteration over maps
    // is made random on purpose by Go itself
    res := make([]string, 0, len(m))
    for k := range m {
        res = append(res, k)
    }
    return res
}

Demo