时间复杂度较高，但速度更快

Question

我有两个函数来检查两个单词word1和word2是否是字谜(注:如果您可以重新排列其中一个单词的字母以得到另一个单词，则两个单词被称为字谜)。

def is_anagram(word1, wrod2):
    histogram = {}
    for char in word1:
        histogram[char] = histogram.get(char, 0) + 1
    # Trying to exhaust all the letters in a histogram by second word
    for char in word2:
        histogram[char] = histogram.get(char, 0) - 1
    for vals in histogram.values():
        if vals != 0: return False
    return True

显然，在上面的函数中，3循环正在运行，因此它的总体复杂度为O(n)。

以下是第二个实现：

def is_anagram2(word1, word2):
    sorted_word1 = ''.join(sorted(word1))
    sorted_word2 = ''.join(sorted(word2))
    return sorted_word1 == sorted_word2

sorted函数的复杂度为nlogn，因此该函数的复杂度应为O(nlogn)。

但是，如果您度量这两个函数的执行时间(例如，通过ipython中的timeit命令)，则会发现is_anagram2函数更快。

请解释为什么..。

Answer 1

这是因为第二个函数将所有重要的工作留给Python解释器的底层本机代码(即sorted函数)。第一个函数是用Python代码执行所有操作，将任务分解为更小的操作。

Python (至少是官方实现的CPython)是用C实现的，C代码比Python代码快一个数量级。这是因为C被优化并编译成直接在CPU上运行的机器代码。另一方面，Python代码运行在用C( Python解释器)实现的虚拟机之上:它必须被解析，转换为Python字节码，然后每个字节码操作都需要由解释器执行，这要慢得多。

这是一个常见的问题，在为Python的性能进行优化时会出现无数次。有时候，让本机代码来完成这项工作更好，因为Python字节码的开销超过了它的优势。这也是为什么像NumPy这样的库非常流行的原因:它们在C中实现了大部分功能，并且只通过Python模块公开高级API，因此如果正确使用而不是普通的Python代码，它们可以非常有效地执行某些任务。