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

在 30 万个单词上，字符串哈希在 0.75 秒内运行，素数哈希在 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.
你没有在你的问题中说明你是如何进行计时的。这很容易出错，例如，对整个程序而不是微基准进行计时。考虑到结果的接近程度，我认为你犯了这样的错误，但这是一个猜测。

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

Anagram Search Algorithm Comparison in Python [Tutorial Homework]

python

algorithm

hash

primes