Crawler url队列还是哈希列表？

Question

我正在重写我之前写过的Delphi 6站点映射器应用程序的spidering/crawler部分.该应用程序蜘蛛网站.

我需要管理两个方面:

以前这些分别是使用TList和StringList完成的.显然,这些性能在具有数千个链接的站点上降级.

我的问题是,应该为这些队列/列表使用什么来确保最佳性能？我对哈希的经验很少.

Answer 1

恕我直言的哈希将是这类名单的最佳候选人.

在Delphi 6中,您可以使用单元中THashedStringList可用的类IniFiles.它会比a快TStringList.

请注意,如果您使用已排序的TStringList,您可以使用更快的二进制搜索,足够快到达您的目的.

有关更完整的内容,您可以查看这些OpenSource库:

TSynBigTableMetaData用于存储与元数据字段关联的任何数量的数据(在您的情况下为HTML页面) - 您有元数据字段的索引,因此添加和检索将很快;
使用散列名称的动态数组可以在带有TDynArrayHashed的 Delphi 6中使用.

更新:

只是一个排序URI的技巧,如果你使用一个有序的TStringList:你可以更好地使用一个向后排序函数,即比较从字符串末尾而不是开头开始的URI文本,因为在URI中,更改是在后缀而不是比在前缀.您将更快地进行排序/二进制搜索.

Answer 2

Trie 非常适合存储大型（唯一）文本块并保持高速搜索。不久前，我为 Pascal Gamer 写了一篇关于它们的快速而肮脏的文章： http://www.pascalgamer.com/issue_details.php ?i=1 可能值得一读。

基本概念是创建一个记录（类，无论什么），其中包含字母或符号及其所有链接的字母和符号作为子项。这些子节点按顺序存储，因此可以使用快速二分搜索来查找下一个节点。当您到达输入的末尾时，您可以判断您是否处于单词结尾或有效位置。

Trie 的好处是你可以毫无问题地进行部分匹配、反向查找、跳过搜索等。缺点是；您不能轻易拥有重复的条目，它们在较小的数据集上占用更多空间，并且根据您的实现情况，敏感的切换可能是“有趣的”。

日复一日地在数百万条记录上使用这个概念，没有任何问题，并且可以高速保留。