在一个大的List上测试大量字符串的最有效方法

本文关键字：测试 字符串 方法 有效 一个 List string | 更新日期: 2023-09-27 18:01:41

我看过许多其他类似的问题，但是给出的方法对于我想要完成的任务来说似乎太慢了，或者正在测试部分匹配，这是我不需要的，应该更慢。

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

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

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

这是我的问题

在不需要部分匹配的情况下，将一个大字符串列表单独与另一个更大的字符串列表进行比较，有没有更有效的方法?

在一个大的List<string>上测试大量字符串的最有效方法

不使用List<string>，使用HashSet<string>。它有O(1)次查找而不是像列表那样有O(n)次查找。如果你做了这个改变，你应该会看到数量级的加速。

使用HashSet.Contains()而不是LINQ的.Any()扩展方法可能会给你带来更好的性能。

首先，我认为你的逻辑是完全错误的。将委托传递给Contains到Any方法将进行部分字符串匹配，并且您已明确声明只需要精确匹配。

把这个放在一边，你的性能问题是由于列表数据结构的性质;它的设计不是为了通过"Any"有效地搜索。

问题是"Any"只是简单地进行线性搜索，从列表的开头开始搜索，直到找到匹配项。如果列表有100K个条目，那么每次"miss"将进行100K个字符串比较，每次"hit"将平均进行50K个字符串比较。

可怕的

。

你应该做的是将List转换为字符串的HashSet。该集合占用的内存稍微多一些，但是非常快。

另一种可能的优化是对其中一个列表进行排序——这是一个O(nlgn)的操作——然后对排序后的列表进行二叉搜索，这是一个O(lgn)的操作。

第三种可能的优化是对两个列表进行排序，然后编写一个排序列表比较器。显然，排序列表比较器要比未排序列表比较器快得多。您保留每个列表的索引，并且只推进指向"较小"项的索引。也就是说，如果列表是

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

然后从指向A和B的索引开始。A比较小，所以你把第一个索引推进到B。现在它们是一样的;你找到匹配了。把它们都推进。第一个指标是"C"，第二个指标是"D"。

更一般地说，我认为你对问题的描述太低了。我觉得你应该问洞的时候问的是钻头的问题。也许钻一开始就不是合适的工具。你能告诉我们为什么要匹配两个大的字符串列表吗?也许有一个更简单的方法来做你想做的事。

使用Union和Except运算符来获得两个列表之间的异同

联盟: http://msdn.microsoft.com/en-us/library/bb341731.aspx

除了:

http://msdn.microsoft.com/en-us/library/system.linq.enumerable.except.aspx

每个函数返回一个包含结果数据的列表。

我不明白为什么没有人提到Enumerable.Intersect。这是一个非常有效和简单的函数。

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

字符串是预先知道的，因此排序向量将比散列映射更快。使用字符串友好的散列(如FNV)对较小文件中的字符串进行散列，并将它们放入

中。
vector<pair<int, string> >

定义函数使其在哈希上可排序和可比较，然后sort vector 

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查找匹配的哈希并比较它们的完整字符串可能会更快。我将把细节留给读者作为练习(:)。请记住，两边可能存在哈希冲突

相关文章：