Лучший способ проверить, имеют ли два массива одинаковые члены

Question

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

Это то, что я имею до сих пор, просто интересно, есть ли более простой / более эффективный способ, который я пропускаю.

func unorderedEqual(first, second []string) bool {
    if len(first) != len(second) {
        return false
    }
    for _, value := range first {
        if !contains(value, second) {
            return false
        }
    }
    return true
}

func contains(needle string, haystack []string) bool {
    for _, matchValue := range haystack {
        if matchValue == needle {
            return true
        }
    }
    return false
}

Answer 1

Вы можете сначала отсортировать массивы, а затем проверить по индексу:

package main

import (
    "fmt"
    "sort"
)

func main() {
    s1 := []string{"first", "second", "third"}
    s2 := []string{"third", "first", "second"}

    if len(s1) != len(s2) {
        fmt.Println("not equal")
    }
    sort.Strings(s1)
    sort.Strings(s2)
    for i := 0; i < len(s1); i++ {
        if s1[i] != s2[i] {
            fmt.Println("not equal")
            return
        }
    }
    fmt.Println("equal")
}

Или на детской площадке .

Идея сортировки состоит в том, что она делает сравнениепроще и быстрее.Сортировка и последующее сравнение по индексу происходит за O (n log n), тогда как двухконтурная проверка занимает O (n ^ 2).

Answer 2

Используя этот выделенный пакет, вы должны будете использовать []interface{} вместо []string, а затем действовать так:

package main

import (
    "fmt"

    "github.com/deckarep/golang-set"
)

func main() {
    some := []interface{}{"a", "b", "c"}
    other := []interface{}{"a", "b", "d"}
    fmt.Println(
        mapset.NewThreadUnsafeSetFromSlice(some).
            Difference(mapset.NewThreadUnsafeSetFromSlice(other)).Cardinality() == 0,
    )
    // Output: false
}

Answer 3

Общий, независимый от языка:

1. сортировка с использованием самого быстрого из доступных алгоритмов
2. перебор таблицы A и сравнение с B [currentIndexFromA]
3. при первом обнаруженииРазница, вы знаете, что они содержат разные данные - бросить!
4. вы повторяли всю A?- они одинаковы

Я не знаю GO, но вы, кажется, наивно ищете каждый элемент из A в B. В худшем случае вы получаете много итераций по B. Сортировка сАлгоритм Performanceman кажется более эффективным, хотя это дополнительная операция.

Я, к сожалению, не предоставлю пример кода, так как не знаю GO.

Answer 4

Учитывая, что вы делаете проверку длины, я собираюсь предположить, что они 1: 1, просто упорядочены по-разному.

Вы можете сделать это за один проход (каждый)используя map[string]bool, чтобы проверить существование в обоих.При этом используется тот факт, что map возвращает нулевое значение bool, то есть false, когда ключ отсутствует.

Отказ от ответственности: Технически это порядокO (N) * O (карта). Спецификация языка программирования Go не дает никаких гарантий производительности для типов карт.

https://play.golang.org/p/2LUjN5LkXLL

func unorderedEqual(first, second []string) bool {
    if len(first) != len(second) {
        return false
    }
    exists := make(map[string]bool)
    for _, value := range first {
        exists[value] = true
    }
    for _, value := range second {
        if !exists[value] {
            return false
        }
    }
    return true
}

Если вы хотите немного разборчивы в использовании памяти, вы можете сэкономить, храня кучу bool с (что обычно незначительно, но каждому свое), используя map[string]struct{} (пустую структуру), и вы просто проверяете существование немного по-другому, как в этом примере

https://play.golang.org/p/MjwP_wCtYZV

Набор

exists[value] = struct{}{}

Чек

if _, ok := exists[value]; !ok {
    return false
}