为什么嵌套循环比单循环运行得更快？

Question

我正在比较不同方法的运行时间，以解决一个问题，该问题需要返回两个数字的索引（作为列表），这些数字加起来等于目标数字，并且对获得的结果感到困惑。方法 -1 的运行时间约为 344 毫秒，而方法 - 2 的运行时间为 682 毫秒。我假装嵌套循环远不如单运行循环。这个观察结果是列表的结果，其中两个数字位于列表的起点附近吗？即使是这样，嵌套循环为什么高效？

# Approach - 1
for index1, num1 in enumerate(nums):           
        num2 = target - num1
        if num2 in nums[index1 + 1:]:
            if nums.index(num2) != index1:
                return [index1, nums.index(num2)]
            else:
                return [index1, nums[index1 + 1:].index(num2) + index1 + 1]


# Approach - 2
for i in range(len(nums)):
        var = target - nums[i]
        a = nums.pop(i)
        try:
            index2 = nums.index(var) + 1
        except:
            nums.insert(i, a)
            continue
        return [i, index2]

Answer 1

不断地从列表中插入和删除（弹出）将是昂贵的。如果您正在寻找一种有效的方法来实现这一点（这是经典的 2-Sum 问题），那么：

def sumsum(nums, target):
    info = {}
    for i, v in enumerate(nums):
        r = info.get(target - v)
        if r is not None:
            return [r, i]
        info[v] = i

编辑：为此答案添加了完整的测试用例以及原始问题的两种方法

from timeit import timeit
from random import randint, shuffle

# this is the most efficient 2-sum algorithm that I can think of
def func1(nums, target):
    info = {}
    for i, v in enumerate(nums):
        r = info.get(target - v)
        if r is not None:
            return [r, i]
        info[v] = i


# this is approach 1
def func2(nums, target):
    for index1, num1 in enumerate(nums):
        num2 = target - num1
        if num2 in nums[index1 + 1 :]:
            if nums.index(num2) != index1:
                return [index1, nums.index(num2)]
            else:
                return [index1, nums[index1 + 1 :].index(num2) + index1 + 1]

# this is approach 2
def func3(nums, target):
    for i in range(len(nums)):
        var = target - nums[i]
        a = nums.pop(i)
        try:
            index2 = nums.index(var) + 1
        except:
            nums.insert(i, a)
            continue
        return [i, index2]

# the performance of each function will vary depending on where the 2 key values are in the input list
# therefore, I build a list starting with two values which, when summed, equal a target
# I then pseudo-randomly add numbers to the list ensuring that the two key values are not repeated
# then pseudo-randomly shuffle the 100 element list
N = 5
totals = [0.] * 3
funcs = func1, func2, func3

# run N tests accumulating the durations for each function
for _ in range(N):
    nums = [2, 3]
    target = sum(nums)

    nums += [randint(10, 1000) for _ in range(98)]

    shuffle(nums)

    for i, func in enumerate(funcs):
        totals[i] += timeit(lambda: func(nums, target), number=5_000)

# show the averages
for f, t in zip(funcs, totals):
    print(f.__name__, f"{t / N:.4f}")

输出：

func1 0.0350
func2 0.1899
func3 0.6292

因此 func1 优于 func2（方法 1）大约 5 倍 func2（方法 1）优于 func3（方法 2）约 3 倍

**Platform:**

Python 3.12.1
macOS 14.2.1
Apple Silicon M2

Answer 2

弹出、插入、切片和搜索（无论是使用

in

还是

index

）平均都需要线性时间。但搜索是迄今为止最慢的，因为这涉及比较值，这相对昂贵。方法 1 平均搜索 n/2 个值（其中 n=len(nums)），而方法 2 总是搜索 n-1 个值。因此，方法 2 花费大约两倍的时间也就不足为奇了。

您可以轻松地使方法 2 也仅搜索 n/2 个值，通过使用

nums.index(var, i) + 1

而不是

nums.index(var) + 1

..然后它应该比方法 1 更快，因为 pop+insert 比切片更快。 （当然你甚至不需要弹出/插入，只需使用

nums.index(var, i + 1)

即可。）