Сравните два среза

Ответ 1

Что-то вроде этого должно работать:

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

Ответ 2

Если порядок не важен, а множества большие, вы должны использовать реализацию набора и использовать его функцию diff для их сравнения.

Наборы не являются частью стандартной библиотеки, но вы можете использовать эту библиотеку, например, вы можете автоматически инициализировать набор из среза с ним. https://github.com/deckarep/golang-set

Что-то вроде этого:

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)
}

Ответ 3

Все предоставленные решения не позволяют точно ответить на заданный вопрос. Вместо различий в срезах решения обеспечивают различия в наборах элементов в срезах.

В частности, вместо предполагаемого примера:

    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}

Приведенные решения приведут к:

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

Чтобы точно привести результат примера, требуется другой метод. Вот два решения:

Если срезы уже отсортированы:

Это решение может быть быстрее, если вы сортируете свои фрагменты, а затем вызываете сравнение. Это определенно будет быстрее, если ваши фрагменты уже отсортированы.

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
}

Перейти к игровой площадке

Несортированная версия с использованием карт

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, потому что Time не работает должным образом, поэтому я запустил его на своем компьютере.

compareSort сортирует срез и вызывает итерационную версию сравнения, а compareSorted запускает afters compareSort, но полагается на уже отсортированный срез.

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

Как вы можете видеть, если массив отсортирован не с использованием карт, он выполняется намного быстрее, но использование карт выполняется быстрее, чем сортировка, а затем с использованием итерационного подхода. Для небольших случаев сортировка может быть достаточно быстрой, чтобы ее можно было использовать, но контрольный показатель завершился быстро, чтобы быть приурочен.

Ответ 4

Перетаскивание в реализацию набора может быть чрезмерным. Этого должно быть достаточно:

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
}

Фильтр цветения может быть добавлен, если срезы становятся действительно большими.

Ответ 5

Там также github.com/mb0/diff пакет (docs на godoc.org):

Пакет diff реализует разностный алгоритм. Алгоритм описан в "Алгоритм разностных алгоритмов O (ND) и его вариациях" , Eugene Myers, Algorithmica Vol. 1 № 2, 1986, стр. 251-266.