作为哈佛大学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 …