Quel est le moyen le plus rapide de comparer deux tableaux pour l'égalité?

Question

J'ai deux tableaux d'objets qui sont susceptibles d'avoir les mêmes valeurs, mais dans un ordre différent, par ex.

{ "cat", "dog", "mouse", "pangolin" } 

{ "dog", "pangolin", "cat", "mouse" } 

Je souhaite traiter ces deux ensembles de façon égale. Quel est le moyen le plus rapide de tester cela?

Answer 1

Je ne peux pas garantir que c'est le le plus rapide, mais il est certainement très efficace:

bool areEquivalent = array1.Length == array2.Length 
        && new HashSet<string>(array1).SetEquals(array2); 

EDIT: SaeedAlg et Sandris soulèvent des points valides sur les différentes fréquences de doublons causant des problèmes avec cette approche. Je peux voir deux solutions de contournement si cela est important (ne pas avoir pensé beaucoup à leurs efficacités respectives):

1.Sort les tableaux, puis les comparer séquentiellement. Cette approche, en théorie, devrait avoir une complexité quadratique dans le pire des cas. .: par exemple

return array1.Length == array2.Length 
     && array1.OrderBy(s => s).SequenceEqual(array2.OrderBy(s => s)); 

2.Build une fréquence table de chaînes dans chaque tableau, puis de les comparer. Par exemple:

if(array1.Length != array2.Length) 
    return false; 

var f1 = array1.GroupBy(s => s) 
       .Select(group => new {group.Key, Count = group.Count() }); 

var f2 = array2.GroupBy(s => s) 
       .Select(group => new {group.Key, Count = group.Count() }); 

return !f1.Except(f2).Any(); 

Answer 2

J'utiliser un HashSet, en supposant qu'il n'y a pas de doublons

string[] arr1 = new string[] { "cat", "dog", "mouse", "pangolin" }; 
string[] arr2 = new string[] { "dog", "pangolin", "cat", "mouse" }; 

bool result = true; 
if (arr1.Length != arr2.Length) 
{ 
    result = false; 
} 
else 
{ 
    HashSet<string> hash1 = new HashSet<string>(arr1); 
    foreach (var s in arr2) 
    { 
     if (!hash1.Contains(s)) 
      result = false; 
    } 
} 

Edit:
Si vous avez juste quatre éléments, il pourrait être plus rapide de sauter le HashSet et utiliser arr1 .Contient dans la comparaison. Mesurez et choisissez le plus rapide pour votre taille de tableau.

Answer 3

Je pense que le seul moyen raisonnable est de les trier puis de les comparer.

tri nécessite O(n logn) et en comparant O(n), de sorte que est encore un total de O(n logn)

Answer 4

Convertir les deux tableaux à HashSet et utiliser setequals

Answer 5

Avez-vous essayé quelque chose comme

string[] arr1 = {"cat", "dog", "mouse", "pangolin"}; 

string[] arr2 = {"dog", "pangolin", "cat", "mouse"}; 

bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0; 

Answer 6

pseudocode:

A:array 
B:array 
C:hashtable 

if A.length != B.length then return false; 

foreach objA in A 
{ 
H = objA; 
if H is not found in C.Keys then 
C.add(H as key,1 as initial value); 
else 
C.Val[H as key]++; 
} 

foreach objB in B 
{ 
H = objB; 
if H is not found in C.Keys then 
return false; 
else 
C.Val[H as key]--; 
} 

if(C contains non-zero value) 
return false; 
else 
return true;