辞書のキーとして使用する必要のあるバイト配列があります。理想的には、バイト配列のサイズのメモリのコピーを実行せずにこれを実行したいと思います。とにかくこれを行うことはありますか？基本的に、
b = some bytearray
d[byte(b)] = x
これを行うためのより速い方法はありますか？byte（b）はO（len（bytearray））操作であり、望ましくありません。
質問する
2966 次
3 に答える
6
実際に正しく機能するハッシュアルゴリズムは、O（len（b））時間を使用します。したがって、「これを行うためのより速い方法はありますか」という答えはノーです。
実際の懸念がメモリ使用量である場合は、原則として、__hash__bytearrayのサブクラスにメソッドを追加できます。しかし、それはかなり悪い考えです。何が起こるか見てください：
>>> class HashableBytearray(bytearray):
... def __hash__(self):
... return hash(str(self))
...
>>> h = HashableBytearray('abcd')
>>> hash(h)
-2835746963027601024
>>> h[2] = 'z'
>>> hash(h)
-2835746963002600949
したがって、同じオブジェクトが辞書内の2つの異なる場所にハッシュされる可能性がありますが、これは発生しないはずです。そしてそれはさらに悪化します：
>>> d = dict()
>>> hb1 = HashableBytearray('abcd')
>>> hb2 = HashableBytearray('abcd')
>>> d[hb1] = 0
>>> d[hb2] = 1
>>> d
{bytearray(b'abcd'): 1}
わかりました、これまでのところ、とても良いです。値は等しいので、ディクショナリには1つのアイテムしかありません。すべてが期待どおりに機能しています。次に、変更するとどうなるか見てみましょうhb1。
>>> hb1[2] = 'z'
>>> d[hb2] = 2
>>> d
{bytearray(b'abzd'): 1, bytearray(b'abcd'): 2}
まったく変更されていなくても、hb2今回は辞書に新しいキーと値のペアが作成されたことがわかりますか？
キーをに渡すたびにd、そのキーはに等しくなりました'abcd'。しかし、辞書に追加された後に最初のキーの値が変更されたため、Pythonは、新しいキーの値が追加されたときの古いキーと同じであることを認識できませんでした。これで、ディクショナリには2つのキーと値のペアがありますが、1つしかないはずです。
これは、可変値をキーとして使用すると、予測できない非常に間違った動作につながる可能性がある多くの方法の1つにすぎません。を不変型に変換するbytearrayか、そもそも不変型を操作するだけです。
そして好奇心旺盛な人のために：確かにbuffer、最初のハッシュをキャッシュしますが、それはまったく役に立ちません。キー値は2つしかないため、生成されるdictエントリは2つだけです。
>>> a, b, c = bytearray('abcd'), bytearray('abcd'), bytearray('abzd')
>>> a_buf, b_buf, c_buf = buffer(a), buffer(b), buffer(c)
>>> d = {b_buf:1, c_buf:2}
>>> b[2] = 'z'
>>> d[a_buf] = 0
しかし、それは3つを生成します。
>>> d
{<read-only buffer for 0x1004a2300, size -1, offset 0 at 0x100499cb0>: 1,
<read-only buffer for 0x1004a2420, size -1, offset 0 at 0x100499cf0>: 0,
<read-only buffer for 0x1004a22d0, size -1, offset 0 at 0x100499c70>: 2}
于 2012-10-24T01:22:49.820 に答える
4
時間に関心があり、使用しているキーが常に同じオブジェクトである場合は、そのid（メモリ内の場所）を辞書のキーとして使用できます。
b = some byte array
d[id(b)] = x
メモリが心配な場合は、バイト配列に対して優れた暗号化ハッシュ関数を使用できます。おそらく衝突は発生しません（たとえば、gitはsha1を使用します。インターネット上で、その方法についていくつかの 議論があります。不注意によるsha1の衝突が発生する可能性があります）。その微小なリスクに問題がない場合は、次のことができます。
b = some byte array
d[hashlib.sha1(b).hexdigest()] = x
これは、時間内にバイト配列のサイズがO（n）になります（ハッシュを計算するたびに）が、後で別のバイト配列を読み込むことができますが、同じシーケンスを表します同じ辞書キーにハッシュされます。
そして@senderleは絶対に正しいです。id()ディクショナリのキーとして（のような不変の関数ではなく）値で使用する場合、実際に可変であるオブジェクトを使用したくありません。辞書キーとして使用されるオブジェクトのハッシュは変更してはなりません。これは、辞書オブジェクトがハッシュ関数に期待するものの不変条件に違反します。
于 2012-10-24T01:44:53.177 に答える
1
これはあなたが望むものに近いかもしれないと思います。比較的高速で、バイト配列のサイズのメモリをコピーしませんが、O（len（bytearray））です。これを回避する方法は考えられず、常に一意の値を生成します。
def byte(ba):
""" decode a bytearray as though it were a base 256 number """
return reduce(lambda a,d: a*256 + d, ba, 0)
ba = bytearray('this is a bytearray')
d = {}
d[byte(ba)] = 42
ba[8] = 'X' # now 'this is X bytearray'
d[byte(ba)] = 17 # accesses a separate entry in dict
print d
于 2012-10-24T18:28:12.007 に答える