c# - 检查子字符串的有效方法 C#

Question

我有一堆包含 30 万行的 txt 文件。每行都有一个 URL。例如。 http://www.ieee.org/conferences_events/conferences/conferencedetails/index.html?Conf_ID=30718

在一些 string[] 数组中我有一个网站列表

amazon.com
google.com
ieee.org
...

我需要检查该 URL 是否包含网站之一并更新与特定网站相对应的一些计数器？

目前我正在使用contains 方法，但速度很慢。数组中有 ~900 条记录，所以最坏的情况是 900*300K(对于 1 个文件)。我相信 indexOf 也会很慢。

有人可以帮助我更快地接近吗？提前谢谢你

Answer 1

好的解决方案将利用哈希。我的方法如下

1. 散列所有已知主机(您提到的 string[] 集合)
2. 将散列存储在 List<int> 中(hashes.Add("www.ieee.com".GetHashCode() )
3. 对列表进行排序 ( hashes.Sort() )
4. 查找网址时:
   1. 从 url 中解析主机名(从 ieee.com 中获取 http://www.ieee.com/...)。您可以使用 new Uri("http://www.ieee.com/...").Host得到www.ieee.com .
   2. 对其进行预处理以始终期望相同的情况。使用小写字母(如果你有 http://www.IEee.COM/ 取 www.ieee.com )
   3. 散列解析的主机名，并在 hashes 中查找它列表。使用 BinarySearch 查找哈希的方法。
   4. 如果散列存在，那么您的列表中就有这个主机

更快、内存效率更高的方法是使用 Bloom filters .我建议您在维基百科上阅读它们，甚至还有布隆过滤器的 C# 实现 on CodePlex .当然，您需要考虑到布隆过滤器允许误报结果(它可以告诉您某个值在集合中，即使它不在集合中)，因此它仅用于优化。它不会告诉您某些东西不在集合中，如果它真的不在集合中的话。

---

使用 Dictionary<TKey, TValue>也是一种选择，但如果您只需要计算出现的次数，那么自己维护哈希集合会更有效。