Python中的字符串搜索算法比较[教程作业]

Question

我正在Python中使用defaultdict进行简单的算法排序，创建一个用作键的散列，然后只是通过字典，然后打印出超过一个单词值。

最初通过使用创建一个排序的字符串制作哈希开始：

def createHashFromFile(fileName): 
    with open(fileName) as fileObj: 
     for line in fileObj: 
      line = line.lower() 
      aHash = ("").join(sorted(line.strip())) 
      aSorter[aHash].append(line.strip()) 

但是，因为排序（）函数是O（n^2）都配备了由创造过黄金哈希的建议因式分解。我创建了一个已经映射所有的小写字母的黄金，然后做了解释：

def keyHash(word): 
    mulValue = 1 
    for letter in word: 
     letter = letter.lower() 
     mulValue = mulValue * primeDict[letter] 

    return mulValue 

在30万字，在0.75s字符串哈希运行，并在1秒的主要哈希奔跑。我一直在读这篇文章，但我无法确定我是否错过了这个或者它为什么运行速度较慢。

就作业而言，这已经完成，但我想了解我在这里失踪的原因或缺点。

Answer 1

有一大堆的因素会在这里的：

• sorted是O（n log n）的平均情况，而不是为O（n^2）。最糟糕的情况在真正的节目中几乎从不相关。
• 将素数相乘是一个聪明的诀窍，但虽然它是乘法运算中的O（n）代价，但将一个大数N乘以一个小因子将成本为O（log N），而不是O（1）你必须通过bignum的O（log N）数字）。这意味着主要技术也将是O（n log n），因为keyHash（s）将具有O（len（s））数字。
• n很小，所以实现细节将比复杂性更重要。
• sorted内置并用C语言编写。实现已经调整了很多年。您的主要乘法代码是用Python编写的。
• 你不会在你的问题中说你如何执行时间。例如，通过对整个程序进行计时而非微观基准，很容易弄错。鉴于结果的接近程度，我预计你会犯这样的错误，但这是一个猜测。