python - 比较两种获取子列表长度的方法

Question

我有两种获取子列表长度的实现。存在显着的性能差异。我想知道为什么。

import time

# list with 100000 integers
with open('IntegerArray.txt') as f:
    input_list = [int(x) for x in f.read().splitlines()]

i = 50000

start_1 = time.time()
len(input_list[i:])
print("--- %s seconds --- " % (time.time() - start_1))

start_2 = time.time()
len(input_list) -i
print("--- %s seconds --- " % (time.time() - start_2))

输出:

--- 0.000550985336304 seconds ---
--- 2.14576721191e-06 seconds ---

这是为什么？这是否意味着我必须避免使用第一种方法而始终使用第二种方法？

Answer 1

len(input_list[i:])

这会复制列表从位置 i 到末尾，O(n) 操作(其中 n 是 中的元素数切片)。然后它询问它的长度是多少:O(1)。所以 O(n) 总体而言。

len(input_list) -i

这只是要求长度 (O(1)) 然后减去(也是 O(1))。所以 O(1) 总体而言。

参见:https://wiki.python.org/moin/TimeComplexity