为什么分配使用NP.empty而不是O(1)

Question

>>> timeit.timeit(lambda: np.empty(100000000 ), number=10000)
0.2733485999999914
>>> timeit.timeit(lambda: np.empty(1000000000), number=10000)
0.8293009999999867

Answer 1

首先，我尝试在我的各种尺寸的机器上重现这种行为。以下是原始结果：

np.empty(10**1)   # 421 ns ± 23.7 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**2)   # 406 ns ± 1.44 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**3)   # 471 ns ± 5.8 ns per loop     (on 7 runs, 1000000 loops each)
np.empty(10**4)   # 616 ns ± 1.56 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**5)   # 620 ns ± 2.83 ns per loop    (on 7 runs, 1000000 loops each)
np.empty(10**6)   # 9.61 µs ± 34.2 ns per loop   (on 7 runs, 100000 loops each)
np.empty(10**7)   # 11.1 µs ± 17.6 ns per loop   (on 7 runs, 100000 loops each)
np.empty(10**8)   # 22.1 µs ± 173 ns per loop    (on 7 runs, 10000 loops each)
np.empty(10**9)   # 62.8 µs ± 220 ns per loop    (on 7 runs, 10000 loops each)
np.empty(10**10)  # => Memory Error

因此，您是对的：这不是O(1)（至少在我的Windows计算机和您的系统上）。请注意，不能在这么短的时间内（急切地）初始化这些值，因为这意味着RAM吞吐量超过127 Tb/s，而我的机器上显然没有这个数据。

对于np.empty，这意味着创建（分配）这个数组所用的时间为O(1)

./malloc.exe 10           # Average time:  41.815 ns (on 1 run, 1000000 loops each)
./malloc.exe 100          # Average time:  45.295 ns (on 1 run, 1000000 loops each)
./malloc.exe 1000         # Average time:  47.400 ns (on 1 run, 1000000 loops each)
./malloc.exe 10000        # Average time: 122.457 ns (on 1 run, 1000000 loops each)
./malloc.exe 100000       # Average time: 123.032 ns (on 1 run, 1000000 loops each)
./malloc.exe 1000000      # Average time:   8.351 us (on 1 run, 1000000 loops each)
./malloc.exe 10000000     # Average time:   9.342 us (on 1 run, 100000 loops each)
./malloc.exe 100000000    # Average time:  18.972 us (on 1 run, 10000 loops each)
./malloc.exe 1000000000   # Average time:  64.527 us (on 1 run, 10000 loops each)
./malloc.exe 10000000000  # => Memory error

而且，大多数操作系统(OS)都有多个内存池。Linux、MacOS和Windows将虚拟内存分割成小页（通常为4KB)。由于在处理GB/TB的分配数据时，处理太小的页会带来很大的开销，因此这些操作系统还提供称为超级页或巨页的大页（通常为2MB到很少GB)。操作系统中所采用的路径可以根据分配的内存数量而改变，大多数操作系统都是为分配小块虚拟内存而不是大块虚拟内存而进行优化的。

请注意，用于管理系统内存的数据结构的大小通常受RAM大小的限制，而RAM在运行时通常是恒定的。此外，在给定的操作系统中用于管理内存碎片的算法的复杂性可能在理论上O(1)（或接近于此）。因此，有些人认为分配/释放数据是在恒定时间内完成的。但这是有争议的，因为人们应该考虑实际结果，而不仅仅是理论上的渐近界限。

有关更多信息，您可以查看以下帖子：

null