直接

Question

をnumpyの配列をインデックスの時間複雑だ私は、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は基本的にはcontiguous blocks of homogeneous memoryで、寸法などの面でいくつかの追加情報があります。したがって、アクセスはO（1）であり、メモリ内の位置を決定するためにはほんの些細な計算が必要です。

一方

インデックスはかなり効率的でなければなりません。

は、まったく真実ではありません。境界検査（配列が行う）を除いて、純粋なPythonを含むすべてのものは非常に非効率的です（アクセスは純粋なPython呼び出しを伴います）。ナンシーアレイのアクセスはno exceptionです。可能であれば、ベクトル操作を使用するようにしてください。

Answer 2

の妥当性を証明するための簡単なベンチマークを追加しました。 numpyの配列は名前が示すと同じように、配列され、アドレスは次のように計算されます。一方で

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

Answer 3

Ami's Answerへのテストを通して追加の検証を追加するには、直接インデックスを使用して挿入するだけの単純な円形バッファを作成しました。基本的には、各挿入はキュー内の最も古い要素の値を変更するだけです。

コードは完全にバグがないわけではありませんが、いくつかの簡単なパフォーマンスベンチマークの基礎として役立ちます。

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 

投稿の回答の正しさは、私が走っている簡単なテストを通じて確認されているようです。デキューオブジェクトに対する挿入パフォーマンスをテストしました。静的なデータ構造ではなく動的な構造としても機能するサーバーを1000個挿入する場合でも、循環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の静的配列はシンプルで、利用可能なオーバーヘッドの少ないデータ構造です。