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

StackOverflow https://stackoverflow.com/questions/308476

Вопрос

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

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

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

Это было полезно?

Решение

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

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

Содержит все

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

Значение true, если все элементы найдены. "

[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;
}

Другие советы

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

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

  • Сравните количество коллекций :верните false, если они разные
  • Повторите первую коллекцию
    • Если элемент не существует в словаре, то добавьте запись с ключом = Item, значением = 1 (количество)
    • Если элемент существует, увеличьте количество элементов в словаре;
  • Повторите вторую коллекцию
    • Если элемента нет в словаре, то then возвращает false
    • Если элемент находится в словаре, уменьшите количество для элемента
      • Если count == 0, то элемент удаления;
  • возвращает словарь.Количество == 0;

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

if (firstCollection.SequenceEqual(secondCollection))

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

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

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

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

Опять же, используя библиотеку 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).

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top