3

我有两个系列，每个系列包含大约 40,000 件物品。

列表 2 中的元素通过外键链接到列表 1 中的元素。

对于列表一的每个元素，我想在列表二中找到相应的元素。

像这样的东西：

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 子句中的列表选择最合适的策略。也许我需要明确地转换为排序列表？或者也许我需要使用比较器实现自定义二进制搜索算法？

任何见解都值得赞赏。

谢谢。

4

6 回答 6

11

为什么不使用联接？

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;
}
于 2009-08-25T17:18:53.140 回答
1

我之前遇到过这个问题，基于 LINQ 的搜索与基于 DB 的搜索相比非常慢，因为它没有使用任何索引。

您是否考虑过使用字典而不是列表？

您可以实现一个 Dictionary ，然后使用ContainsKey而不是使用 Where，如果它确实存在，则使用index accessor获取值。

示例代码：

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

...

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

使用索引访问将比搜索列表快得多，因为索引需要额外的内存。

于 2009-08-25T17:28:35.103 回答
1

那这个呢：

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

?

于 2009-08-25T17:31:52.727 回答
1

由于两个列表都按相同的值排序，因此您可以并行循环它们：

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;
   }
}
于 2009-08-25T17:35:09.707 回答
1

我忍不住回答这个:-)

您的代码变慢的主要原因是您的项目将被多次读取。速度的艺术是：仅在需要时读取内存，如果需要读取，则尽可能少地读取。

这是一个例子：

代码

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

示例代码：

主要目标是扫描列表并比较当前索引上的 item 和 itemdetail。当 parentid 等于它的父母 id 时。将其添加到列表中并继续下一个细节。如果不同，请转到下一位父母。

// 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项目
详细列表计数：800000
匹配项目：
总毫秒：265 毫秒

这打字很快，可以更干净。所以我希望你能读到它。玩它。

格雷茨，杰伦。

于 2009-10-05T20:38:05.233 回答
0

不确定这是否真的会加快速度，但您可以将谓词移动到 FirstOrDefault() 子句并完全摆脱 where 。

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

它实际上可能没有帮助，因为这可能会隐式调用 Where()。

不过，这里有一个问题，该方法实际上是慢还是仅在编译后第一次运行时才慢？看看这篇文章的讨论。

于 2009-08-25T17:19:54.340 回答