Python字谜搜索算法比较[教程作业]

Question

我使用defaultdict在Python中做了一个简单的排序算法，创建一个散列作为键，然后遍历字典，打印出任何超过一个值的内容。你知道吗

最初是通过使用以下命令创建排序字符串来创建哈希：

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())  

但是，由于sorted（）函数是O（n^2），因此建议通过素因子分解创建哈希。我创建了一个字典，将所有小写字母映射到素数，然后执行以下操作：

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

    return mulValue

在30万字上，字符串散列在0.75秒内运行，主散列在1秒内运行。我一直在阅读这篇文章，但我无法确定是否遗漏了任何内容，也无法确定它为什么运行较慢。你知道吗

就家庭作业而言，这已经完成了，但是我想知道为什么或者我遗漏了什么。你知道吗

Answer 1

这里有很多因素：

• sorted是O（n logn）的平均情况，而不是O（n^2）。这种最坏的情况在实际的程序中几乎不相关。你知道吗
• 将素数相乘是一个聪明的技巧，但是当它在乘法中是O（n）代价时，将一个大的数n乘以一个小的因子将是O（logn）而不是O（1）（因为你必须通过bignum的O（logn）数字）。这意味着基本技术也将是O（nlogn），因为keyHash（s）将有O（len（s））个数字。你知道吗
• n很小，所以实现细节比复杂性更重要。你知道吗
• sorted是内置的，用C语言编写。这个实现经过了多年的优化。素数乘法代码是用Python编写的。你知道吗
• 在你的问题中你没有说你是如何完成计时的。这很容易出错，例如，对整个程序进行计时，而不是对一个微观基准进行计时。考虑到结果的接近性，我认为你犯了这样的错误，但这只是猜测。你知道吗