0

pytables ファイル操作の時間の複雑さはget_node?

私がクエリするとしましょう

mynode = myfile.get_node(where='group0/group1/..../groupN', name ='mynode')

の親グループの数 N で、この演算はどのようにスケーリングされmynodeますか? 直線的に、つまり O(N)、またはさらに悪い O(N*d) ここで、d は私の hdf5 ノード ツリーの平均分岐係数、または非常に高速な O(1) です。

どうもありがとう！

4

1 に答える 1

1

HDF5 はノードを B ツリーとして実装するため、get_node() の時間計算量は O(log N) [1] です。PyTables は、この O(1) を作成するために、これらのパスをディクショナリにプリロードしません。ただし、ノードがロードされると、「alive」としてタグ付けされ、alive_nodes ディクショナリに入ります。したがって、ノードがメモリに残っている限り、後続のアクセスは O(1) です。したがって、これは一種の怠惰な O(1) 操作であり、O(log N) コストを一度前払いします。

  1. http://en.wikipedia.org/wiki/B-tree
于 2013-09-12T00:20:03.547 に答える