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

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

我想提取 List2 中前 6 位来自 List1 成员的所有项目，所以这里的字符串“1234568897”是有效的，因为它的前 6 位来自 List1 的第一项。最快的方法是什么？

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

这适用于少于 1000 个的组，但是当 List2 项目增长时，这需要太长时间

4

3 回答 3

3

您可以使用Enumerable.Join非常有效的方法：

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

演示

编辑

由于@Oleksandr Pshenychnyy 认为这样大的集合会很慢，所以这里有一个演示，其中 list1 中有 100000 个随机字符串，list2 中有 500000 个字符串，范围与问题中的相同。它在 ideone 上执行 600 毫秒：

http://ideone.com/rB6LU4

于 2013-03-06T11:51:44.267 回答
0

这在很大程度上取决于您正在运行的硬件。不过，您很可能正在进行过早的优化。简单地暴力破解它可能就足够快了。500,000 * 100,000 是您的最大比较次数（即，如果没有匹配项）这在合理规格的台式 PC 上真的不会花很长时间。

如果您发现这对于您的目的来说太慢了，那么您可以使用一些技术来提高性能：

  1. 并行化它。这只会在多核硬件上显示出巨大的好处。从本质上讲，您需要一个调度程序类，它将 List2 中的数字提供给执行在 List1 中搜索匹配项的线程。请参阅任务并行库。

  2. 通过变得更聪明来减少比较次数。对您的集合进行一些预分析，以改进它们的特征以进行比较步骤。例如，将 List1 中的项目放入“桶”列表中，其中每个桶包含具有相同前 2 个数字的所有序列。例如，存储桶 1 将包含以“00”开头的那些，存储桶 2 “01”等。当您进行实际比较时，您只需比较少量字符串。从您的示例中，对于“1234568897”，我们将检查存储桶中的“12”，然后我们知道我们只需要与该存储桶中的字符串进行完整的字符串比较。

这种预处理实际上可能会使事情变慢，因此请确保您分析您的代码以确保。

于 2013-03-06T12:05:00.183 回答
0

实现所需内容的最有效方法是Aho-Corasick算法- 如果您需要动态处理 List 2 的新元素。它基于前缀树，这是字符串搜索算法中常用的技术。这些算法会给你O的复杂度（所有字符串长度的总和）

另一个选项是Knuth-Morris-Pratt算法，它会给您相同的复杂性，但最初使用单个字符串进行搜索。

但如果你对没问题O((list2.Count*log(list2.Count) + list1.Count*log(list1.Count))*AverageStrLength)，我可以提出我的简单实现：对两个列表进行排序。然后同时进行并选择匹配项。

更新：当您已经对列表进行排序时，此实现很好。然后它在大约 100 毫秒内执行。但是排序本身需要 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]);
    }
}

这是我能提出的最简单有效的实现。

于 2013-03-06T12:21:26.267 回答