Самый быстрый способ узнать, содержат ли две коллекции ICollection <T>

Question

Что такое самый быстрый способ узнать, содержат ли две коллекции ICollection<T> те же записи? Грубая сила ясна, мне было интересно, есть ли более элегантный метод.

Мы используем C# 2.0, поэтому никаких методов расширения, если возможно, пожалуйста!

Редактировать: ответ будет интересен как для упорядоченных, так и неупорядоченных коллекций, и, мы надеемся, будет отличаться для каждого.

Answer 1

использование С5

http://www.itu.dk/research/c5/

ContainsAll

"Проверьте, если все элементы в поставляемой коллекции А находится в этом пакете
(с учетом кратностей).
В пунктов для поиска.

Истинно, если все предметы найдено. "

[Tested] 

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T 
{ 
    HashBag<T> res = new HashBag<T>(itemequalityComparer); 

    foreach (T item in items) 
    if (res.ContainsCount(item) < ContainsCount(item)) 
     res.Add(item); 
    else 
     return false; 

    return true; 
} 

Answer 2

Грубая сила принимает O (n) - сравнивает все элементы (при условии, что они отсортированы), что, по моему мнению, является лучшим, что вы могли бы сделать - если только не существует некоторого свойства данных, которое облегчает его.

Я предполагаю, что для случая не отсортированного, его O (n * n).

В этом случае, я думаю, решение, основанное на merge sort, вероятно, поможет.

Например, вы можете переделать его так, чтобы была только одна коллекция? Или 3 коллекции, одна для тех, кто только в коллекции A, только для B и для обоих - так что, если только A и B только пустые, - тогда они одинаковы ... Я, вероятно, полностью отключился от неправильной касательной here ...

Answer 3

Вы имеете в виду те же записи или те же записи в одном порядке?

В любом случае, если вы хотите сравнить, содержат ли они одни и те же записи в том же порядке, «грубая сила» на самом деле является вашим единственным вариантом в C# 2.0. Я знаю, что вы подразумеваете под неэфирностью, но если сама атомная сопоставления равна O (1), весь процесс должен быть в O (N), который не является , что плохой.

Answer 4

Если записи должны быть в том же порядке (помимо того же самого), то я предлагаю - как оптимизацию - одновременно выполнять итерацию обеих коллекций и сравнивать текущую запись в каждой коллекции. В противном случае грубая сила - это путь.

О, и еще одно предложение - вы можете переопределить Equals для класса коллекции и реализовать там вещи равенства (в зависимости от вашего проекта).

Answer 5

Первое сравнение. Подсчет коллекций, если они имеют одинаковый счет, сравнивают поровну все элементы. Наихудшими сценариями являются O (n). Это в том случае, когда порядок элементов должен быть одинаковым.

Второй случай, когда порядок не то же самое, что вам нужно использовать словарь для хранения количества найденных элементов в коллекциях: Вот возможный алгоритм

• Сравнить коллекции Count: возвращает ложь, если они разные
• Iterate первая коллекция
  • Если элемент не существует в словаре, то добавить и запись с ключом = пункт, Value = 1 (счет)
  • Если элемент существует растет в цене подсчет количества слов в словаре;
• Iterate вторая коллекция
  • Если деталь отсутствует в словаре тогда вернуть ложную
  • Если предмет находится в словаре подсчета декремента для элемента
    • Если счетчик == 0 удалить элемент;
• возвращение Dictionary.Count == 0;

Answer 6

Для упорядоченных коллекций, вы можете использовать метод SequenceEqual() расширения, определяемый System.Linq.Enumerable:

if (firstCollection.SequenceEqual(secondCollection)) 

Answer 7

Опять же, используя библиотеку C5, имея два набора, вы можете использовать:

 
C5.ICollection<T> set1 = C5.ICollection<T>(); 
C5.ICollection<T> set2 = C5.ICollecton<T>(); 
if (set1.UnsequencedEquals (set2)) { 
    // Do something 
} 

Библиотека C5 включает в себя эвристику, которая на самом деле проверяет непересекающиеся хэш-коды двух наборов (s ee C5.ICollection<T>.GetUnsequencedHashCode()), так что если хэш-коды двух наборов не равны, для проверки равенства не нужно перебирать все элементы для каждого элемента.

Также вам следует обратить внимание на то, что C5.ICollection<T> наследует от System.Collections.Generic.ICollection<T>, поэтому вы можете использовать реализации C5, все еще используя интерфейсы .NET (хотя у вас есть доступ к меньшим функциям через скупые интерфейсы .NET).