测试大量字符串与大型 List<string> 匹配的最有效方法

Question

我查看了许多类似的问题，但所给出的方法对于我要完成的任务来说速度过慢，或者是在测试部分匹配，而我不需要并且应该更慢。

我有两个填满字符串的大文件，我需要检查第一个列表中的每个字符串是否与第二个列表中的任何字符串相匹配。我不需要检查是否存在部分匹配，并且所有内容都应正确转义。

第二个字符串列表（要删除的字符串）包含160,000个字符串。我已将其加载到 List<String> 中，然后读取较大文件的每一行，并使用 List<String>.Any(line.contains) 进行测试。

即使只有第一个列表的一小部分（40k个字符串），这也需要很长时间，在我的快速开发计算机上可能超过20分钟。

我的问题在这里

当不需要部分匹配时，比较大量字符串列表与另一个更大的字符串列表时，是否有更有效的方法/最有效的方法是什么？

- Kin

---

听起来很可疑，好像你正在做数据库的工作？ - jk.

不，这只是一个简单的清理一些CSV文件的应用程序。本来不应该花这么长时间制作，也不会经常使用。 - Kin

Answer 1

不要使用List<string>，而是使用HashSet<string>。它具有O（1）查找，而列表的查找时间是O（n）。如果您进行此更改，应该会看到数量级的加速。

使用HashSet.Contains()可能比LINQ的.Any()扩展方法提供稍微更好的性能。

- recursive

---

哇，进步神速。这个有4万个字符串的文件比较起来需要20-30分钟的时间。在测试时我无意中使用了近100万个字符串的列表，只用了约10秒钟的时间。除此之外，我只需改变两行代码就使它正常工作了。 - Kin

我不确定这个短语的上下文，但是该表达通常是一个玩笑或幽默用语，类似于“我不小心把整个清单都做了”。它通常用于指一个人做了某件事情，而不是有意为之。 - Kin

“稍微好一些的性能”是指O(1)和O(N)吗？如果是，那么“稍微”这个词不太合适。 :) - Rotsor

啊，那就是误解了。我从来没有把 as 或 is 当作反射。 - recursive

很多LINQ中的扩展方法对于一些类型都进行了特殊处理。 - configurator

Answer 2

首先，我认为你的逻辑是错误的。将一个委托传递给Contains方法将会进行部分字符串匹配，而你明确声明只想要完全匹配。

抛开这个问题不谈，你的性能问题源于列表数据结构的本质；它并没有被设计成通过“Any”方法进行高效的搜索。

问题在于“Any”仅仅是执行线性搜索，从列表的开头开始，并快速地遍历整个列表直到找到匹配项。如果列表有100K个条目，则每个“未命中”操作将执行100K个字符串比较，每个“命中”操作平均会执行50K个字符串比较。

这非常糟糕。

你应该将List转换为一个字符串HashSet。这种集合需要略微更多的内存，但搜索速度极快。

另一个可能的优化是对其中一个列表进行排序——这是O（n lg n）操作——然后二分搜索已排序的列表，这是O（lg n）操作。

第三个可能的优化是对两个列表进行排序，然后编写一个已排序的列表比较器。显然，已排序的列表比较器比未排序的列表比较器要快得多。你保持对每个列表的索引，并只提前指向“较小”的项目的索引。也就是说，如果列表是

A, B, C, D, G, I
B, D, E, H, I

然后你从指向A和B的索引开始。"A"更小，因此你将第一个索引移动到"B"。现在它们相同了；你有一个匹配。将它们都推进。第一个索引是"C"，第二个索引是"D"。"C"更小，因此将其推进...

---

总的来说，我认为你描述问题的层次太低了。感觉你问的是钻头的问题，但你应该问的是洞的问题。也许钻头本身就不是正确的工具。你能告诉我们为什么要匹配两个大字符串列表吗？也许有更简单的方法来实现你想要的。

- Eric Lippert

---

关于您的第一条评论，我一开始真的不知道该怎么做，我使用的方法是我能找到的最相似情景的最常见解决方案。意识到这并不足够，我来到这里提出正确的问题。 - Kin

你也可以使用基数排序来将第二和第三种方法的排序复杂度降至O(n)。 - mehdi.loa

Answer 3

使用Union和Except运算符获取两个列表之间的差异和相似之处。 Union: http://msdn.microsoft.com/en-us/library/bb341731.aspx Except: http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx 每个函数返回包含结果数据的列表。

- Gage

---

@SethO：你能解释一下你的评论吗？为什么它不能加速？序列的具体实现细节与此事有什么关系？ （翻译）：@SethO：您能解释一下您的评论吗？为什么它不能加速？序列的具体实现细节与此事有什么关系？ - Eric Lippert

@Eric L: 我的意思是对于OP最关心的问题-速度，选择数据结构最为重要。正如你在回帖中建议的那样，更改基础容器（例如从List到Hashset）可以提高OP所需的效率。List1.Except(List2)仍然受到线性复杂度限制，不是吗？ - SethO

@SethO：您声称list1.Except(list2)的时间复杂度是O(n^2)？您基于什么得出这个结论的？ - Eric Lippert

@Eric L：我承认这是一个不太确定的说法（这就是为什么我在上一条评论中寻求意见的原因）。但是，针对你的具体问题，我从MSDN获取了Except()的信息，并根据其签名（IEnumerable<T>）和（请鼓掌）做出了实现的假设。Except()的实现是否经过优化以提供O(n)？ - SethO

@SethO：Except的实现是：Set<T> set = new Set<T>(comparer); foreach (T element in second) set.Add(element); foreach (T element in first) if (set.Add(element)) yield return element; -- 因此，只要set.Add在时间和空间上都是O(1)，而且序列的大小为m和n，则该算法的时间复杂度为O(m+n)，空间复杂度为O(n)。 - Eric Lippert

Answer 4

我不明白为什么还没有人提到 Enumerable.Intersect。这是一个相当高效和非常直观的函数，可以在这里使用。

- Rotsor

Answer 5

您可以将第一个列表中的每个元素插入到 HashSet<string> 中，然后测试第二个列表中的每个元素是否存在于该集合中。这样只会检查每个项目一次，并且插入和测试应该是 O(1) 的（除非您的数据集由于某种原因是病态的）。

- dlev

Answer 6

字符串已知，因此排序后的向量比哈希映射更快。使用字符串友好的哈希（例如FNV）对较小文件中的字符串进行哈希处理，并将它们放入一个

vector<pair<int, string> >

定义函数使其可以在哈希表上进行排序和比较，然后sort向量。

bool operator < (pair<int, string> const&, pair<int, string> const&) { ... }
bool operator < (pair<int, string> const&, int) { ... }
bool operator < (int, pair<int, string> const&) { ... }

现在从较大的文件中读取每个字符串，对其进行哈希并使用equal_range搜索向量。仅在哈希匹配的情况下比较完整的字符串。（注意：可能需要额外的魔法来通过哈希搜索，而不是使用虚拟的pair<int, string>。）

如果可以接受更长的输出延迟并且有足够的空间，则将两个文件加载到排序向量中，使用set_intersection查找匹配的哈希，并比较它们的完整字符串。我将把细节留给读者作为练习（:-)。请记住，两侧都可能存在哈希冲突。

- Mark