D2009更快的CompareText实现方式

Question

D2009更快的CompareText实现方式

delphistringperformancedelphi-2009hashmap

3

我的程序中广泛使用哈希表数据结构。我正在使用Barry Kelly在Codegear论坛上发布的哈希表实现。该实现内部使用RTL的CompareText函数。通过分析，我意识到程序大量时间用于SysUtils CompareText函数。

我查看了Fastcode网站，发现了一些更快的CompareText实现。不幸的是，它们似乎不能用于D2009及其Unicode字符串。

那么问题来了：是否有类似的更快版本支持D2009字符串？当使用哈希表时（至少在我目前使用的实现中），CompareText函数被频繁调用，因此小的性能改进可能真的会有所不同。或者那里提供的实现也适用于Unicode字符串吗？

- Smasher

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Rob Kennedy · Accepted Answer

许多FastCode函数在Delphi 2009中可能会编译并且看起来工作得很好，但它们不适用于所有输入。那些使用汇编实现的函数会失败，因为它们假定字符只占一个字节。使用Delphi实现的函数会稍微好一点，但有时仍会返回不正确的结果，因为旧版的CompareText的“不区分大小写”的概念是基于ASCII的，而新版应该基于Unicode。对于哪些字符被认为除了大小写外相同的规则，在Unicode中与ASCII大不相同。

Andreas在下面的评论中说，Unicode CompareText仍然使用ASCII大小写比较规则，因此许多FastCode函数应该能正常工作。在使用它们之前，请检查它们是否做出任何字符大小的假设。我似乎记得一些FastCode函数已经被合并到Delphi RTL中。我不知道CompareText是否是其中之一。

如果您在哈希表中频繁调用CompareText，那么这表明您的哈希表工作得不太好。CompareText只有在您要查找的内容的哈希指定了非空桶时才会被调用。从那里开始，哈希表通常会使用线性搜索来在桶中找到正确的项目，并在该搜索期间为每个项目调用CompareText。我不知道您正在使用的哈希表是否是这样工作的。

您可以通过使用分布结果更均匀的不同哈希函数来解决此问题。如果您的桶已经填满，则可能需要更多的桶（然后确保哈希函数在该数量上仍然均匀分布）。

如果你正在使用基于 TBucketList 的哈希映射类，则桶存储方面有改进的余地。该类只在输入中使用输入来确定要使用的桶，而不计算整个输入的哈希值。如果该类还可以跟踪计算出字符串的完整哈希值，则线性搜索期间的比较速度可以大大加快。只需比较哈希值，并仅当哈希值完全匹配时才比较字符串。(对于支持的最大尺寸256个桶的桶列表，输入的仅一个字节就决定了桶的位置，其余字节将被忽略。)我之前在这里写过关于 TBucketList 的文章。