为什么 IPython `%timeit` 会为 O(n) 解决方案产生较慢的时间？

Question

我正在通过比较 interactivepython.org 提供的字谜算法来研究数量级。我正在使用 IPython 的 %timeit 魔法来测试这些功能。解决方法如下。第一种算法：

# Sort and Compare
def anagram_solution2(s1,s2):
    a_list1 = list(s1)
    a_list2 = list(s2)

    a_list1.sort()
    a_list2.sort()

    pos = 0
    matches = True

    while pos < len(s1) and matches:
        if a_list1[pos] == a_list2[pos]:
            pos = pos + 1
        else:
            matches = False
    return matches

第二个算法：

# Count and Compare
def anagram_solution4(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26

    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1

    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1

    j = 0
    still_ok = True
    while j < 26 and still_ok:
        if c1[j] == c2[j]:
            j = j + 1
        else:
            still_ok = False
    return still_ok

排序和比较 函数（解决方案 2）被声明为高阶，O(n^2) 或 O(nlogn) 解决方案。 count 和 compare 函数（解决方案 4）据说是一个 O(n) 解决方案，因此如果使用 %timeit 进行测试，我预计时间会更短。但是，我得到以下结果：

%timeit anagram_solution2('conversationalists', 'conservationalists')
# 100000 loops, best of 3: 13 µs per loop

%timeit anagram_solution4('conversationalists', 'conservationalists')
# 10000 loops, best of 3: 21 µs per loop

也许我遗漏了一些基本的东西，但为什么线性解决方案比 quadratic/log-linear 解决方案花费的时间更长？

编辑

为了完整起见，我添加了一张 common Big-O functions 的图表。在较低的 "x" 值处似乎存在对数衬里曲线和衬里曲线的交集。

Answer 1

请记住，O() 符号指的是仅整个时间方程的主导项。例如，O(n) 可能指的是一个需要 1000*n + 7000 秒的过程；竞争的 O(n^2) 过程可能是 0.5*n^2 + .10 秒。 N 必须非常大才能使 n^2 过程在更短的时间内达到运行。

在这种情况下，O(n) 算法经历了三个单独的 n 长度循环，并插入了一些操作。这会使 N 的小值变慢。我会去运行几个测试...

我试过用两个字母，然后是一份字母表，然后是 30 份：

length 2    O(n^2) 1.00135803223e-05    O(n) 1.50203704834e-05
length 26   O(n^2) 1.69277191162e-05    O(n) 2.59876251221e-05
length 780  O(n^2) 0.000540971755981    O(n) 0.00049901008606

在我的环境中，O(n) 算法可能要到 500 个字符才能赶上，但从那时起它将是更快的算法。

Answer 2

O[N] 和 O[N^2] 是关于缩放的，而不是关于绝对时间的。例如，O[N] 算法可能需要 10 秒获得 10 分，100 秒获得 100 分，1000 秒获得 1000 分，等等。

O[N^2] 算法可能需要 10 毫秒获得 10 个点，1 秒获得 100 个点，100 秒获得 1000 个点等。

注意这里 O[N^2] 算法在需要多少时钟时间方面比 O[N] 更快，但缩放比例不同。

O[N] 衡量时间如何随着 N 的增加而变化，而不是算法所花费的时间。

Answer 3

常量！

线性解可能类似于

t_linear = c0 + c1 * N

另一个可能是

t_square = d0 + d1 * N + d2 * N**2

其中 c 和 d 是常量。

让我们设置c0 = 100, c1 = 1; d0 = 1, d1 = 0 and d2 = 1

然后对于小 N，说 N = 4 我们得到 t_linear = 104 和 t_square = 17，即 t_linear > t_square

随着 N 的增加，t_square 接近然后超过 t_linear，即对于 N = 11，我们得到 t_linear = 111 和 t_square = 122，即 t_linear < t_square

我想如果达到缓存限制，现代 CPU 架构也可能会造成计时错误；可以操纵操作系统以识别基准并偏爱一个示例而不是另一个示例； ... 但常量是更可能的原因。

Answer 4

已经有 3 个不错的答案，但我认为这增加了一个稍微不同的视角。

一般来说，大符号实际上只说明低阶算法比高阶算法快 在某些时候。 Big O 本身完全没有提供关于该点何时的信息。它可以是 N=3 或 N=10^1000。

也就是说，对于实际的算法，它往往会在 N=100 万左右之前发生，并且通常在 N 超过 10,000 左右之前发生。在较小输入的情况下（N < 10 左右），通常情况下最简单的算法是最快的，不管 O 多大，只要算法是现实的，不像说 Bogosort.

打个比方，可以用不同的交通工具来驱动。对于增加出行距离，最有效的方式依次是：步行-自行车-汽车-火车-飞机。对于更小的距离，每一个开始时都比前一个差，但最终开始超越它。

这导致了另一个结论：更简单但 "slower" 算法拥有完整的存在权，并且如果您的数据大小在它们所在的段中，则可以选择 "faster" 算法更有效。 这是另一个问题，您无法预测您的数据将有多大，尤其是当它是一个软件库时。这就是为什么通常选择 "latest and greatest"，或者如果选择一个方法的权衡足够大，代码会在几种方法之间交替。

为什么 IPython `%timeit` 会为 O(n) 解决方案产生较慢的时间？

Why does IPython `%timeit` yield a slower time for an O(n) solution?

python

sorting

algorithm

big-o

ipython