Linq和二进制搜索 - 提高这慢哪里声明？

Question

我有两个收藏，每个收藏约40,000个物品。

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

对于列表1中的每个元素，我想找到列表2中的相应元素。

事情是这样的：

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

这工作，但它的速度慢得要命。

现在，列表1和列表2都由数据库中的这些键排序。所以list1按ChildID排序，list2按ID排序（相同的值）。

我认为二进制搜索会大大加快速度，但我在某处读到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

不知道这实际上会加速它的任何，但可以断言移动到FirstOrDefault（）子句并获得其中完全消除。

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

它可能实际上没有帮助，因为这可能隐式地调用Where（）。

虽然这是一个问题，但方法实际上很慢，还是只在编译后第一次运行时才慢呢？查看on this post的讨论。

Answer 3

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

您是否考虑过使用Dictionary而不是List？

您可以实现一个字典，然后代替使用Where，您可以使用ContainsKey，如果它存在，则使用index accessor获取该值。

示例代码：

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

... 

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

访问使用指数会比搜索列表，在为索引所需的额外内存的成本显著更快。

Answer 4

这个怎么样：

 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 5

由于两个列表在相同的值进行排序，你可以通过它们并行只是循环：

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 6

我忍不住回答这个问题:-)

你的代码变慢的主要原因是你的物品会被许多次重复使用。速度的艺术是：只有在你需要的时候才能阅读记忆，如果你需要阅读，尽量少阅读。

下面是一个例子：

代码

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

示例代码：

主要目标是扫描列表和对当前指标比较的项目和itemdetail。当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倍以上的项目看到一个更好的结果：

添加项目：
总毫秒：140ms的
添加itemdetails：
总毫秒：203ms
ItemList Count：400000
ItemDetailList Count：800000
匹配项：
总毫秒数：265ms

这是打字速度快，可能更干净。所以我希望你能阅读它。玩吧。

Greetz， Jeroen。