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

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

4 голосов
/ 21 ноября 2008

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

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

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

Ответы [ 7 ]

4 голосов
/ 21 ноября 2008

используйте C5

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;
}
3 голосов
/ 21 ноября 2008

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

if (firstCollection.SequenceEqual(secondCollection))
3 голосов
/ 21 ноября 2008

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

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

  • Сравнить коллекцию Count: вернуть false, если они отличаются
  • Итерация первой коллекции
    • Если элемент не существует в словаре, добавьте и введите ключ = Элемент, Значение = 1 (количество)
    • Если элемент существует, увеличить счетчик для элемента в словаре;
  • Повтор второй коллекции
    • Если элемент отсутствует в словаре, тогда возвращается false
    • Если элемент находится в словаре, то счетчик декрементов для элемента
      • Если считать == 0 удалить элемент;
  • return Dictionary.Count == 0;
2 голосов
/ 21 ноября 2008

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

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

1 голос
/ 10 июля 2009

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

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

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

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

1 голос
/ 21 ноября 2008

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

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

0 голосов
/ 21 ноября 2008

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

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

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

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

...