6

9 桁の整数であるキーと、各キーに関連付けられたブール値を持つインメモリ オブジェクトを作成する必要があります。以下の単純化された例のように、辞書を使用しています。

#!/usr/bin/python
from __future__ import print_function
import sys

myDict = {}
for n in range(56000):
        myDict[n] = True

print('Count:',len(myDict),' Size:', sys.getsizeof(myDict))

各キーに関連付けられたブール値を検索して取得できる必要があります。問題は辞書のサイズです。64 ビット Linux システムで Python 2.7 を使用し、上記の例を使用すると、sys.getsizeof() によると、dict のサイズは 3.1 メガバイトになります。(9 桁とブール値を格納するために、エントリごとに約 56 バイト)

(約) 55.000 エントリのブール状態を dict に保存する必要があります。各 dict キーは 9 桁の整数です。辞書のサイズを変更せずに、整数と str(theInteger) をキーとして使用してみました。

このような大規模なデータセットでメモリを節約するために使用する必要がある他の種類のデータ構造または方法論はありますか?

4

5 に答える 5

8

ブール値を整数キーで検索し、キーの範囲が 0 から始まり、連続している場合、リストを使用しない理由はありません。

my_list = []
for n in range(56000):
        my_list[n] = True

またはそれ以上:

my_list = [True for n in range(5600])

それでも不十分な場合は、arrayモジュールを試して、ブールごとに 1 バイトを使用します。

import array
my_array = array.array("b", (True for n in range(56000)))

それでも十分でない場合は、PyPi で bitarray モジュールを試してください。

もう 1 つのアイデアは、 を使用することsetです。FalseTrue

my_true_numbers = {0, 2323, 23452} # just the True ones

で確認してください

value = number in my_true_numbers

を超える場合はTrue、False逆にします。

于 2013-09-04T13:32:20.207 に答える
3

Pythonの受け入れられた答え：辞書のメモリ使用量を減らすには、できることはあまりないという結論があり、私はそれに同意します。ディクショナリの全体的なメモリ オーバーヘッドは小さいですが、例のキーと値のペアの数によってメモリ フットプリントが増加します。

可能性があると思うかもしれません: キーが常に線形である場合は、ブール値のリストを直接作成するか、bitarrayを使用することをお勧めします。その場合、キーは暗黙的になります。しかし、これがあなたの例にのみ当てはまる場合、多くのことはできません。

于 2013-09-04T13:24:02.677 に答える
2

「キーが見つかりません」が重要な状態ではない場合 (つまり、配列にないキーを として扱っても問題ないFalse場合)、set代わりに a を使用して、 にマップする要素だけを格納できますTrue。これは、各エントリが 3 つの量 (ハッシュ、キー、値) ではなく 2 つの 64 ビット量 (ハッシュとキー) だけで構成されるため、必要なスペースが約 30% 少なくなります。

含まれているオブジェクトではなく、それ自体sys.getsizeof(dict)のサイズのみを示すことに注意してください。dictキーとして56000 を作成intすると、独自のコストもかかります: 整数ごとに 24 バイト (型ポインター、refcount、値)。ディクショナリが使用するメモリに加えて、それだけで 1.3MB になります。

スペースを本当に節約するには、NumPy で圧縮されたスパース行行列を使用できます。

from scipy.sparse import lil_matrix # linked-list matrix, used to construct the csr matrix
vals = lil_matrix((1,1000000000), dtype='int8'))
# We will use 0 = no such key, 1 = True, 2 = False
for n in myIndices:
    vals[n] = 1
vals = vals.tocsr()

のメモリ使用量valsは非常に少なく、データ用に 56KB、インデックス用に 224KB、その他の構造用に 1KB 未満です。したがって、合計サイズは281KB未満(dict の 10 分の 1) であり、余分に割り当てられた整数はありません。要素を調べてゼロ以外の要素を変更するのは非常に高速ですが (ソートされた配列でのバイナリ検索)、新しいゼロ以外の値を挿入したり、既存のゼロ以外の値をゼロにしたりする操作はコストがかかります。

于 2013-09-04T13:54:07.350 に答える
0

正確なニーズに応じて、リストを使用して値を保存できます。これは、ディクショナリが使用するスペースの約 16% しか使用しませんが、ルックアップや挿入などの特定の操作は (おそらくかなり) 遅くなります。

values = list(range(56000))

モジュールを使用bisectしてソートされたリストに値を保存すると、ルックアップは dict よりも遅くなりますが、単純なx in my_listチェックよりもはるかに高速です。

リストは常にソートされた順序で保持する必要があります。値がリストにあるかどうかを確認するには、次の関数を使用できます。

def is_in_list(values, x):
    i = bisect_left(values, x)
    return i != len(values) and values[i] == x

次のように機能します。

>>> is_in_list([2, 4, 14, 15], 4)
True
>>> is_in_list([2, 4, 14, 15], 1)
False
>>> is_in_list([2, 4, 14, 15], 13)
False

このメソッドはメモリ使用量を大幅に削減しますが、dict または set と比較して、検索には O(1) ではなく O(log n) の時間がかかり、挿入には O(1) ではなく O(n) の時間がかかります。

于 2013-09-04T16:54:04.103 に答える