直接索引numpy数组的时间复杂度是多少 [英] What's the time complexity of indexing a numpy array directly

问题描述

我假设当有一个numpy数组时，假设

I assume when having a numpy array, let's say

>>>>nArray
array([[  23425.     ,  521331.40625],
       [  23465.     ,  521246.03125],
       [  23505.     ,  528602.8125 ],
       [  23545.     ,  531934.75   ],
       [  23585.     ,  534916.375  ],
       [  23865.     ,  527971.1875 ]])

直接索引必须非常有效.

direct indexing must be pretty efficient.

我想像nArray[0, 1] = 69696420之类的东西必须使用哈希表，这将使时间复杂度接近O(1).是吗?

I imagine something like that nArray[0, 1] = 69696420 must be using a hash-table which will give a time complexity close to O(1). Is that right?

更新

正如两个答案都指出的那样，在索引numpy数组时不涉及散列.这两个答案都清楚地说明了索引编制的过程.

As both answers noted, there is no hashing involved in indexing a numpy array. Both answers give a clear explanation about how the indexing happens.

更新2

我添加了一个简单的基准测试来证明答案的有效性

I added a simple benchmarking to prove the validity of the answers

推荐答案

一方面

必须使用哈希表，该哈希表将使时间复杂度接近O(1).是吗?

must be using a hash-table which will give a time complexity close to O(1). Is that right?

不太正确. Numpy array基本上是同类内存的连续块，以及有关尺寸等方面的一些额外信息.因此，访问权限为 O(1)，仅涉及一些简单的数学运算即可确定内存中的位置.

is not quite true. Numpy arrays are basically contiguous blocks of homogeneous memory, with some extra info on the side on dimensions and such. Therefore, the access is O(1), and just involves some trivial math to determine the position within the memory.

另一方面

索引编制必须非常有效.

indexing must be pretty efficient.

不幸的是，

根本不是真的.从边界检查(哪些数组可以做到)的角度来看，涉及纯python的一切都效率极低(访问涉及纯python调用). numpy数组访问为无例外.您应尽可能尝试使用向量运算.

is unfortunately not true at all. Asides from bounds checking (which arrays do), everything involving pure python is extremely inefficient (and accesses involve pure-python calls). Numpy array access is no exception. You should try to use vector operations whenever possible.

这篇关于直接索引numpy数组的时间复杂度是多少的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！