python - 排序如何比线性(低常数)更快？

Question

我将 python 3 中一些内置排序函数的性能与我知道它们性能的一些算法进行了比较，我看到了一些意想不到的结果。我想澄清这些问题。

我使用“perfplot”库来比较可视化算法的复杂性。

import numpy as np
import perfplot

# algorithms:


def sort(x):
    np.sort(x)
    return 0


def sort_c(x):
    np.sort_complex(x)
    np.sort_complex(x)
    return 0


def builtin(x):
    sorted(x)
    return 0


def c_linear_inplace(x):
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            x[i] = x[i] + x[i + 1]
            x[i + 1] = x[i] - x[i + 1]
            x[i] = x[i] - x[i + 1]
    return 0


def c_linear_outplace(x):
    a = x.copy()
    for i in range(len(x) - 1):
        if x[i] > x[i + 1]:
            a[i] = x[i + 1]
            a[i + 1] = x[i]
    x = a.copy()
    return 0

def c_nlogn(x):
    logn = int(np.ceil(np.log2(len(x))))
    for i in range(len(x)-1):
        for j in range(logn):
            x[i] = 0
    return 0

#comprasion:
perfplot.show(
    setup=np.random.rand,  # function to generate input for kernel by n
    kernels=[
        sort,
        sort_c,
        builtin,
        c_linear_inplace,
        c_linear_outplace,
        c_nlogn,
    ],
    labels=["sort", "sort_c", "builtin", "check: linear inplace", "check: linear not in place", "check: nlogn"],
    n_range=[2 ** k for k in range(15)],  # list of sizes of inputs, i"setup" function will be called with those values
    xlabel="len(a)",
)

我希望所有排序函数都接近 nlogn() 函数或至少比线性函数效率低，我希望“c_linear_inplace”比“c_linear_outplace”更快。但所有内置排序函数都比线性函数快得多，“c_linear_outplace”函数比“c_linear_inplace”函数慢。

编辑:在我看来，这些是具有常量的函数的复杂性:
sort, sort_c, builtin : cnlog₂(n) for c>=1
检查:线性就地:6n
检查:线性不到位:7n
检查:nlogn : 2n + 3nlog₂n

我将任何 for 循环计算为 2*(迭代次数)用于检查和递增。和任何“如果”作为 O(1) 和任何赋值 (=) 作为 O(1)奇怪的是，即使占用更多内存的“check: linear not in place”的性能也比“check: linear inplace”好得多，但仍然比 numpy 的任何类型都差

Answer 1

您想在“对数-对数”图上显示您的结果。渐近/大 O 表示法通过忽略低阶因子来近似运行时间，这会对实际运行时间产生重大影响，因此您会看到差异。

如果您绘制对数-对数图，您应该会得到近似直线的出现，这些直线的高度被这些低阶常量偏移。另请注意，从单个元素开始往往会突出调用函数的开销，而不是任何渐近性能。

例如，这是我在运行时得到的结果:

    n_range=[2 ** k for k in range(10, 17)],
    xlabel="len(a)", logx=True, logy=True,

现在更明显的是，高度差异只是性能差异