Подсчитайте элементы, существующие в 2 списках

Ответ 1

B.Intersect(A).Count(); //should do the job

Ответ 2

A.Where(a=>B.Contains(a)).Count ()

Ответ 3

Стандартная реализация B.Intersect(A).Count() имеет большое преимущество быть коротким и читаемым, если у вас нет проблемы с производительностью, с которой вы должны пойти.

Когда производительность является проблемой, вы можете ввести HashSet<int>, это хороший компромисс в использовании ресурсов и времени поиска. Однако, поскольку вы беспокоитесь о производительности, мы должны выполнить некоторое тестирование (я использую этот бесплатный инструмент, который я написал):

Процессор: 1,8 ГГц Pentium Core 2 Duo
Количество итераций: 100
Количество элементов в каждом списке: 1000

A.Where(a => B.Contains(a)).Count(): 8338 тиков
A.Intersect(B).Count(): 288 тиков
B.Count - B.Except(A).Count(): 313 тиков

Теперь представим HashSet<int> в нашем тесте (выберите реализацию из любого другого ответа):

HashSet<int>: 163 тика

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

public static int UseBitArray(int range, List<int> listA, List<int> listB) {
    var BitArray array = new BitArray(range);
    for (int i = 0; i < listA.Count; ++i)
        array[listA[i]] = true;

    int count = 0;
    for (int i = 0; i < listB.Count; ++i) {
        if (array[listB[i]])
            ++count;
    }

    return count;
}

Как это работает?

BitArray: 95 тиков

Требуется только 58% второго лучшего метода (HashSet<int>). Я даже не сравниваюсь с другими. Обратите внимание, что он использует память сильно и для широкого диапазона (скажем, Int32.MaxValue / 2), он использует много памяти (кроме того, его размер ограничен Int32.MaxValue, тогда вы не можете иметь полный 32-битный целочисленный диапазон. Если его ограничения для вас не проблема, тогда вам обязательно нужно пойти с ним.

Также обратите внимание, что если вы можете сделать некоторые предположения о своих входах, вы можете дополнительно оптимизировать свою функцию поиска (например, если вы можете предположить, что наборы упорядочены).

Как они масштабируются (масштаб оси Y является логарифмическим):

Обратите внимание, что Except работает лучше, чем Intersect, когда число элементов растет. Также обратите внимание, что для такого тривиального объекта (целого) вы не будете иметь никакого увеличения производительности, чтобы сделать это параллельно (см. Также Поиск разницы между двумя списками строк): сравнение настолько тривиально, что накладные расходы и синхронность выше преимуществ (если только он не настроил алгоритм на ОЧЕНЬ большое количество элементов).

Если вы действительно ищете последний бит производительности, вы можете даже реализовать свой собственный класс BitArray (без ненужного материала и проверки ошибок):

sealed class FastBitArray {
    public FastBitArray(int length) {
        m_array = new int[((length - 1) / 32) + 1];
    }

    public bool this[int index] {
        get {
            return (m_array[index / 32] & (1 << (index % 32))) != 0;
        }
        set {
            if (value)
                m_array[index / 32] |= (1 << (index % 32));
            else
                m_array[index / 32] &= ~(1 << (index % 32));
        }
    }

    private int[] m_array;
}

Обратите внимание, что внутри сеттера есть ветка, нам не нужно беспокоиться, чтобы ее оптимизировать, потому что шаблон прост (всегда true) для предсказателя ветвления. Нет повышения производительности, чтобы сделать его более сложным, чем это.

Последние тесты:

Число итераций: 100
Количество элементов в каждом списке: 1000000

HashSet<int>: 144748 тиков
BitArray: 37292 тиков
FastBitArray: 28966 тиков

Сравнивать их визуально (синяя серия - это тест с 1000 наименованиями, оранжевая серия - 1 000 000, ось Y - логарифмическая для простого сравнения с серией 1k). Методы, которые мы знаем, медленны, просто пропущены:

Те же данные, показывающие только 1M-ряд и линейную ось Y:

Ответ 4

HashSet<int> Btemp = new HashSet<int>(B);
var x = A.Count(p => B.Contains(p));

// or var x = A.Count(B.Contains); 
// but I have always found it to be a little unreadable to skip a lambda
// but this shorted form could be a little faster, because it skips a delegate

или

HashSet<int> Btemp = new HashSet<int>(B);
Btemp.IntersectWith(A); // note that this method is of the HashSet, it isn't 
                        // a "generic" Intersect, so it optimized against 
                        // the HashSet internals
var y = Btemp.Count;

(теоретически как добавление, так и проверка существования в HashSet являются операциями O(1))

оба из них O(n), где n = A.Count вместо O(m * n) с m = B.Count, поэтому O(x^2).

(технически они O(n) + O(m), потому что построение HashSet равно O(m), но оно все еще O(x))...

В конце они линейны во времени, а не квадратичны... Но все это зависит от длины B... Если B - 1-3 элемента, возможно, быстрее использовать непосредственно Contain, поскольку вы сделал.

В общем, если вы знаете, что A намного больше B, тогда вы должны положить A в HashSet и оставить B в List (вы должны сделать обратное, если B намного больше, чем A)

Ответ 5

У меня была такая же проблема, но я искал что-то более эффективное.

// Testcase: 500 items exist in both lists
List<int> InputA = Enumerable.Range(0, 1000).ToList();
List<int> InputB = Enumerable.Range(500, 1000).ToList();

// Result
int Result1 = InputA.Where(a => InputB.Contains(a)).Count(); //13000 ticks
int Result2 = InputA.Intersect(InputB).Count(); //5700 ticks
int Result3 = B.Count - B.Except(A).Count(); //5800 ticks

int Result4 = InputA.CountIntersect(InputB); //2400 ticks

Мое решение равно внутреннему методу Intersect, только с подсчетом и без копирования элементов. Вот почему он более чем в 2 раза быстрее.

Код:

public static int CountIntersect<T>(this IEnumerable<T> collectionA, IEnumerable<T> collectionB)
{
    HashSet<T> tempA = new HashSet<T>(collectionA);
    int Result = 0;
    foreach (var itemB in collectionB)
    {
        if (tempA.Remove(itemB))
            Result++;
    }
    return Result;
}

Ответ 6

вы можете получить это, используя этот

A.Count(match => B.Contains(match));

или

var count = A.Count(B.Contains);

Ответ 7

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

• Сортировка (легко выполняется в LINQ с помощью OrderBy) элементов в списке B - complex O(m log m) - и поиск элементов в ней с помощью Бинарный поиск. Общая сложность O(n log m) (принимая n как число элементов в A и m как число элементов в B).
• Преобразование (с использованием метода ToDictionary) B в словаре (сложность O(m)). Таким образом, общая сложность становится max(O(n), O(m)).

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

Сообщите мне, если что-то неясно.

Ответ 8

вы можете использовать метод Intersect и count

List<int> A = new List<int>;
List<int> B = new List<int>;
// Some logic....item added in both lists. Then
A.Intersect(B).Count();

Ответ 9

Вероятно, это не лучшая производительность, но лучше OP и решение linq.

другой подход с Except()

int Result = B.Count - B.Except(A).Count();

Ответ 10

Прежде всего важно знать, могут ли ваши списки содержать дубликаты и как вы хотите их подсчитать, если они есть.

Например:

var listA = new List<int> { 1, 1, 1, 2, 3, 4, 4, 5 };
var listB = new List<int> { 1, 1, 2, 2, 3, 4, 5, 6 };
var result = listA.Intersect(listB).Count(); // 5

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

public static int GetDuplicatesCount(List<int> listA, List<int> listB)
{
    var tempB = new HashSet<int>(listB);
    return listA.Count(tempB.Contains);
}

Он вернет 8 для списков выше. Также вы можете попытаться профилировать более подробную версию:

public static int GetDuplicatesCount(List<int> listA, List<int> listB)
{
    var tempB = new HashSet<int>(listB);
    var result = 0;
    foreach (var item in listA)
    {
        if (tempB.Contains(item))
        {
            result++;
        }
    }
    return result;
}

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

Ответ 11

Если списки ОЧЕНЬ большие, и вы хотите быть эффективными, первое, что вам нужно сделать, это отсортировать их. Второе, что нужно сделать, - удалить дубликаты в целевом (несчисленном списке). Но если проблема достаточно велика, то простых выражений linq, описанных в других ответах, недостаточно. Вы должны нажать данные на SQL-сервер и запустить запрос, чтобы получить ответ. Тогда многопоточность sqlserver позаботится о масштабировании, которое вам понадобится, если проблема будет большой.

Ответ 12

Мы не можем использовать HashSet для первого списка, так как вполне возможно, что список содержит повторяющиеся записи... Однако мы можем создать HashSet для второго списка (добавляет сложность пространства + O (m), но мы могли бы начать с HashSet), поскольку дубликаты не имеют смысла... Затем мы можем выполнить итерацию по первому списку и проверить, содержит ли HashSet значение... Это будет сложность O (n) (для цикла) и сложность O (1) для проверки HashSet...

Используется LinqPad....

  var lst = new List<int>{1,2,3,4,4,5,6,7};
  var lst2 = new List<int>{4,4,6};

  int count=0;
  var hs= new HashSet<int>(lst2);  //O(m) ... contains {4,6}
  foreach (var l in lst)  // O(n)
  {
    if (hs.Contains(l))  // O(1)
      count++;
  }
  count.Dump();  //returns 3

Ответ 13

A.Where(B.Distinct().ToDictionary(_ => _).ContainsKey).Count(); //This should work for other scenario with good performance

Ответ 14

С точки зрения строгих структур данных лучше всего сделать это O (n * m), если ваш вход не сортирован. См. Примечания ниже о том, почему O (n + m) не обязательно правильно.

Отвратительный Psuedocode:

int FindCommonIntersects (ListA, ListB){
    int return_var = 0
    for each_a_entry in ListA: // Assumes that ListA is sorted
        if each_a_entry != each_a_entry->next.value() then:
            for each_b_entry in ListB:
                if each_a_entry == each_b_entry then return_var++
    return return_var;

Переход через O (n) для списка A и O (m) для списка B, если списки не отсортированы

Ergo оптимальное решение работает в точке O (n * m), где вы проходите только один раз. Обратите внимание, что даже если в есть несколько элементов, которые являются одинаковыми, строка each_a_entry != each_a_entry->next.value() означает, что мы не проводим сравнение с элементом B, тем самым сохраняя некоторое время.

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

Ответ 15

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