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

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

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

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

Je souhaite traiter ces deux tableaux que l'égalité. Quel est le moyen le plus rapide pour tester cela?

source d'informationauteur izb

  1. 18

    Je ne peux pas garantir que c'est la plus rapidemais c'est certainement très efficace:

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

    EDIT:
    SaeedAlg et Sandris soulever des points valables sur les différentes fréquences de doublons, provoquant des problèmes avec cette approche. Je vois deux solutions de contournement si c'est important (n'ont pas donné beaucoup de pensée à leur efficacité):

    1.Trier les tableaux et les comparer de manière séquentielle. Cette approche, en théorie, devrait avoir quadratique de la complexité dans le pire des cas.
    E. g.:

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

    2.Construire une fréquence de tableau de chaînes de caractères dans chaque tableau et de les comparer. E. g.:

    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();
  2. 4

    Je pense que la seule façon raisonnable est de les trier puis de les comparer.

    De tri nécessite O(n logn) et en comparant O(n)donc c'est toujours un total de O(n logn)

  3. 2

    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;
  4. 1

    Convertir les deux tableaux à HashSets et l'utilisation setequals

  5. 0

    Je voudrais utiliser un HashSet, s'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 des quatre éléments, il pourrait être plus rapide pour sauter le HashSet et l'utilisation arr1.Contient dans la comparaison. Mesure et de choisir la manière la plus rapide pour votre taille de la matrice.

  6. 0

    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;