C # Сходства двух массивов

Question

Там должен быть лучшим способом сделать это, я уверен ...

// Simplified code
var a = new List<int>() { 1, 2, 3, 4, 5, 6 };
var b = new List<int>() { 2, 3, 5, 7, 11 };
var z = new List<int>();
for (int i = 0; i < a.Count; i++)
    if (b.Contains(a[i]))
        z.Add(a[i]);
// (z) contains all of the numbers that are in BOTH (a) and (b), i.e. { 2, 3, 5 }

Я не против использовать вышеописанную технику, но я хочу что-то быстрое и эффективное (мне нужно сравнивать очень большие списки <> несколько раз), и это, похоже, ни то, ни другое! Есть мысли?

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

Answer 1

Вы можете использовать IEnumerable.Intersect.

var z = a.Intersect(b);

что вероятно будет более эффективным, чем ваше текущее решение.

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

Редактировать В ответ на ваш комментарий по поводу заказа:

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

    int j = 0;
    foreach (var i in a)
    {
        int x = b[j];
        while (x < i)
        {
            if (x == i)
            {
                z.Add(b[j]);
            }
            j++;
            x = b[j];
        }
    }

это то место, где вам нужно добавить несколько юнит-тестов;)

Редактировать И последнее замечание - вполне возможно, что Linq может использовать SortedList для очень эффективного выполнения этого пересечения, если производительность является проблемой, стоит протестировать различные решения. Не забудьте учесть сортировку, если вы загружаете данные неупорядоченным образом.

Одно окончательное редактирование , потому что там были кое-что, и люди могут использовать вышеупомянутое без надлежащей отладки. Я выкладываю более позднюю версию здесь:

        int j = 0;
        int b1 = b[j];
        foreach (var a1 in a)
        {
            while (b1 <= a1)
            {
                if (b1 == a1)
                    z1.Add(b[j]);
                j++;
                if (j >= b.Count)
                    break;
                b1 = b[j];
            }
        }

Answer 2

Есть IEnumerable.Intersect, но так как это метод расширения, я сомневаюсь, что он будет очень эффективным.

Если вам нужна эффективность, возьмите один список и превратите его в набор, затем просмотрите второй список и посмотрите, какие элементы находятся в наборе. Обратите внимание, что я предварительно выделил z, просто чтобы убедиться, что вы не страдаете от перераспределения.

var set = new HashSet<int>(a);
var z = new List<int>(Math.Min(set.Count, b.Count));

foreach(int i in b)
{
    if(set.Contains(i))
        a.Add(i);
}

Это гарантированно работает в O (N + M) (N и M - размеры двух списков).

Теперь вы можете использовать set.IntersectWith(b), и я считаю, что это будет столь же эффективно, но я не уверен на 100%.

Answer 3

Использование SortedSet<T> в System.Collections.Generic пространстве имен:

SortedSet<int> a = new SortedSet<int>() { 1, 2, 3, 4, 5, 6 };
SortedSet<int> b = new SortedSet<int>() { 2, 3, 5, 7, 11 };
b.IntersectWith(s2);

Но наверняка у вас нет дубликатов!
Хотя ваш второй список не должен быть SortedSet. Это может быть любая коллекция (IEnumerable<T>), но внутри метод действует так, что если второй список также равен SortedSet<T>, операция является операцией O (n).

Answer 4

Если вы можете использовать LINQ, вы можете использовать метод расширения Enumerable.Intersect().

Answer 5

Метод Intersect() делает именно это.От MSDN :

Создает заданное пересечение двух последовательностей с помощью средства сравнения по умолчанию для сравнения значений.

Так в вашем случае:

var z = a.Intersect(b);