Linq и бинарный поиск - улучшить это медленное утверждение Where? - PullRequest
Новая
       4

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

3 голосов
/ 25 августа 2009

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

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

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

Примерно так: 

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

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

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

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

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

Спасибо.

Ответы [ 6 ]

11 голосов
/ 25 августа 2009

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

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;
}
1 голос
/ 06 октября 2009

Я не удержался, чтобы ответить на это: -)

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

Вот пример:

код 

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 мс
ItemList Count: 400000
ItemDetailList Count: 800000
Подходящие предметы:
Всего миллисекунд: 265 мс

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

Greetz, Йерун.

1 голос
/ 25 августа 2009

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

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;
   }
}
1 голос
/ 25 августа 2009

Что по этому поводу: 

        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;
        }

1 голос
/ 25 августа 2009

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

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

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

Пример кода: 

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

...

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

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

0 голосов
/ 25 августа 2009

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

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

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

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

...