python - Python 中的 Anagram 搜索算法比较 [教程作业]

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

对于 300k 单词，字符串哈希运行时间为 0.75 秒，素数哈希运行时间为 1 秒。我一直在阅读此内容，但我无法确定我是否错过了任何内容或它运行速度变慢的原因。

就家庭作业而言，这已经完成，但我想了解为什么或我在这里缺少什么。

Answer 1

这里发生了很多因素:

• 排序平均情况为 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 编写的。
• 您在问题中没有说明您是如何进行计时的。例如，通过对整个程序而不是微基准进行计时，很容易出错。考虑到结果的接近性，我希望您犯了这样的错误，但这只是猜测。