改善目前的LINQ的時間複雜查詢

Question

我有以下列表：

RakeSnapshots, ProductMovements

目的是既處理，並得到符合條件的元素的數量，具體如下：

• 考慮RakeSnapshots與StatusCode == "Dumping"

• 考慮ProductMovementStatus == "InProgress"

• 抓取所有的元素都列出，滿足條件RakeSnapshots.RakeCode等於ProductMovements.ProductCode

以下是我目前的選擇的count：

//代碼1：

var resultCount = ProductMovements.Where(x => RakeSnapshots 
               .Where(r => r.StatusCode == "Dumping") 
               .Any(y => y.RakeCode == x.ProductCode && 
                  x.Status == "InProgress")) 
               .Count(); 

//代碼2：

var productMovementsInprogress = ProductMovements.Where(x => x.Status == "InProgress"); 

var rakeSnapShotsDumping = RakeSnapshots.Where(r => r.StatusCode == "Dumping"); 

var resultCount = productMovementsInprogress.Zip(rakeSnapShotsDumping,(x,y) => (y.RakeCode == x.ProductCode) ? true : false) 
              .Where(x => x).Count(); 

挑戰既是代碼O(n^2)複雜，有沒有改善它的方式，如果數據是非常大的

Answer 1

您可以使用inner join做到這一點：

var dumpingRakeSnapshots  = rakeSnapshots.Where(r => r.StatusCode == "Dumping"); 
var inProgressProductMovements = productMovements.Where(p => p.Status == "InProgress"); 

var matches = 
    from r in dumpingRakeSnapshots 
    join p in inProgressProductMovements on r.RakeCode equals p.ProductCode 
    select r; 

int count = matches.Count(); // Here's the answer. 

注意（伊萬Stoev指出的）這僅適用於如果RakeCode是RakeSnapshots主鍵。

如果不是，您將不得不使用grouped join。

下面是你應該在這種情況下使用，但請注意，這是完全一樣伊萬的答案（僅在Linq查詢形式）LINQ查詢語法版本：

var matches = 
    from r in dumpingRakeSnapshots 
    join p in inProgressProductMovements on r.RakeCode equals p.ProductCode into gj 
    select gj; 

---

爲了完整起見，這裏是一個演示了不同的結果可編譯控制檯應用程序，你會得到，如果RakeCode和ProductCode不是主鍵：

using System; 
using System.Collections.Generic; 
using System.Linq; 

namespace ConsoleApp1 
{ 
    class RakeSnapshot 
    { 
     public string StatusCode; 
     public string RakeCode; 
    } 

    class ProductMovement 
    { 
     public string Status; 
     public string ProductCode; 
    } 

    sealed class Program 
    { 
     void run() 
     { 
      var rakeSnapshots = new List<RakeSnapshot> 
      { 
       new RakeSnapshot {StatusCode = "Dumping", RakeCode = "1"}, 
       new RakeSnapshot {StatusCode = "Dumping", RakeCode = "1"}, 
       new RakeSnapshot {StatusCode = "Dumping", RakeCode = "2"} 
      }; 

      var productMovements = new List<ProductMovement> 
      { 
       new ProductMovement {Status = "InProgress", ProductCode = "1"}, 
       new ProductMovement {Status = "InProgress", ProductCode = "2"}, 
       new ProductMovement {Status = "InProgress", ProductCode = "2"} 
      }; 

      var dumpingRakeSnapshots  = rakeSnapshots.Where(r => r.StatusCode == "Dumping"); 
      var inProgressProductMovements = productMovements.Where(p => p.Status == "InProgress"); 

      // Inner join. 

      var matches1 = 
       from r in dumpingRakeSnapshots 
       join p in inProgressProductMovements on r.RakeCode equals p.ProductCode 
       select r; 

      Console.WriteLine(matches1.Count()); 

      // Grouped join. 

      var matches2 = 
       from r in dumpingRakeSnapshots 
       join p in inProgressProductMovements on r.RakeCode equals p.ProductCode into gj 
       select gj; 

      Console.WriteLine(matches2.Count()); 

      // OP's code. 

      var resultCount = 
       productMovements 
       .Count(x => rakeSnapshots 
       .Where(r => r.StatusCode == "Dumping") 
       .Any(y => y.RakeCode == x.ProductCode && x.Status == "InProgress")); 

      Console.WriteLine(resultCount); 
     } 

     static void Main(string[] args) 
     { 
      new Program().run(); 
     } 
    } 
} 

Answer 2

聽起來Group Join這樣會傷害它（以及Join）是最有效的LINQ方式關聯兩組：

var resultCount = ProductMovements.Where(p => p.Status == "InProgress") 
    .GroupJoin(RakeSnapshots.Where(r => r.StatusCode == "Dumping"), 
     p => p.ProductCode, r => r.RakeCode, (p, match) => match) 
    .Count(match => match.Any()); 

以上的時間複雜度是O（N + M）。

Answer 3

常，用O（N^2），你會創建一箇中間的'搜索'數據結構來加速查找。類似於O（1）訪問的散列表，或者O（log N）訪問的排序列表。

從技術上講，你有兩個不同的列表，所以實際的訂單是O（P.R），其中P是產品移動的數量，R是耙子快照的數量。

就你而言，這是你的原始代碼;

var resultCount = ProductMovements 
    .Where(x => RakeSnapshots 
     .Where(r => r.StatusCode == "Dumping") 
     .Any(y => y.RakeCode == x.ProductCode && 
        x.Status == "InProgress")) 
     .Count(); 

爲O（PR），因爲每一個P，內where子句通過每一個R.循環我想看看創造一個Dictionary<T>或HashSet<T>，然後改變你的代碼，類似

var rakeSnapshotSummary = ... magic happens here ...; 
var resultCount = ProductMovements 
    .Where(x => rakeSnapshotSummary[x.ProductCode] == true) 
    .Count(); 

以這種方式，創建快照是O（R），查找到所述數據結構是O（1），和創建的結果是O（P），對於更健康O（P + R）。我的事情就是這樣。

所以我對你的指數例行程序的建議會是這樣的;

var rakeSnapshotSummary = new HashSet<string>(RakeSnapshots 
    .Where(r => r.StatusCode == "Dumping") 
    .Select(r => r.RakeCode)); 

這產生了HashSet<string>這將有用於的耙代碼測試所有腦幹O（1）時間複雜度。然後最終行看起來像

var resultCount = ProductMovements 
    .Where(x => x.Status == "InProgress" && rakeSnapshotSummary.Contains(x.ProductCode)) 
    .Count(); 

所以，總體來說，O（P + R）或，大致，O（2N）=> O（N）。