我有一個字符串數組，我需要將它與另一個字符串數組進行比較，但它們的順序可能不同。比較這兩個數組的最佳方法是什么？這是我到目前為止所擁有的，只是想知道我是否缺少一種更簡單/更有效的方法。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}
5 回答
幕布斯6054654
TA貢獻1876條經驗 獲得超7個贊
鑒于您正在進行長度檢查，我將假設它們是 1:1，只是順序不同。
您可以在一次通過（每次）中執行此操作，使用 amap[string]bool檢查兩者是否存在。這利用了這樣一個事實，即當鍵不存在時，map返回 a 的零值bool，即。false
免責聲明：從技術上講，這是 O(n)*O(map) 的順序。Go?Programming Language Specification不對地圖類型做任何性能保證。
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通過使用 a?map[string]struct{}（空結構）來保存一堆 s （通?？梢院雎圆挥?，但對每個 s 來說都是），你只需稍微不同地檢查存在，如本例所示。
放
exists[value]?=?struct{}{}查看
if?_,?ok?:=?exists[value];?!ok?{?
???return?false
???}
POPMUISE
TA貢獻1765條經驗 獲得超5個贊
理想情況下，這將是一個評論，但 TLDR 是使用 Husain 的排序和比較更正確和更快。
細節。對于查看上面 RayfenWindspear 答案（當前排名最高）的任何人，乍一看它看起來是正確的，但請注意它不檢查完全相等性，而只是檢查第二個列表中的每個元素都在第一個列表中. 反之亦然，但不通過此方法檢查。因此它沒有通過這個測試（bb重復）：
assert.False(t, unorderedEqual([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))
當然你可以只運行兩次就得到正確的結果，這只是一個線性因素
func DoubleUnorderedEqual(a, b []string) bool {
return unorderedEqual(a, b) && unorderedEqual(b, a)
}
Husain 提出的先排序后檢查的建議可能排名更高，因為它是正確的，而且對于較大的列表也更快。
這是 Husain 在導出函數中的代碼：
func SortCompare(a, b []string) bool {
if len(a) != len(b) {
return false
}
sort.Strings(a)
sort.Strings(b)
for i, v := range a {
if v != b[i] {
return false
}
}
return true
}
還有一些你可以在上面運行的測試（它通過了）
func TestSortCompare(t *testing.T) {
assert.True(t, SortCompare([]string{"aa"}, []string{"aa"}))
assert.False(t, SortCompare([]string{"aa"}, []string{"bb"}))
assert.False(t, SortCompare([]string{"aa"}, []string{"bb", "cc"}))
assert.True(t, SortCompare([]string{"cc", "bb"}, []string{"bb", "cc"}))
assert.True(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "cc"}))
assert.False(t, SortCompare([]string{"aa", "cc", "bb"}, []string{"aa", "bb", "bb"}))
}
這是一些示例基準測試....
func getStrings() ([]string, []string) {
a := []string{"a", "foo", "bar", "ping", "pong"}
b := []string{"pong", "foo", "a", "bar", "ping"}
return a, b
}
func BenchmarkSortCompare(b *testing.B) {
s0, s1 := getStrings()
var outcome bool
for n := 0; n < b.N; n++ {
outcome = SortCompare(s0, s1)
}
fmt.Println(outcome)
}
func BenchmarkDoubleUnorderedEqual(b *testing.B) {
s0, s1 := getStrings()
var outcome bool
for n := 0; n < b.N; n++ {
outcome = DoubleUnorderedEqual(s0, s1)
}
fmt.Println(outcome)
}
結果...
BenchmarkSortCompare-32 2637952 498 ns/op
BenchmarkDoubleUnorderedEqual-32 3060261 381 ns/op
所以在這個小尺寸下運行兩次 map 方法稍微快一些......但是添加更多的字符串并且 sort 方法勝出 10 倍。我沒有考慮字符串中混亂程度的影響但是它們足夠混亂，乍一看這并不是一個明顯不公平的測試。
func getStrings2() ([]string, []string) {
a := []string{"a", "foo", "bar", "ping", "pong", "b", "c", "g", "e", "f", "d", "h", "i", "j", "q", "l", "n", "o", "p", "k", "r", "s", "t", "u", "v", "w", "x", "y", "z"}
b := []string{"pong", "foo", "a", "bar", "ping", "p", "r", "q", "s", "u", "t", "v", "j", "x", "y", "z", "b", "e", "d", "c", "h", "g", "f", "i", "w", "k", "l", "n", "o"}
return a, b
}
func BenchmarkSortCompare2(b *testing.B) {
s0, s1 := getStrings2()
var outcome bool
for n := 0; n < b.N; n++ {
outcome = SortCompare(s0, s1)
}
fmt.Println(outcome)
}
func BenchmarkDoubleUnorderedEqual2(b *testing.B) {
s0, s1 := getStrings2()
var outcome bool
for n := 0; n < b.N; n++ {
outcome = DoubleUnorderedEqual(s0, s1)
}
fmt.Println(outcome)
}
結果：
BenchmarkSortCompare2-32 454641 2797 ns/op
BenchmarkDoubleUnorderedEqual2-32 44420 26714 ns/op
結論 - 我將使用 Husain 的排序和比較......
慕桂英546537
TA貢獻1848條經驗 獲得超10個贊
通用的，與語言無關的：
用最快的可用算法對兩者進行排序
遍歷表 A 并與 B[currentIndexFromA] 進行比較
第一次發現差異時，您知道它們持有不同的數據 - 拋出！
你遍歷了整個A？- 他們是一樣的
我不知道 GO，但您似乎天真地在 B 中搜索 A 中的每個元素。在最壞的情況下，您會在 B 上進行多次迭代。使用高性能算法進行排序似乎更有效，即使它是額外的操作。
不幸的是，我不會提供代碼示例，因為我不知道 GO。
婷婷同學_
TA貢獻1844條經驗 獲得超8個贊
您將不得不使用[]interface{}而不是[]stringthen proceed as such
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
}
慕姐4208626
TA貢獻1852條經驗 獲得超7個贊
您可以先對數組進行排序，然后按索引檢查：
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)，而 2 循環檢查需要 O(n^2)。
- 5 回答
- 0 關注
- 205 瀏覽
添加回答
舉報
0/150
提交
取消