快速路

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

这是我可以提出的最简单高效的实现。