Сравнение двух наборов для равенства независимо от порядка пунктов в них

Существует много решений этой проблемы. Если Вы не заботитесь о дубликатах, Вы не должны сортировать обоих. Сначала удостоверьтесь, что у них есть то же количество объектов. После того вида один из наборов. Тогда binsearch каждый объект от второго набора в отсортированном наборе. Если Вы не находите, что данный объект останавливает и возвращает false. Сложность этого: - сортировка первого набора: Журнал N (N) - ищущий каждый объект от второго в первое: ЖУРНАЛ N (N), таким образом, Вы заканчиваете с 2*N*LOG (Н), предполагающий, что они соответствуют и Вы ищете все. Это подобно сложности сортировки обоих. Также это приносит Вам пользу для остановки ранее, если существует различие. Однако имейте в виду, что, если и отсортированы перед продвижением в это сравнение и Вы пытаетесь сортировать по использованию что-то как qsort, сортировка будет более дорогой. Существует оптимизация для этого. Другая альтернатива, которая является большой для небольших коллекций, где Вы знаете диапазон элементов, должна использовать индекс битовой маски. Это даст Вам O (n) производительность. Другая альтернатива должна использовать хеш и искать его. Для небольших коллекций обычно намного лучше сделать сортировку или индекс битовой маски. Хеш-таблица имеет недостаток худшей местности, так имейте это в виду. Снова, это - то, только если Вы не заботитесь о дубликатах. Если Вы хотите объяснить дубликаты, идут с сортировкой обоих.

erickson является почти правильным: так как Вы хотите соответствовать на количествах дубликатов, Вы хотите Сумка . В Java это смотрит что-то как:

(new HashBag(collection1)).equals(new HashBag(collection2))

я уверен, что C# имеет встроенную реализацию Набора. Я использовал бы это сначала; если производительность является проблемой, Вы могли бы всегда использовать различную реализацию Набора, но использовать тот же интерфейс Set.

Вы могли использовать Hashset. Посмотрите метод SetEquals .

Это - мой (в большой степени под влиянием D.Jennings) универсальная реализация метода сравнения (в C#):

/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
    /// <summary>
    /// Compares the content of two collections for equality.
    /// </summary>
    /// <param name="foo">The first collection.</param>
    /// <param name="bar">The second collection.</param>
    /// <returns>True if both collections have the same content, false otherwise.</returns>
    public bool Execute(ICollection<T> foo, ICollection<T> bar)
    {
        // Declare a dictionary to count the occurence of the items in the collection
        Dictionary<T, int> itemCounts = new Dictionary<T,int>();

        // Increase the count for each occurence of the item in the first collection
        foreach (T item in foo)
        {
            if (itemCounts.ContainsKey(item))
            {
                itemCounts[item]++;
            }
            else
            {
                itemCounts[item] = 1;
            }
        }

        // Wrap the keys in a searchable list
        List<T> keys = new List<T>(itemCounts.Keys);

        // Decrease the count for each occurence of the item in the second collection
        foreach (T item in bar)
        {
            // Try to find a key for the item
            // The keys of a dictionary are compared by reference, so we have to
            // find the original key that is equivalent to the "item"
            // You may want to override ".Equals" to define what it means for
            // two "T" objects to be equal
            T key = keys.Find(
                delegate(T listKey)
                {
                    return listKey.Equals(item);
                });

            // Check if a key was found
            if(key != null)
            {
                itemCounts[key]--;
            }
            else
            {
                // There was no occurence of this item in the first collection, thus the collections are not equal
                return false;
            }
        }

        // The count of each item should be 0 if the contents of the collections are equal
        foreach (int value in itemCounts.Values)
        {
            if (value != 0)
            {
                return false;
            }
        }

        // The collections are equal
        return true;
    }
}

Создайте Словарь "dict" и затем для каждого участника в первом наборе, сделайте dict [участник] ++;

Затем цикл по второму набору таким же образом, но для каждого участника делает dict [участник]-.

В конце, цикле по всем участникам в словаре:

    private bool SetEqual (List<int> left, List<int> right) {

        if (left.Count != right.Count)
            return false;

        Dictionary<int, int> dict = new Dictionary<int, int>();

        foreach (int member in left) {
            if (dict.ContainsKey(member) == false)
                dict[member] = 1;
            else
                dict[member]++;
        }

        foreach (int member in right) {
            if (dict.ContainsKey(member) == false)
                return false;
            else
                dict[member]--;
        }

        foreach (KeyValuePair<int, int> kvp in dict) {
            if (kvp.Value != 0)
                return false;
        }

        return true;

    }

Редактирование: Насколько я могу сказать, что это находится на том же порядке как самый эффективный алгоритм. Этот алгоритм является O (N), предполагая, что Словарь использует O (1) поиски.

Простое и довольно эффективное решение должно отсортировать оба набора и затем сравнить их для равенства:

bool equal = collection1.OrderBy(i => i).SequenceEqual(
                 collection2.OrderBy(i => i));

Этот алгоритм является O (N*logN), в то время как Вашим решением выше является O (N^2).

, Если наборы имеют определенные свойства, можно быть в состоянии реализовать более быстрое решение. Например, если оба из Ваших наборов являются наборами хеша, они не могут содержать дубликаты. Кроме того, проверка, содержит ли набор хеша некоторый элемент, очень быстра. В этом случае алгоритм, подобный Вашему, вероятно, был бы самым быстрым.

РЕДАКТИРОВАТЬ: Я понял, как только я сформулировал, что это действительно работает только для наборов - это не будет правильно работать с коллекциями, в которых есть повторяющиеся элементы. Например, {1, 1, 2} и {2, 2, 1} будут считаться равными с точки зрения этого алгоритма. Однако, если ваши коллекции являются наборами (или их равенство может быть измерено таким образом), я надеюсь, что приведенное ниже будет вам полезно.

Я использую следующее решение:

return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;

Linq выполняет скрытую работу со словарем, так что это также O (N). (Обратите внимание, это O (1), если коллекции не одинакового размера.)

Я проверил работоспособность, используя метод «SetEqual», предложенный Дэниелом, метод OrderBy / SequenceEquals, предложенный Игорем, и мое предложение. Ниже приведены результаты, показывающие O (N * LogN) для Игоря и O (N) для меня и Дэниела.

Я думаю, что простота кода пересечения Linq делает его предпочтительным решением.

__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect    
1024, 0, 0, 0    
2048, 0, 0, 0    
4096, 31.2468, 0, 0    
8192, 62.4936, 0, 0    
16384, 156.234, 15.6234, 0    
32768, 312.468, 15.6234, 46.8702    
65536, 640.5594, 46.8702, 31.2468    
131072, 1312.3656, 93.7404, 203.1042    
262144, 3765.2394, 187.4808, 187.4808    
524288, 5718.1644, 374.9616, 406.2084    
1048576, 11420.7054, 734.2998, 718.6764    
2097152, 35090.1564, 1515.4698, 1484.223

В случае отсутствия повторов и порядка можно использовать следующий EqualityComparer, чтобы разрешить коллекции в качестве ключей словаря:

public class SetComparer<T> : IEqualityComparer<IEnumerable<T>> 
where T:IComparable<T>
{
    public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
    {
        if (first == second)
            return true;
        if ((first == null) || (second == null))
            return false;
        return first.ToHashSet().SetEquals(second);
    }

    public int GetHashCode(IEnumerable<T> enumerable)
    {
        int hash = 17;

        foreach (T val in enumerable.OrderBy(x => x))
            hash = hash * 23 + val.GetHashCode();

        return hash;
    }
}

Здесь - реализация ToHashSet (), которую я использовал. Алгоритм хэш-кода заимствован из Effective Java (через Джона Скита).

Повторяющееся сообщение, но ознакомьтесь с моим решением для сравнения коллекций . Это довольно просто:

Это выполнит сравнение на равенство независимо от порядка:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

Это проверит, были ли элементы добавлены / удалены:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

Это увидит, какие элементы в словаре были изменены:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
  Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Исходное сообщение здесь .