Linq и двоичный поиск — улучшите этот медленный оператор Where?

Question

У меня есть две коллекции, каждая из которых содержит около 40 000 предметов.

Элементы списка 2 связаны с элементами первого списка через внешний ключ.

Для каждого элемента первого списка я хочу найти соответствующий элемент во втором списке.

Что-то вроде этого:

foreach(var item in list1)
{
  var match = list2.Where(child => child.ID == item.ChildID).FirstOrDefault();
  item.Child = match;
}

Это работает, но чертовски медленно.

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

Я думаю, что двоичный поиск значительно ускорит этот процесс, но я где-то читал, что Linq выберет наиболее подходящую стратегию для списка в предложении Where.Может быть, мне нужно явно привести к отсортированному списку?Или, может быть, мне нужно реализовать собственный алгоритм двоичного поиска с компаратором?

Любые идеи приветствуются.

Спасибо.

Answer 1

Почему бы не использовать соединение?

var query = 
   from a in list1
   join b in list2 on a.ChildID equals b.ID
   select new {Item1 = a, Item2 = b};

foreach(var item in query)
{
   item.Item1.Child = item.Item2;
}

Answer 2

Как насчет этого:

        var joined = list1.Join(list2, x => x.ChildID, x => x.ID, (x, y) => new { x, y });

        foreach (var j in joined)
        {
            j.x.Child = j.y;
        }

?

Answer 3

У меня была эта проблема раньше: поиск на основе LINQ выполняется очень медленно по сравнению с поиском на основе БД, поскольку он не использует какой-либо индекс.

Рассматривали ли вы возможность использования Словарь вместо списка?

Вы можете реализовать словарь, а затем вместо использования Where вы можете использовать Содержит ключ и если оно существует, получите значение, используя метод доступа к индексу.

Образец кода:

Dictionary<int, Child> list2 = ...;

...

foreach(var item in list1)
{
  if (list2.ContainsKey(item.ChildID))
    item.Child = list2[item.ChildID];
}

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

Answer 4

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

int index1 = 0, index2 = 0;
while (index1 < list1.Count && index2 < list2.Count) {
   while (index1 < list1.Count && list1[index1].ChildId < list2[index2].Id) index1++;
   if (index1 < list1.Count) {
      while (index2 < list2.Count && list2[index2].Id < list1[index1].ChildId) index2++;
      if (index2 < list2.Count && list1[index1].ChildId == list2[index2].Id) {
         list1[index].Child = list2[index2];
         index1++;
         index2++;
      }
   }
}

или:

int index1 = 0, index2 = 0;
while (index1 < list1.Count && index2 < list2.Count) {
   if (list1[index1].ChildId == list2[index2].Id) {
      list1[index].Child = list2[index2];
      index1++;
      index2++;
   } else {
      if (list1[index1].ChildId < list2[index2].Id) {
         index1++;
      } else {
         index2++;
      }
   }
}

Другая эффективная альтернатива, но не использующая преимущества порядка списков, — создать индекс, поместив один из списков в словарь:

Dictionary<int, TypeOfChild> index = new Dictionary<int, TypeOfChild>();
foreach (TypeOfChild child in list2) {
   index.Add(child.Id, child);
}
foreach (TypeOfParent parent in list1) {
   TypeOfChild child;
   if (index.TryGetValue(parent.ChildId, out child) {
      parent.Child = child;
   }
}

Answer 5

Я не мог удержаться от ответа :-)

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

Вот пример:

код

public class Item
{    
   private int _id;
   private List<ItemDetails> _detailItems = new List<ItemDetails>();

   public Item(int id)<br>
   {
       _id = id;
   }

   public void AddItemDetail(ItemDetails itemDetail)
   {
       _detailItems.Add(itemDetail);
   }

   public int Id
   {
       get { return _id; }
   }
   public ReadOnlyCollection<ItemDetails> DetailItems
   {
       get { return _detailItems.AsReadOnly(); }
   }
}


public class ItemDetails
{
    private int _parentId;

    public ItemDetails(int parentId)
    {
        _parentId = parentId;
    }

    public int ParentId
    {
        get { return _parentId; }
    }
}

пример кода:

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

// for performance tests..
DateTime startDateTime;

// create 2 lists  (master/child list)
List<Item> itemList = new List<Item>();
List<ItemDetails> itemDetailList = new List<ItemDetails>();

Debug.WriteLine("# Adding items");
startDateTime = DateTime.Now;

// add items (sorted)
for (int i = 0; i < 400000; i++)
    itemList.Add(new Item(i));

// show how long it took
Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms" );

// adding some random details (also sorted)
Debug.WriteLine("# Adding itemdetails");
Random rnd = new Random(DateTime.Now.Millisecond);

startDateTime = DateTime.Now;

int index = 0;
for (int i = 0; i < 800000; i++)
{
    // when the random number is bigger than 2, index will be increased by 1
    index += rnd.Next(5) > 2 ? 1 : 0;
    itemDetailList.Add(new ItemDetails(index));
}
Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms");

// show how many items the lists contains
Debug.WriteLine("ItemList Count: " + itemList.Count());
Debug.WriteLine("ItemDetailList Count: " + itemDetailList.Count());

// matching items
Debug.WriteLine("# Matching items");
startDateTime = DateTime.Now;

int itemIndex = 0;
int itemDetailIndex = 0;

int itemMaxIndex = itemList.Count;
int itemDetailMaxIndex = itemDetailList.Count;

// while we didn't reach any end of the lists, continue...
while ((itemIndex < itemMaxIndex) && (itemDetailIndex < itemDetailMaxIndex))
{
    // if the detail.parentid matches the item.id. add it to the list.
    if (itemList[itemIndex].Id == itemDetailList[itemDetailIndex].ParentId)
    {
        itemList[itemIndex].AddItemDetail(itemDetailList[itemDetailIndex]);
        // increase the detail index.
        itemDetailIndex++;
    }
    else
        // the detail.parentid didn't matches the item.id so check the next 1
        itemIndex++;
}

Debug.WriteLine("Total milliseconds: " + (DateTime.Now - startDateTime).TotalMilliseconds.ToString("0") + "ms");

Результаты

Я взял в 10 раз больше предметов, чтобы увидеть лучший результат:

Добавление предметов:
Всего миллисекунд:140 мс
Добавляем детали товара:
Всего миллисекунд:203 мс
Количество предметов в списке:400000
Количество ItemDetailList:800000
Соответствующие предметы:
Всего миллисекунд:265 мс

Это было напечатано быстро и могло бы быть чище.Так что я надеюсь, что вы сможете это прочитать.Играть с этим.

Здравствуйте, Йерун.

Answer 6

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

item.Child = list2.FirstOrDefault(child => child.ID == item.ChildID)

На самом деле это может не помочь, поскольку это может просто неявно вызывать Where().

Однако вот вопрос: действительно ли этот метод медленный или он медленный только при первом запуске после компиляции?Посмотрите обсуждение на этом посту.