Kin*_*Kin 18 c# linq string performance
我已经看了很多其他类似的问题,但是给出的方法对于我想要完成的事情来说似乎太慢了,或者正在测试部分匹配,我不需要并且应该更慢.
我有两个填充字符串的大文件,我需要检查一个列表中的每个字符串,看它是否匹配第二个列表中的任何字符串.我不需要检查部分匹配,所有内容都应该正确转义.
第二个列表(要删除的字符串)包含160,000个字符串.我已将其加载到a中List<String>,然后读取较大文件的每一行并使用它进行测试List<String>.Any(line.contains).
即使只有第一个列表的一小部分(40k字符串),这需要很长时间,可能在我的快速开发计算机上超过20分钟.
这是我的问题
当不需要部分匹配时,是否有更多/什么是将大型字符串列表与另一个更大的字符串列表进行比较的最有效方法.
rec*_*ive 50
而不是使用List<string>,使用HashSet<string>.它具有O(1)查找而不是像列表那样的O(n).如果进行此更改,您应该会看到数量级的加速.
它也可以为您提供稍微好一点的性能HashSet.Contains(),而不是LINQ的.Any()扩展方法.
Eri*_*ert 26
首先,我认为你的逻辑是完全错误的.将委托传递给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"更小",所以提前......
但更普遍的是,我认为你的问题太低了.当你问一个关于洞的问题时,我觉得你问的是关于演习的问题.也许钻头首先不是正确的工具.你能告诉我们为什么你要匹配两个大字符串列表吗？也许有一种更简单的方法来做你想要的.