Цикл по двум коллекциям - производительность и возможности оптимизации

Question

Это, вероятно, очень распространенная проблема, которая имеет много ответов. Я не смог найти ответ, потому что не очень уверен, как его искать.

У меня есть две коллекции объектов - обе взяты из базы данных, и в некоторых случаях эти коллекции относятся к одному и тому же типу объектов. Кроме того, мне нужно выполнить некоторые операции для каждой комбинации этих коллекций. Так, например:

foreach(var a in collection1){
 foreach(var b in collection2){
   if(a.Name == b.Name && a.Value != b.Value)
      //do something with this combination
   else 
      //do something else
}
}

Это очень неэффективно и становится медленнее в зависимости от количества объектов в обеих коллекциях.

Как лучше всего решить этот тип проблем?

РЕДАКТИРОВАТЬ:

В настоящее время я использую .NET 4, поэтому меня также интересуют предложения по использованию параллелизма для ускорения этого процесса.

РЕДАКТИРОВАТЬ 2: Выше я добавил пример бизнес-правил, которые должны выполняться для каждой комбинации объектов. Однако бизнес-правила, определенные в примере, могут отличаться.

РЕДАКТИРОВАТЬ 3: Например, внутри цикла будет сделано следующее: Если бизнес-правила выполнены (см. Выше), в базе данных будет создана запись со ссылкой на объект A и объект B. Это одна из операций, которые мне нужно сделать. (Операции будут настраиваться из дочерних классов, использующих этот класс).

Answer 1

Если вам действительно нужно обработать каждый элемент в списке b для каждого элемента в списке a, тогда потребуется время, пропорциональное a.Count * b.Count.Вы ничего не можете сделать, чтобы предотвратить это.Добавление параллельной обработки даст вам линейное ускорение, но это не повлияет на время обработки, если списки даже достаточно велики.

Насколько велики эти списки?Вам действительно нужно проверять каждую комбинацию a и b?Можете ли вы дать нам больше информации о проблеме, которую вы пытаетесь решить?Я подозреваю, что есть способ применить более эффективный алгоритм, который уменьшит ваше время обработки на порядки.

Изменить после публикации дополнительной информации

IЗнайте, что приведенный вами пример - всего лишь пример, но он показывает, что вы можете найти лучший алгоритм по крайней мере для некоторых ваших случаев.В этом конкретном примере вы можете отсортировать a и b по имени, а затем выполнить прямое слияние.Или вы можете отсортировать b в массив или список и использовать двоичный поиск для поиска имен.Любой из этих двух вариантов будет работать намного лучше, чем ваши вложенные циклы.Фактически, намного лучше, так что вам, вероятно, не придется беспокоиться о распараллеливании.

Посмотрите на числа.Если ваш a содержит 4000 элементов, а b содержит 100 000 элементов, ваш вложенный цикл выполнит 400 миллионов сравнений (a.Count * b.Count).Но сортировка составляет всего n log n, а слияние является линейным.Таким образом, сортировка и последующее слияние будут примерно (a.Count * 12) + (b.Count * 17) + a.Count + b.Count или около 2 миллионов сравнений.Это примерно в 200 раз быстрее.

Сравните это с тем, что вы можете сделать с параллельной обработкой: только линейное ускорение.Если у вас четыре ядра и вы получаете линейное ускорение, вы сократите время только в четыре раза.Более качественный алгоритм сокращает время в 200 раз с помощью одного потока.

Вам просто нужно найти лучшие алгоритмы.

LINQ также может обеспечить хорошее решение.Я не эксперт по LINQ, но, похоже, он сможет быстро справиться с чем-то вроде этого.

Answer 2

Прежде всего, есть причина, по которой вы ищете значение из первой коллекции во второй коллекции.

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

Answer 3

Если вам нужно проверить все варианты один за другим, вы не сможете сделать ничего лучше. НО вы можете распараллелить петли. Например, если вы используете c # 4.0, вы можете использовать параллельный цикл foreach.

Вы можете найти пример здесь ... http://msdn.microsoft.com/en-us/library/dd460720.aspx

foreach(var a in collection1){
Parallel.ForEach(collection2, b =>
            {

//do something with a and b
            } //close lambda expression
                 ); 
}

Точно так же вы можете распараллелить и первый цикл.

Answer 4

Parallel.ForEach(a, currentA => Parallel.ForEach(b, currentB =>
                                                                {
             // do something with currentA and currentB
                                                                }));