什麼是索引一個numpy的陣列直接

Question

的時間複雜度有numpy的陣列時，我認爲，我們說

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

直接索引必須是相當有效。

我想象那樣的nArray[0, 1] = 69696420必須使用一個哈希表，它會給時間複雜度接近O（1）。是對的嗎？

更新

作爲兩個答案指出，沒有涉及索引一個numpy的陣列散列。這兩個答案給出了索引如何發生的清晰解釋。

更新2

我添加了一個簡單的基準測試來證明答案

Answer 1

一方面，

必須使用哈希表，這將接近給出一個時間複雜度到O（1）。是對的嗎？

並不完全正確。 Numpy array s基本上是contiguous blocks of homogeneous memory，在尺寸等方面有一些額外的信息。因此，訪問權限是O（1），並且僅涉及一些微不足道的數學來確定內存中的位置。

在另一方面

索引必須是相當有效。

不幸的是不是真的。除了邊界檢查（哪些數組），涉及純python的所有事情都非常低效（訪問涉及純python調用）。 Numpy數組訪問是no exception。只要可能，你應該嘗試使用矢量操作。

Answer 2

有沒有涉及哈希表的有效性。 numpy的陣列排列，就像名字所暗示的，並且地址計算是這樣的：

address of nArray[x, y] = base address + A * x + B * y 

Answer 3

要通過測試添加一些額外的驗證到Ami的答案我做了一個簡單的循環緩衝區從一個numpy陣列只使用直接索引來插入。基本上每個插入只是改變隊列中最舊元素的值。

代碼不是完全沒有bug，但它可以作爲一些簡單的性能基準測試的基礎。

import math 
import numpy as np 


class CircFifo(): 
""" 
helper class, uses a numpy array to provide a circular fixed size fifo 
interface. 

put(element): removes the oldest element and 
places a new one 

get(): returns the oldest entry 

empty(): returns true if fifo is empty 

full(): returns true if fifo is full 
""" 
def __init__(self, size): 
    self.array = np.empty(shape=(size, 2)) 
    self.size = size 
    self.array[:] = np.NAN 
    self.top = 0 
    self.bottom = 0 

def put(self, row): 
    self.array[self.top, :] = row 
    self.top += 1 
    if self.top == self.size: 
     self.top = 0 

def get(self): 
    if not math.isnan(self.array[self.bottom, 0]): 
     row = copy.deepcopy(self.array[self.bottom, :]) 
     self.array[self.bottom, :] = float('NaN') 
     self.bottom += 1 
    if self.bottom == self.size: 
     self.bottom = 0 
    if math.isnan(self.array[self.bottom, 0]): 
     self.bottom = 0 
     self.top = 0 
    return row 

def empty(self): 
    if math.isnan(self.array[self.bottom, 0]): 
     return True 
    else: 
     return False 

def full(self): 
    if self.size - np.count_nonzero(
      np.isnan(self.array[:, 0])) == self.size: 
     return True 
    else: 
     return False 

在帖子中的答案的正確性似乎通過我運行一個簡單的測試來確認。我測試了對deque對象的插入性能。即使是1000個插入deque，它也是一個動態而非靜態的數據結構（與我的靜態循環fifo相反），顯然勝過了循環fifo。

下面是簡單的測試，我跑

In [5]: import time 

In [6]: circFifo = CircFifo(300) 

In [7]: elapsedTime = 0 

In [8]: for i in range(1, 1000): 
    ...:   start = time.time() 
    ...:   circFifo.put(np.array([[52, 12]])) 
    ...:   elapsedTime += time.time() - start 
    ...:  

In [9]: elapsedTime 
Out[9]: 0.010616540908813477 


In [21]: queue = deque() 

In [22]: elapsedTime = 0 

In [23]: for i in range(1, 1000): 
    ....:   start = time.time() 
    ....:   queue.append(np.array([[52, 12]])) 
    ....:   elapsedTime += time.time() - start 
    ....:  

In [24]: elapsedTime 
Out[24]: 0.00482630729675293 

我知道，這個基準是不是言之有物，但它變得相當明顯，雙端隊列爲快得多。至少需要這樣的插入量。

我認爲如果這個循環fifo是在C中用一個靜態數組實現的，它不可能輕易超越。由於基本上C的靜態數組是最簡單的並且具有較少的開銷數據結構。