Какой самый быстрый способ сравнить два массива для равенства?

Question

У меня есть два массива объектов, которые, вероятно, имеют одинаковые значения, но в другом порядке, например.

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

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

Я хочу рассматривать эти два массива как равные. Какой самый быстрый способ проверить это?

Answer 1

Я не могу гарантировать, что это быстрый, но это, конечно, весьма эффективно:

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

EDIT: SaeedAlg и Sandris поднять действительные пункты о различных частотах дублей, вызывающих проблемы с этим подходом. Я вижу два обходных решения, если это важно (не придали большого значения их соответствующей эффективности):

1. Содержите массивы, а затем последовательно сравните их. Такой подход теоретически должен иметь квадратичную сложность в худшем случае. т.д .:

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

2.Build вверх частотную таблицу строк в каждом массиве, а затем сравнить их. Например:

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

Я хотел бы использовать HashSet, предполагая, что нет дубликатов

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:
Если вы только четыре элемента может быть быстрее, чтобы пропустить HashSet и использовать arr1 . Сопоставляет в сравнении. Измерьте и выберите самый быстрый размер вашего массива.

Answer 3

Я думаю, что единственный разумный способ - сортировать их, а затем сравнивать.

Сортировка требует O(n logn) и сравнения O(n), так что до сих пор в общей сложности O(n logn)

Answer 4

Преобразование обоих массивов в HashSets и использовать setequals

Answer 5

Вы пробовали что-то вроде

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

псевдокод:

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;