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