是来自缓存/内存访问的这两个O(n^2)算法之间的实际性能差异

Question

我写了两种方法来对数字进行排序，它们具有相同时间的复杂性：o（n^2），但实际运行时间是3倍（第二种方法使用

的时间是第一个时间的3倍。

我的猜测是差异来自内存层次结构（寄存器/缓存/内存的计数完全不同），是否正确？

是正确的吗？

要具体：第一个方法将一个列表元素与一个变量进行比较，并在它们之间分配值，第二种方法比较了两个列表元素和它们之间的分配值。我猜这意味着第二种方法比第一方法更具缓存/内存获取。对吗？

当列表具有10000个元素时，循环计数和运行时间如下：

# TakeSmallestRecursivelyToSort   Loop Count: 50004999
# TakeSmallestRecursivelyToSort   Time: 7861.999988555908       ms
# CompareOneThenMoveUntilSort     Loop Count: 49995000
# CompareOneThenMoveUntilSort     Time: 17115.999937057495      ms

这是代码：

# first method
def TakeSmallestRecursivelyToSort(input_list: list) -> list:
    """In-place sorting, find smallest element and swap."""
    count = 0
    for i in range(len(input_list)):
        #s_index = Find_smallest(input_list[i:]) # s_index is relative to i
        if len(input_list[i:]) == 0:
            raise ValueError
        if len(input_list[i:]) == 1:
            break
        index = 0
        smallest = input_list[i:][0]
        for e_index, j in enumerate(input_list[i:]):
            count += 1
            if j < smallest:
                index = e_index
                smallest = j
        s_index = index
        input_list[i], input_list[s_index + i] = input_list[s_index + i], input_list[i]
    print('TakeSmallestRecursivelyToSort Count', count)
    return input_list

# second method
def CompareOneThenMoveUntilSort(input_list: list) -> list:
    count = 0
    for i in range(len(input_list)):
        for j in range(len(input_list) - i - 1):
            count += 1
            if input_list[j] > input_list[j+1]:
                input_list[j], input_list[j+1] = input_list[j+1], input_list[j]
    print('CompareOneThenMoveUntilSort Count', count)
    return input_list

Answer 1

您的第一个算法可能会对O（n^2）进行比较，但它仅能使O（n）交换。那些掉期花费最多。如果删除了第二个算法中的互换，则会发现它花费的时间大大减少：

def CompareOneThenMoveUntilSortNoSwap(input_list: list) -> list:
    for i in range(len(input_list)):
        for j in range(len(input_list) - i - 1):
            if input_list[j] > input_list[j+1]:
                pass

# 1000 randomised sequential integers, 100 repeats
TakeSmallestRecursivelyToSort:     4.625916245975532
CompareOneThenMoveUntilSort:       10.164166125934571
CompareOneThenMoveUntilSortNoSwap: 4.86395191506017

仅仅是因为两种算法在相同的非透明顺序中并不意味着它们会一样快。在比较同一订单类中的算法实现时，这些恒定成本仍然很重要。因此，尽管这两个实现将显示出与所花费的分类元素所花费的时间相同的指数曲线，但CompareOneThenMoveUntilSort实现将行较高的线绘制在较高的时间表图表中。

请注意，您通过在其中添加4个额外的O（n）循环，增加了TakeSmallestRecursivelyToSort实现中每个N循环的常数成本。每个inputlist[i:]切片都会创建一个新列表对象，并在从索引i开始的所有引用中复制到新列表。它可以是更快的：

def TakeSmallestRecursivelyToSortImproved(input_list: list) -> list:
    """In-place sorting, find smallest element and swap."""
    l = len(input_list)
    for i in range(l - 1):
        index = i
        smallest = input_list[i]
        for j, value in enumerate(input_list[i + 1:], i + 1):
            if value < smallest:
                smallest, index = value, j
        input_list[i], input_list[index] = input_list[index], input_list[i]
    return input_list

这个大约需要3秒。