¿Cuál es la forma más rápida de comparar dos matrices para la igualdad?

Question

Tengo dos matrices de objetos que probablemente tengan los mismos valores, pero en un orden diferente, p.

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

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

Deseo tratar estas dos matrices como iguales. ¿Cuál es la forma más rápida de probar esto?

Answer 1

No puedo garantizar que esta es la más rápido, pero es sin duda bastante eficiente:

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

EDIT: SaeedAlg y Sandris plantean puntos válidos sobre diferentes frecuencias de duplicados causando problemas con este enfoque. Puedo ver dos soluciones si esto es importante (no he pensado mucho en sus respectivas eficiencias):

1. Clasifique las matrices y luego las compare secuencialmente. Este enfoque, en teoría, debería tener una complejidad cuadrática en el peor de los casos. ej .:

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

2.Build hasta una frecuencia de la tabla de cadenas en cada matriz y luego compararlos. Por ejemplo:

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

me gustaría utilizar un HashSet, asumiendo que no hay duplicados

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; 
    } 
} 

Editar:
Si sólo hay cuatro elementos que podría ser más rápido para saltar el HashSet y utilizar arr1 .Contiene en la comparación. Mida y elija el más rápido para su tamaño de matriz.

Answer 3

Creo que la única manera razonable es ordenarlos y luego compararlos.

Clasificación requiere O(n logn) y comparando O(n), por lo que sigue siendo un total de O(n logn)

Answer 4

Convertir ambas matrices a HashSets y utilizar setequals

Answer 5

Ha intentado algo así como

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

Pseudocódigo:

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;