Python限制列表出现次数的最快方法

Question

我想知道为什么O(n(中的list.count()几乎和我的自定义方法一样快，有2个if和2个赋值。

基本方法应该在O(n * m)中，其中n是输入元素的长度，m是输出元素的长度。我的方法应该在O(n)中，其中n是输入元素的长度。

任何想法都将不胜感激。

from timeit import default_timer as timer
from typing import List
def run_test_timings(func, n_repeat, *args):
start = timer()
res = [func(*args) for _ in range(n_repeat)]
end = timer()
return end - start, res
def method_custom(elements: List[int], exclude_len: int = 2):
elements_out = list()
# 0(len(elements) * ~1)
prev_val, prev_val_counter = None, 0
for element in elements:
prev_val_counter = prev_val_counter + 1 if element == prev_val else 0
if prev_val_counter < exclude_len:
elements_out.append(element)
prev_val = element
return elements_out

def method_count(elements: List[int], exclude_len: int = 2):
elements_out = []
# O(len(elements) * len(elements_out))
for values in elements:
if elements_out.count(values) < exclude_len:
elements_out.append(values)
return elements_out

if __name__ == "__main__":
N_TESTS = 1_000_000
INPUT_ELEMENTS = sorted([1, 2, 3, 3, 3, 3, 4, 5, 8, 8])
print(f'n_tests : {N_TESTS}')
print('method_count timer : ', end='')
timer_1, res_1 = run_test_timings(method_count, N_TESTS, INPUT_ELEMENTS)
print(timer_1, res_1[0])
print('method_custom timer : ', end='')
timer_2, res_2 = run_test_timings(method_custom, N_TESTS, INPUT_ELEMENTS)
print(timer_2, res_2[0])

输出：

n_tests : 1000000
method_count timer : 1.665171445987653 [1, 2, 3, 3, 4, 5, 8, 8]
method_custom timer : 1.5837802449823357 [1, 2, 3, 3, 4, 5, 8, 8]

Answer 1

增加元素的数量比预期的巨大收益更明显。

这是完整的代码。

import random
from typing import List
from timeit import default_timer as timer

def run_test_timings(func, n_repeat, *args):
start = timer()
res = [func(*args) for _ in range(n_repeat)]
end = timer()
return end - start, res

def method_custom(elements: List[int], exclude_len: int = 2):
elements_out = list()
# 0(len(elements) * ~1)
prev_val, prev_val_counter = None, 0
for element in elements:
prev_val_counter = prev_val_counter + 1 if element == prev_val else 0
if prev_val_counter < exclude_len:
elements_out.append(element)
prev_val = element
return elements_out

def method_count(elements: List[int], exclude_len: int = 2):
elements_out = []
# O(len(elements) * len(elements_out))
for values in elements:
if elements_out.count(values) < exclude_len:
elements_out.append(values)
return elements_out

if __name__ == "__main__":
N_TESTS = 1_000
N_ELEMENTS = 1_000
print(f'N_TESTS    : {N_TESTS}')
print(f'N_ELEMENTS : {N_ELEMENTS}')
INPUT_ELEMENTS = sorted([random.randint(0, 100) for _ in range(N_ELEMENTS)])
print('method_count timer : ', end='')
timer_1, res_1 = run_test_timings(method_count, N_TESTS, INPUT_ELEMENTS)
print(timer_1)  # , res_1[0])
print('method_custom timer : ', end='')
timer_2, res_2 = run_test_timings(method_custom, N_TESTS, INPUT_ELEMENTS)
print(timer_2)  # , res_2[0])