c# - 在这个例子中，为什么 For Each 循环比 linq 的外部连接慢？

Question

客户对象有 30,000 条记录，订单对象有 20,000 条记录。使用 for each 的左连接比使用 linq 的组连接慢 4 秒。我有两个问题:

1. 这是什么原因？

2. 如何在不使用 linq 的情况下使其更快？

   foreach (Customer c in Customers) {
       foreach (Order o in Orders) {
           if (c.ID == o.OwnerID) {
               c.OrderName = o.OrderName;
               break; 
           }
       }
   }
   

Answer 1

Processing a sorted array is always faster . (这可能是 stackoverflow 中最受欢迎的答案之一)。这个问题与硬件有关，但软件也能从中获益。

对两个数组进行排序。

现在从外循环的最新索引(等于 ownerid)等同于内循环索引开始内循环，而不是从零开始。你已经提前退出了，所以总的复杂度是

O(small) + O(small) instead of O(bruteforce)
sorting    nested loop         nested loop unsorted

---

如果您有时间，可以安装 arrayfire(C++) 并围绕它获取一些包装器，以便在 C# 中用于这些强力计算。只有这种作弊会比 linq 对小型 (30k-100k) 数组的连接更好。

当元素数量达到数百万并且算法变得最重要时，作弊就会消失，除非你有 3-4 个高端 gpus 以防万一。然后它会停留在 30M 左右，然后算法会再次发光，除非你有一个集群，但如果你有集群，那么不使用高级算法将是一种浪费。

---

当使用 CPU 时，最好是 C# 自己的实现。在 Ivan Stoev 的评论中，一个好的散列函数比排序更好。