установить равенство в linq - PullRequest
Новая
       38

установить равенство в linq

8 голосов
/ 03 июня 2009

У меня есть два списка A и B (Список). Как определить, равны ли они самым дешевым способом? Я могу написать что-то вроде '(A минус B) объединение (B минус A) = пустой набор' или объединить их вместе и посчитать количество элементов, но это довольно дорого. Есть ли обходной путь?

Ответы [ 5 ]

18 голосов
/ 03 июня 2009

Если порядок пунктов списка уместен: 

bool areEqual = a.SequenceEqual(b);

Если списки следует рассматривать как неупорядоченные множества: 

// assumes that the list items are ints
bool areEqual = new HashSet<int>(a).SetEquals(b);

(Метод SequenceEqual и конструктор HashSet<T> оба имеют перегрузки, которые принимают параметр IEqualityComparer<T>, если вам нужны эти функции. )

7 голосов
/ 03 июня 2009

Ну, это зависит от того, как вы интерпретируете свои списки.

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

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        if (A.Count != B.Count)
            return false;
        for (int i = 0; i < A.Count; i++)
            if (!A[i].Equals(B[i])) 
                return false;
    }

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

    public bool AreEqual<T>(IList<T> A, IList<T> B)
    {
        HashSet<T> setA = new HashSet<T>(A);
        return setA.SetEquals(B);
    }
1 голос
/ 03 июня 2009

Это зависит от того, что вы подразумеваете под «список равен». Если вы имеете в виду, что они содержат одни и те же объекты, то решение, предложенное Дэниелом, подойдет, просто объедините два списка и подсчитайте количество элементов.

Если под "равным" вы подразумеваете, что они имеют одинаковые элементы в одном и том же порядке , вам лучше сравнить счетчик обоих списков, тогда, если они имеют одинаковое количество, просто повторите с простым for loop для сравнения каждого элемента из обоих списков по одному и тому же индексу. Менее красиво, но вы вряд ли сможете быть быстрее.

1 голос
/ 03 июня 2009

Здесь нет ярлыка, если только списки не отсортированы, и в этом случае вы можете сравнить элементы один за другим. И, очевидно, я предполагаю, что порядок не имеет значения, иначе очевидно, что вы можете сравнивать их по очереди и тогда.

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

public static bool IsEqual<T>(this List<T> x1, List<T> x2)
{
    if(x1.Count != x2.Count) return false;

    var x1Elements = new Dictionary<T, int>();

    foreach(var item in x1)
    {
        int n; x1Elements.TryGetValue(item, out n);
        x1Elements[item] = n+1;
    }

    foreach(var item in x2)
    {
        int n; x1Elements.TryGetValue(item, out n);
        if(n <= 0) return false; // this element was in x2 but not x1
        else x1Elements[item] = n-1;
    }

    // make sure x1 didn't have any elements
    // that weren't in x2

    return x1Elements.Values.All(x => x == 0);
}
0 голосов
/ 03 июня 2009

Первый выстрел - если они содержат одинаковые элементы, объединение обоих списков должно иметь то же количество элементов, что и любой из обоих списков. 

listA.Union(listB).Count() == listA.Count()

Примечание. Сбой, если один список пуст.

Но это, вероятно, все еще операция O(n²).

Другое решение - списки должны иметь одинаковую длину, а список A без списка B не должен содержать никаких элементов. 

(listA.Count() == listB.Count()) && !listA.Except(listB).Any()
...