为什么分配使用 np.empty 而不是 O(1)
Why is allocation using np.empty not O(1)
官方是这么说的numpydocs
Return a new array of given shape and type, without initializing entries.
for np.empty，这意味着创建（分配）这个数组所花费的时间是 O(1)，但是 timeit 中的一些简单测试表明情况并非如此：
>>> timeit.timeit(lambda: np.empty(100000000 ), number=10000)
0.2733485999999914
>>> timeit.timeit(lambda: np.empty(1000000000), number=10000)
0.8293009999999867
作为附带问题，未触及的 np.empty 数组中存在哪些值？它们都是非常小的值，但我希望它们只是该地址内存中存在的任何值。 （示例数组：np.empty(2) = array([-6.42940774e-036, 2.07409447e-117])。这些看起来与存储在内存中的内容完全不同）
首先，我尝试在我的各种尺寸的机器上重现这种行为。以下是原始结果：
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，而我的机器上显然没有。
for np.empty, which would imply that the time taken to create (allocate) this array would be O(1)
分配在 O(1) 中完成的假设并不完全正确。为了检查这一点，我构建了一个简单的 C 程序，执行一个简单的 malloc+free 循环并测量了时间。以下是原始结果：
./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
如您所见，结果与 Numpy 的结果匹配（除了小的结果，这是由于在 CPython 中调用 Python 函数的开销）。因此，问题不是来自 Numpy，而是标准 libc 中的分配算法或 OS 本身。
As a side question, what are the values present in an untouched np.empty array?
是未初始化的数据。实际上，它通常是零初始化的（但并非总是如此），因为主流平台出于安全原因清理分配的内存（以便密码等关键数据在先前存储在另一个进程的内存中时不会泄漏）。 你不应该依赖这个。
malloc 时间的更深入解释：
如您所见，100K 项和 1M 项的分配之间存在差距。这可以通过使用快速用户-space分配器（称为sbrk on Unix and Linux systems): when data are small, the libc of most mainstream platforms does not directly request memory to the operating system. It rather use a fast pre-allocated local memory-pool. Actually, on most mainstream platforms, multiple pool of different sizes are pre-allocated and the libc choose the "right one" depending on the allocated size, hence the timing variation for small data size. Note that this process is done to improve the allocation speed while taking into account memory fragmentation）来解释。这个策略比内核调用[= =75=]（如 mmap）非常昂贵（在我的机器上至少需要几微秒）。
此外，大多数操作系统 (OS) 都有看起来像多个内存池的东西。 Linux、MacOS 和 Windows 将 虚拟内存 分成小的 页 （通常为 4KB） .由于在太小的页面上工作会在处理 GB/TB 分配的数据时引入显着的开销，因此这些 OS 还提供称为超级页面或大页面的大页面（通常为 2MB 到几 GB）。在 OS 中采用的路径可以根据分配的内存量进行更改，并且大多数 OS 都针对分配小块 虚拟内存而不是大块进行了优化。
请注意，用于管理系统内存的数据结构的大小通常受 RAM 大小的限制，而 RAM 在运行时通常是恒定的。此外，在给定的 OS 中用于管理内存碎片的算法的复杂性 可能 是 理论上 O(1) （或接近）。因此，有些人认为 allocating/freeing 数据是在常数时间内完成的。但这有争议，因为人们应该考虑 实际 结果而不仅仅是 理论 渐近边界 .
更多信息您可以查看以下帖子：
- Time complexity of memory allocation
- Why does malloc initialize the values to 0 in gcc?
- Can an
O(n) algorithm ever exceed O(n^2) in terms of computation time?
官方是这么说的numpydocs
Return a new array of given shape and type, without initializing entries.
for np.empty，这意味着创建（分配）这个数组所花费的时间是 O(1)，但是 timeit 中的一些简单测试表明情况并非如此：
>>> timeit.timeit(lambda: np.empty(100000000 ), number=10000)
0.2733485999999914
>>> timeit.timeit(lambda: np.empty(1000000000), number=10000)
0.8293009999999867
作为附带问题，未触及的 np.empty 数组中存在哪些值？它们都是非常小的值，但我希望它们只是该地址内存中存在的任何值。 （示例数组：np.empty(2) = array([-6.42940774e-036, 2.07409447e-117])。这些看起来与存储在内存中的内容完全不同）
首先，我尝试在我的各种尺寸的机器上重现这种行为。以下是原始结果：
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，而我的机器上显然没有。
for np.empty, which would imply that the time taken to create (allocate) this array would be O(1)
分配在 O(1) 中完成的假设并不完全正确。为了检查这一点，我构建了一个简单的 C 程序，执行一个简单的 malloc+free 循环并测量了时间。以下是原始结果：
./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
如您所见，结果与 Numpy 的结果匹配（除了小的结果，这是由于在 CPython 中调用 Python 函数的开销）。因此，问题不是来自 Numpy，而是标准 libc 中的分配算法或 OS 本身。
As a side question, what are the values present in an untouched np.empty array?
是未初始化的数据。实际上，它通常是零初始化的（但并非总是如此），因为主流平台出于安全原因清理分配的内存（以便密码等关键数据在先前存储在另一个进程的内存中时不会泄漏）。 你不应该依赖这个。
malloc 时间的更深入解释：
如您所见，100K 项和 1M 项的分配之间存在差距。这可以通过使用快速用户-space分配器（称为sbrk on Unix and Linux systems): when data are small, the libc of most mainstream platforms does not directly request memory to the operating system. It rather use a fast pre-allocated local memory-pool. Actually, on most mainstream platforms, multiple pool of different sizes are pre-allocated and the libc choose the "right one" depending on the allocated size, hence the timing variation for small data size. Note that this process is done to improve the allocation speed while taking into account memory fragmentation）来解释。这个策略比内核调用[= =75=]（如 mmap）非常昂贵（在我的机器上至少需要几微秒）。
此外，大多数操作系统 (OS) 都有看起来像多个内存池的东西。 Linux、MacOS 和 Windows 将 虚拟内存 分成小的 页 （通常为 4KB） .由于在太小的页面上工作会在处理 GB/TB 分配的数据时引入显着的开销，因此这些 OS 还提供称为超级页面或大页面的大页面（通常为 2MB 到几 GB）。在 OS 中采用的路径可以根据分配的内存量进行更改，并且大多数 OS 都针对分配小块 虚拟内存而不是大块进行了优化。
请注意，用于管理系统内存的数据结构的大小通常受 RAM 大小的限制，而 RAM 在运行时通常是恒定的。此外，在给定的 OS 中用于管理内存碎片的算法的复杂性 可能 是 理论上 O(1) （或接近）。因此，有些人认为 allocating/freeing 数据是在常数时间内完成的。但这有争议，因为人们应该考虑 实际 结果而不仅仅是 理论 渐近边界 .
更多信息您可以查看以下帖子：
- Time complexity of memory allocation
- Why does malloc initialize the values to 0 in gcc?
- Can an
O(n)algorithm ever exceedO(n^2)in terms of computation time?