为什么检查变量是否存在比复制应该是 O(1) vs O(n) 操作的数组花费更多时间？

Question

这些数字对我来说没有意义。为什么检查列表是否存在或检查列表的 len() 比 copy() 花费的时间更长？这是 O(1) 与 O(n) 操作。

Total time: 3.01392 s
File: all_combinations.py
Function: recurse at line 15

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    15                                               @profile
    16                                               def recurse(in_arr, result=[]):
    17                                                   nonlocal  count
    18                                           
    19   1048576     311204.0      0.3     10.3          if not in_arr:
    20    524288     141102.0      0.3      4.7              return
    21                                           
    22    524288     193554.0      0.4      6.4          in_arr = in_arr.copy() # Note: this adds a O(n) operation
    23                                           
    24   1572863     619102.0      0.4     20.5          for i in range(len(in_arr)):
    25   1048575     541166.0      0.5     18.0              next = result + [in_arr.pop(0)]
    26   1048575     854453.0      0.8     28.4              recurse(in_arr, next)
    27   1048575     353342.0      0.3     11.7              count += 1

Total time: 2.84882 s
File: all_combinations.py
Function: recurse at line 38

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
    38                                               @profile
    39                                               def recurse(result=[], index=0):
    40                                                   nonlocal count
    41                                                   nonlocal in_arr
    42                                           
    43                                                   # base
    44   1048576     374126.0      0.4     13.1          if index > len(in_arr):
    45                                                       return
    46                                           
    47                                                   # recur
    48   2097151     846711.0      0.4     29.7          for i in range(index, len(in_arr)):
    49   1048575     454619.0      0.4     16.0              next_result = result + [in_arr[i]]
    50   1048575     838434.0      0.8     29.4              recurse(next_result, i + 1)
    51   1048575     334930.0      0.3     11.8              count = count + 1

Answer 1

并不是说复制本身比你说的O(1)操作要长。

但请记住，您的基本情况运行比递归情况更常见。

Answer 2

我不确定你在问题中用“它”指的是什么。通用（“皇家”）“它” 不会需要更长的时间；您的实施需要更长的时间。在大多数语言实现中，len 是 O(1)，因为它是与对象中的任何更改一起维护的实例属性。这种存在实现速度较慢，因为它会重复而不是简单地遍历列表，尽管它仍然是 O(N).

为什么检查变量是否存在比复制应该是 O(1) vs O(n) 操作的数组花费更多时间？

Why is checking for a variables existence taking more time than copying an array which should be a O(1) vs O(n) operation?

python

algorithm

performance

big-o

profiling