我在程序中广泛使用哈希映射数据结构。我正在使用Barry Kelly的哈希映射实现,该实现在Codegear论坛上发布。该实现在内部使用RTL的CompareText函数。通过分析,我意识到SysUtils CompareText函数花费了很多时间。
我看了看
Fastcode site
并找到了一些CompareText的更快实现。不幸的是,它们似乎不适用于D2009及其unicode字符串。
现在是一个问题:是否有类似的更快版本支持D2009字符串?使用哈希映射时,CompareText函数似乎被调用了很多(至少在我当前使用的实现中),因此,很少的性能改进确实可以起到作用。还是在那里介绍的实现也适用于unicode字符串?
最佳答案
许多FastCode函数可能会编译,并且在Delphi 2009中似乎可以正常工作,但是它们并不适合所有输入。在汇编器中实现的那些将失败,因为它们假定每个字符仅一个字节。用Delphi实现的代码效果会好一些,但是有时它们仍会返回错误的结果,因为旧的CompareText
的“不区分大小写”概念是基于ASCII的,而新的CompareText
概念应该是基于Unicode的。区分大小写的字符被认为与ASCII的规则大不相同。
Andreas在下面的评论中说Unicode CompareText
仍然使用ASCII大小写比较规则,因此许多FastCode函数应该可以正常工作。只是在使用它们之前先仔细检查一下,以确保他们没有做任何字符大小的假设。我似乎还记得,某些FastCode函数已经合并到Delphi RTL中了。我不知道CompareText
是否是其中之一。
如果您在哈希表中经常调用CompareText
,则表明您的哈希表做得不好。 CompareText
仅在您要搜索的事物的哈希在哈希表中指定为非空存储桶时才被调用。从那里开始,哈希表通常会使用线性搜索来在存储桶中找到合适的项目,并且在该搜索过程中它将为每个项目调用TBucketList
。我不知道您使用的那是不是这样。
您可以通过使用其他哈希函数来解决此问题,该哈希函数将其结果更均匀地分布在可用存储桶中。如果您的存储桶已经被均匀填充,那么您可能需要更多的存储桶(然后确保哈希函数也仍然在该数字上均匀分布)。
如果您使用的哈希映射类基于TBucketList
,则存储分区中还有改进的空间。该类不计算整个输入的哈希值。它仅使用输入来确定要使用的存储桶。如果该类还将跟踪为字符串计算的完整哈希,那么线性搜索期间的比较可能会快得多。只需比较哈希值,并且仅在哈希值完全匹配时才比较字符串。 (对于256个存储桶的存储桶列表,支持的最大大小,只有输入的一个字节确定存储桶,其余字节将被忽略。)I've written about here before.