Vergleichen Sie zwei Scheiben

Wenn die Reihenfolge nicht wichtig ist und die Mengen groß sind, sollten Sie eine Mengenimplementierung verwenden und deren Vergleiche verwenden, um sie zu vergleichen.

Sets sind nicht Teil der Standardbibliothek, aber Sie können diese Library beispielsweise verwenden. Sie können damit einen Satz automatisch aus einem Slice initialisieren. https://github.com/deckarep/golang-set

Etwas wie das:

import (
    set "github.com/deckarep/golang-set"
    "fmt"
    )

func main() {
    //note that the set accepts []interface{}
    X := []interface{}{10, 12, 12, 12, 13}
    Y := []interface{}{12, 14, 15}

    Sx := set.NewSetFromSlice(X)
    Sy := set.NewSetFromSlice(Y)
    result1 := Sx.Difference(Sy)
    result2 := Sy.Difference(Sx)

    fmt.Println(result1)
    fmt.Println(result2)
}

Alle Lösungen können die gestellte Frage nicht genau beantworten. Anstelle der Unterschiede in den Schichten geben die Lösungen die Unterschiede der Elementgruppen in den Schichten an.

Anstelle des beabsichtigten Beispiels von:

    X := []int{10, 12, 12, 12, 13}
    Y := []int{12, 14, 15}

func compare(X, Y []int)  

calling compare(X, Y)   
    result1 := []int{10, 12, 12, 13} // if you're looking for elements in slice X that are not in slice Y

calling compare(Y, X)
    result2 := []int{14, 15}

Die bereitgestellten Lösungen führen zu:

result1 := []int{10,13}
result2 := []int{14,15}

Um genau das Beispielergebnis zu erhalten, ist eine andere Methode erforderlich. Hier sind zwei Lösungen:

Wenn die Slices bereits sortiert sind:

Diese Lösung kann schneller sein, wenn Sie Ihre Slices sortieren und Compare anrufen. Es wird auf jeden Fall schneller, wenn Ihre Slices bereits sortiert sind.

func compare(X, Y []int) []int {
    difference := make([]int, 0)
    var i, j int
    for i < len(X) && j < len(Y) {
        if X[i] < Y[j] {
            difference = append(difference, X[i])
            i++
        } else if X[i] > Y[j] {
            j++
        } else { //X[i] == Y[j]
            j++
            i++
        }
    }
    if i < len(X) { //All remaining in X are greater than Y, just copy over
        finalLength := len(X) - i + len(difference)
        if finalLength > cap(difference) {
            newDifference := make([]int, finalLength)
            copy(newDifference, difference)
            copy(newDifference[len(difference):], X[i:])
            difference = newDifference
        } else {
            differenceLen := len(difference)
            difference = difference[:finalLength]
            copy(difference[differenceLen:], X[i:])
        }
    }
    return difference
}

Go Playground-Version

Unsortierte Version mit Karten

func compareMapAlternate(X, Y []int) []int {
    counts := make(map[int]int)
    var total int
    for _, val := range X {
        counts[val] += 1
        total += 1
    }
    for _, val := range Y {
        if count := counts[val]; count > 0 {
            counts[val] -= 1
            total -= 1
        }
    }
    difference := make([]int, total)
    i := 0
    for val, count := range counts {
        for j := 0; j < count; j++ {
            difference[i] = val
            i++
        }
    }
    return difference
}

Go Playground-Version

Edit: Ich habe einen Benchmark zum Testen meiner beiden Versionen erstellt (wobei die Karte geringfügig geändert wurde und dabei Nullwerte aus der Karte löscht). Es läuft nicht auf Go Playground, weil Time nicht richtig funktioniert, also habe ich es auf meinem eigenen Computer ausgeführt.

compareSort sortiert das Slice und ruft die iterierte Version von compare auf, und compareSorted führt nach dem CompareSort aus, setzt aber voraus, dass das Slice bereits sortiert ist.

Case: len(X)== 10000 && len(Y)== 10000
--compareMap time: 4.0024ms
--compareMapAlternate time: 3.0225ms
--compareSort time: 4.9846ms
--compareSorted time: 1ms
--Result length == 6754 6754 6754 6754
Case: len(X)== 1000000 && len(Y)== 1000000
--compareMap time: 378.2492ms
--compareMapAlternate time: 387.2955ms
--compareSort time: 816.5619ms
--compareSorted time: 28.0432ms
--Result length == 673505 673505 673505 673505
Case: len(X)== 10000 && len(Y)== 1000000
--compareMap time: 35.0269ms
--compareMapAlternate time: 43.0492ms
--compareSort time: 385.2629ms
--compareSorted time: 3.0242ms
--Result length == 3747 3747 3747 3747
Case: len(X)== 1000000 && len(Y)== 10000
--compareMap time: 247.1561ms
--compareMapAlternate time: 240.1727ms
--compareSort time: 400.2875ms
--compareSorted time: 17.0311ms
--Result length == 993778 993778 993778 993778

Wie Sie sehen, ist die Sortierung des Arrays nicht mit Karten viel schneller, aber die Verwendung von Karten ist schneller als das Sortieren und anschließend die iterierte Vorgehensweise. Für kleine Fälle kann die Sortierung schnell genug sein, um verwendet zu werden, aber der Benchmark würde zu schnell beendet sein, um zeitlich festgelegt zu werden.

Das Ziehen in einer Set-Implementierung kann übertrieben sein. Das sollte reichen :

func diff(X, Y []int) []int {

  diff := []int{}
  vals := map[int]struct{}{}

  for _, x := range X {
    vals[x] = struct{}{}
  }

  for _, x := range Y {
    if _, ok := vals[x]; !ok {
      diff = append(diff, x)
    }
  }

  return diff
}

Wenn die Scheiben wirklich groß werden, kann ein Bloom-Filter hinzugefügt werden.

Es gibt auch das github.com/mb0/diff package ( docs bei godoc.org ):

Package Diff implementiert einen Differenzalgorithmus. Der Algorithmus ist beschrieben in "Ein O(ND) Difference Algorithm und seine Variationen" , Eugene Myers, Algorithmica Vol. 1 Nr. 2, 1986, S. 251-266.