Dre*_*rew 6 c algorithm performance hashtable cs50
作为哈佛大学CS50课程的一项任务,学生的任务是创建一个拼写检查程序.任务的主要目标是速度 - 纯粹的速度 - 我已经达到了我打败员工实施的程度,但我觉得我可以做得更好,并且正在寻找正确方向的推动力.
这是我的伪代码:
// read the dictionary word list
Read entire dictionary in one fread into memory
rawmemchr through and pick out the words
send each word through the hash function
create chain links for any index where collisions occur
// accept the incoming test words
Run the test word through the hash function
compare to the existing table / linked list
return the result of the comparison
使用150K字的字典,输入文本高达6MB,我能够准确地拼写检查大约半秒钟.
但是,当我查看来自输入文本的单词时,很明显这些单词的大部分是常见的(如"the","and","for"),以及大多数拼写错误的单词也会多次检查.
我的直觉说我应该能够"缓存""好点击"和"糟糕点击",这样我就不会一遍又一遍地为表格查找扫描相同的单词.即使当前结果非常接近O(1),我觉得我应该能够通过重新评估我的方法来减少几微秒的时间.
例如,在我加载字典后,文本输入可能只有8MB,但是:"误导".因此,我不想反复哈希/检查相同的单词(以计算费用),我想了解是否有一种方法可以编程方式丢弃已经被散列和拒绝的单词,但是以一种比哈希/检查本身.(我正在使用MurmurHash3,fwiw).
我意识到理论性能改进将局限于输入文本很长的情况,并且存在大量重复拼写错误.基于我评估的一些输入文本,以下是一些结果:
Unique Misspellings: 6960
Total Misspellings: 17845
Words in dictionary: 143091
Words in input text: 1150970
Total Time: 0.56 seconds
Unique Misspellings: 8348
Total Misspellings: 45691
Words in dictionary: 143091
Words in input text: 904612
Total Time: 0.83 seconds
在第二个示例运行中,您可以看到我必须为每个拼写错误的单词返回哈希表大约5.5次!这对我来说似乎很难解决,我觉得必须有一种更有效的方法来解决这种情况,因为我的程序的大部分时间都花在了哈希函数上.
我可以实现Posix线程(这在8核系统上运行)来改善程序的时间,但我更感兴趣的是改进我的方法和思考过程.
对不起,这是漫长的啰嗦,但这是我的第一个Stack Overflow帖子,我正在努力做到彻底.我在发布之前进行了搜索,但大多数其他"拼写检查"帖子与"如何"而不是"改进"相关.我很感激能够让我指出正确方向的建议.
这是一个很好解决的问题.;-)你应该研究一个名为trie的数据结构.trie是由单个字符构成的树,因此路径代表信息.每个节点都包含可以合法添加到当前前缀的字母.当字母是有效字时,也会记录.
四个字:
root-> [a]-> [a]-> [r]-> [d]-> [v]-> [a]-> [r]-> [k*]->[s*]
[b]
\> [a]-> [c]-> [i*]
[u]-> [s*]
这将代表"aardvark","aardvarks","abaci"和"abacus".节点是垂直连续的,因此第二个字母[ab]是一个节点,第五个字母[i*u]是一个节点.
逐个字符遍历特里字符,并在您触及空格时检查有效字.如果你不能用你所拥有的角色进行遍历,那么这就是一个坏词.如果你在击中太空时找不到有效的东西,这是一个坏词.
这是O(n)处理(n =字长),它非常非常快.构建trie将占用大量内存,但你不关心我的想法.
在你的两个试验中,值得注意的是大多数单词拼写正确.因此,您应该专注于优化词典中单词的查找.
例如,在您的第一次试用中,只有1.5%的单词拼写错误.假设平均需要两倍的时间来查找不在字典中的单词(因为需要检查存储桶中的每个单词).即使你把它减少到0(理论最小值:)),你的程序速度也会提高不到3%.
常见的哈希表优化是将您找到的密钥移动到存储桶链的开头(如果尚未存在).这将倾向于减少为常用单词检查的散列条目的数量.这不是一个巨大的加速,但是在某些键比其他键更常查找的情况下,它肯定会被注意到.
通过减少散列表占用来减少链长可能会有所帮助,但代价是更多的内存.
另一种可能性,因为你不打算在构建字典后修改字典,就是将每个存储桶链存储在连续的内存中,而不是指针.这不仅可以减少内存消耗,还可以提高缓存性能,因为大多数单词都很短,大多数存储区都适合单个缓存行.
由于单词往往很短,您可能能够找到优化比较的方法.strcmp()经过优化,但通常针对较大的弦进行优化.如果您被允许使用它,SSE4.2 PCMPESTRI操作码非常强大(但要弄清楚它的作用以及如何使用它来解决您的问题可能是一个巨大的浪费时间).更简单地说,您应该能够同时比较四个八字节前缀和256位比较操作(您甚至可以使用512位操作),因此通过巧妙的数据排列,您可能能够做到整个桶并行比较.
这并不是说哈希表必然是这个问题的最佳数据结构.但请记住,在单个缓存行中可以执行的操作越多,程序运行的速度就越快.即使链接列表密集型数据结构在纸面上看起来很好,它们也可能不是最理想的.
在考虑了这个问题几天并实际编写了一些代码后,我得出的结论是,对于一个真实世界的拼写检查器来说,优化成功的哈希表查找速度可能是不正确的.确实,正在查找的文本中的大多数单词通常都是正确拼写的 - 虽然这取决于拼写检查用户 - 但是试图建议正确拼写的算法可能会进行大量不成功的查找,因为它会循环可能的拼写错误.我知道这可能超出了这个问题的范围,但它确实对优化产生了影响,因为你最终得到了两种截然不同的策略.
如果您试图快速拒绝,则需要许多可能为空的存储桶链,或Bloom过滤器或其道德等效物,因此您可以拒绝第一次探测时的大多数错误.
例如,如果你有一个好的哈希算法产生比你需要的更多的位 - 你几乎肯定会这样做,因为拼写检查字典不是那么大 - 那么你可以在哈希中使用一些其他未使用的位来获得二级哈希.如果没有实现整个Bloom过滤器的麻烦,您可以在每个桶标头中添加一个32位掩码,表示存储在该存储桶中的值中五个二级散列位的可能值.结合稀疏表 - 我使用30%的占用率进行实验,这不是那么稀疏 - 你应该能够拒绝80-90%的查找失败,而不会超出桶标题.
另一方面,如果您正在尝试优化以获得成功,那么可能会发现较大的存储桶更好,因为它减少了存储区标头的数量,从而提高了缓存使用率.只要整个存储桶适合缓存行,多次比较的速度就会很高,以至于您不会注意到差异.(并且因为单词往往很短,所以期望五或六个适合64字节的高速缓存行是合理的.)
无论如何,在没有太多工作的情况下,我设法在70毫秒的CPU中进行了一百万次查找.多处理可以大大加快经过的时间,特别是因为哈希表是不可变的,所以不需要锁定.
我想从中得出的道德:
为了优化:
你需要了解你的数据
您需要了解您的预期使用模式
您需要根据上述内容调整算法
你需要做很多实验.