Попытка реализовать Java Guava sets.difference In Go - PullRequest
Новая
       9

Попытка реализовать Java Guava sets.difference In Go

0 голосов
/ 27 сентября 2018

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
}

Это дает симметричную разницу, но мне нужно поведениеГуава устанавливает.Я знаю, что-то не так с моим функционалом.Из документации по гуаве public static Sets.SetView difference(Set set1, Set set2): возвращенный набор содержит все элементы, которые содержатся в set1 и не содержатся в set2

1 Ответ

0 голосов
/ 27 сентября 2018

Самым простым и понятным решением является использование карт - если вы используете только ключи, отбрасывая значения, они имеют свойства, аналогичные многим другим реализациям множеств (O(1) lookup *, уникальные ключи, неупорядоченные).В этот момент это на самом деле довольно тривиально: 

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
}

Демо

...