快速路

Question

List1: {"123456", "432978", "321675", …} // containing 100,000 members 

List2: {"7674543897", "1234568897", "8899776644",…} // containing 500,000 members 

我想提取列表2的所有項目，他們的前6位是從列表1的成員，所以這裏字符串「1234568897」是有效的，因爲它的前6位數字是來自List1的第一個項目。 這樣做的最快方法是什麼？

foreach(string id in List1) 
    { 
    string result = List2.FirstOrDefault(x => x.Contains(id)); 
    if(result!=null) 
     { 
     //some works here 
     } 
} 

這個工程的一組小於1000，但是當列表2項增長這個時間太長

Answer 1

您可以使用Enumerable.Join這是quite efficient：

var match = from str1 in List1 
      join str2 in List2 
      on str1 equals (str2.Length < 6 ? str2 : str2.Substring(0, 6)) 
      select str2; 

Demo

編輯

由於@Oleksandr Pshenychnyy認爲這樣的大集合會非常慢，因此這裏是一個演示，其中列表1中包含100000個隨機字符串，列表2中包含與該問題中相同範圍的500000個字符串。它執行在600毫秒的ideone：

http://ideone.com/rB6LU4

Answer 2

這在很大程度上取決於你正在運行的硬件。 雖然你可能會參與過早的優化。它可能足夠快，只是蠻橫的逼迫它。 500,000 * 100,000是您的最大比較次數（即，如果沒有任何匹配）在合理規格的臺式電腦上真的不需要很長時間。

如果你發現這是太慢了你的目的則有，你可以用它來提高性能的幾個技巧：

1. Parallelise它。這隻會在多核硬件上顯示出巨大的優勢。基本上，你需要一個調度器類，它將List2中的數字提供給執行搜索List1中匹配的線程。請參閱Task Parellel Library。

2. 通過變聰明來減少比較次數。對您的藏品進行一些預分析以改善其比較步驟的特徵。例如將List1中的項目放入「桶」列表中，其中每個桶包含具有相同前兩個數字的所有序列。例如桶1將包含那些開始「00」，桶2「01」等等。當你做實際的比較時，你只需要比較少量的字符串。在你的例子中，對於「1234568897」，我們將檢查桶爲「12」，然後我們知道我們只需要對該桶中的字符串進行全字符串比較。

這種預處理實際上可能會讓速度變慢，所以請確保您確定自己的代碼。

Answer 3

實現您所需要的最有效的方法是Aho-Corasick的算法 - 如果您需要動態處理列表2的新元素。它基於前綴樹，這是字符串搜索算法中常用的技術。那些算法會給你複雜的O（所有字符串長度的總和）

另一種選擇是Knuth-Morris-Pratt算法，它會給你相同的複雜度，但最初使用單個字符串進行搜索。

但是，如果你可以用O((list2.Count*log(list2.Count) + list1.Count*log(list1.Count))*AverageStrLength)，我可以提出我的簡單實現： 排序兩個列表。然後同時沿着它們並選擇匹配。

更新：當您已經排序列表時，此實現很好。然後它在大約100ms內執行。但排序本身需要3.5秒，因此實施起初並不如我預期的那麼好。至於簡單的實施，蒂姆的解決方案更快。

list1.Sort(); 
list2.Sort(); 
var result = new List<string>(); 
for(int i=0, j=0; i<list1.Count; i++) 
{ 
    var l1Val = list1[i]; 
    for (; j < list2.Count && string.CompareOrdinal(l1Val, list2[j]) > 0; j++) ; 
    for (; j < list2.Count && list2[j].StartsWith(l1Val); j++) 
    { 
     result.Add(list2[j]); 
    } 
} 

這是我可以提出的最簡單高效的實現。