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

Ответ 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. Создайте таблицу частот строк в каждом массиве, а затем сравните их. Например:.

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

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

Для сортировки требуется O(n logn) и сравнения O(n), так что все еще O(n logn)

Ответ 3

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

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

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

Ответ 5

Я бы использовал 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.Contains. Измерьте и выберите самый быстрый размер вашего массива.

Ответ 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;