4

私は、int64 の配列を多用する Python のアルゴリズムに取り組んでいます。通常、配列はまばらで、常に読み取りと書き込みが行われます。現在、比較的大きなネイティブ配列を使用しており、パフォーマンスは良好ですが、メモリ使用量が高くなっています (予想どおり)。

配列の実装で、使用されていない値のスペースを無駄にせず、ゼロ以外のインデックス オフセットを許可できるようにしたいと考えています。例として、数値が 1,000,000 から始まる場合、1,000,000 から始まる配列にインデックスを付け、100 万の未使用の値でメモリを浪費する必要がないようにしたいと考えています。

配列の読み取りと書き込みは高速である必要があります。新しい領域への拡大は少し遅れる可能性がありますが、可能であれば読み取りと書き込みは O(1) にする必要があります。

それができるライブラリを知っている人はいますか？

ありがとう！

データ型として int64 を記載するように更新されました。

4

5 に答える 5

4

blistタイプ ( documentation 、download ) はまさにあなたが探しているものかもしれません (免責事項: 私は著者です) 。Python の とまったく同じインターフェイスを備えているため、学習曲線はありませんが、異なるパフォーマンス特性を備えています。特に、多くの場合、スパース リストを効率的に処理できます。以下は、2**29 個の要素を持つリストを作成する例です。それはほとんど瞬時です。この方法で作成されたスパース リストは、O(log n) スペースを使用します。list

>>> from blist import *
>>> x = blist([0])             # x is a blist with one element
>>> x *= 2**29                 # x is a blist with > 500 million elements
>>> x.append(5)                # append to x
>>> y = x[4:-234234]           # Take a 500 million element slice from x
>>> del x[3:1024]              # Delete a few thousand elements from x

リスト全体を反復する操作には、依然として O(n) 時間かかります ( remove、reverse、countなど)。ドキュメントには、各操作の時間の複雑さが明記されているため、ニーズを満たすかどうかを評価できるはずです。

于 2010-06-09T04:33:32.407 に答える
1

もう1つのオプションは、少なくとも自分で実装する場合は、ページテーブルです。これは、仮想メモリシステムで仮想アドレスを物理アドレスにマップするために一般的に使用され、アドレススペースがまばらに配置され、使用されるアドレスがクラスター化されている場合に最適に機能します。使用するアドレスがランダムに分散している場合、これは効果が低くなります。

ページテーブルの基本的なアプローチは、 Trieと同じです-再帰的なサブディビジョン。ページテーブルには固定数のレベルがあり、各ノードは固定サイズの配列です。特定のサブノードのエントリがnullの場合、そのノードでカバーされるすべてのリーフはnullです。ページテーブルの主な利点は、ルックアップが高速で、わずかなビットシフトと逆参照のみが必要なことです。

2レベルのページテーブルの簡単なPython実装を見てみましょう。

class Pagetable(object):
  def __init__(self, num_bits=8):
    """Creates a new Pagetable with num_bits bits per level.

    Args:
      num_bits: The number of bits per pagetable level.
        A 2 level pagetable will be able to store indexes between 0 and 2^(num_bits*2).
    """
    self.num_bits = num_bits
    self.mask = (1 << num_bits) - 1
    self.root = [None] * (2 ** num_bits)

  def __getitem__(self, idx):
    page = self.root[idx >> self.num_bits]
    return page and page[idx & self.mask]

  def __setitem__(self, idx, val):
    page = self.root[idx >> self.num_bits]
    if not page:
      page = self.root[idx >> self.num_bits] = [None] * (2 ** self.num_bits)
    page[idx & self.mask] = val
于 2010-06-10T09:23:07.450 に答える
1

なぜdictを使用しないのですか？

sparse = dict()
sparse[100000] = 1234
sparse[123456] = 2345
于 2010-06-09T09:13:48.853 に答える
1

numpy のスパース マトリックスをスパース配列に再マップするか、ハッシュ テーブル (python dict) の使用を検討できます。オフセットに関する限り、使用しているストレージ クラスをラップして、独自の挿入/検索/削除メソッドを作成します。

于 2010-06-09T04:05:39.300 に答える
1

私はPythonを知らないので、これはおそらく未回答です:

一部の言語では、インデックス スペースからデータ スペースへの関数を定義することにより、スパース配列をシミュレートできます。例（疑似コード）：

f[1000000] = 32;
f[2000000] = 51;

一部の言語 (最良の言語) では、配列参照の形式 (例: f[3]) が関数呼び出しの形式 (例: ) のように見えますf[3]。これはもちろん、配列がインデックス空間からデータ空間への関数を定義するためです。このようにして、高次元のスパース配列を実装することも非常に簡単です。

于 2010-06-09T08:20:39.580 に答える