Какой самый быстрый способ сравнить два массива на равенство? - PullRequest
12 голосов
/ 11 ноября 2010

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

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

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

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

Ответы [ 6 ]

18 голосов
/ 11 ноября 2010

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

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

РЕДАКТИРОВАТЬ: SaeedAlg и Сандрис поднимают действительные точки о различных частотах дубликатов, вызывая проблемыс таким подходом.Я вижу два обходных пути, если это важно (они не особо задумывались об их эффективности):

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();
4 голосов
/ 11 ноября 2010

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

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

2 голосов
/ 11 ноября 2010

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

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

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

bool equal = arr1.Except(arr2).Count() == 0 && arr2.Except(arr1).Count() == 0;
1 голос
/ 11 ноября 2010

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

0 голосов
/ 11 ноября 2010

Псевдокод:

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;
0 голосов
/ 11 ноября 2010

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

...