Vergleichen Sie zwei Scheiben

Etwas wie dies funktionieren sollte:

package main

import "fmt"

func main() {
    X := []int{10, 12, 12, 12, 13}
    Y := []int{12, 14, 15}

    fmt.Println(compare(X, Y))
    fmt.Println(compare(Y, X))
}

func compare(X, Y []int) []int {
    m := make(map[int]int)

    for _, y := range Y {
        m[y]++
    }

    var ret []int
    for _, x := range X {
        if m[x] > 0 {
            m[x]--
            continue
        }
        ret = append(ret, x)
    }

    return ret
}

http://play.golang.org/p/4DujR2staI

InformationsquelleAutor ctn

Alle Lösungen scheitern präzise Antwort auf die gestellte Frage. Statt die Unterschiede in den Scheiben, die Lösungen bieten, die Unterschiede der Sätze der Elemente in den Scheiben.

Speziell, anstelle der vorgesehenen Beispiel:

    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}

Den Lösungen führt:

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

Ausbeute streng der Beispiel-Ergebnis, eine andere Methode erforderlich ist. Hier sind zwei Lösungen:

Wenn die Scheiben bereits sortiert:

Kann diese Lösung schneller, wenn Sie die Art Ihre Scheiben, und rufen Sie dann vergleichen. Es wird definitiv schneller sein, wenn Sie Ihre Scheiben sind bereits sortiert.

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
}

Gehen Spielplatz 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
}

Gehen Spielplatz version

Edit: habe ich einen benchmark für meine Prüfung in zwei Versionen (mit der Karte habe eine leichte Modifikation, wo es löscht die null-Werte aus der Karte). Es wird nicht ausgeführt, auf den Spielplatz Gehen, weil die Zeit nicht richtig funktioniert, so dass ich lief es auf meinem eigenen computer.

compareSort sortiert die Scheibe und ruft die iterierten version vergleichen, und compareSorted läuft afters compareSort, sondern verlässt sich auf die Scheibe bereits sortiert.

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 können, wenn das array sortiert ist, nicht mit Karten ist viel schneller, aber mit Karten ist schneller als das Sortieren, und dann mit Hilfe der iterierten Ansatz. Für kleine Fälle, die Sortierung kann schnell genug, dass es verwendet werden soll, aber der benchmark fertig würde, schnell zu terminieren.

InformationsquelleAutor Laremere

Gibt es auch die github.com/mb0/diff - Paket (docs an godoc.org):

Diff-Paket implementiert einen Unterschied-Algorithmus. Der Algorithmus ist beschrieben in "Ein O(ND) - Differenz-Algorithmus und seine Varianten", Eugene Myers, Algorithmica, Vol. 1 No. 2, 1986, pp. 251-266.

InformationsquelleAutor akavel