1

10 個のバケット リストのセットを持つ単純なハッシュ テーブルを作成しています。インデックスは組み込み関数を使用して計算されhash()、テーブル サイズをモジュロします。ただし、そのインデックスでオブジェクトをバケット リストに追加しようとすると、代わりにすべてのバケット リストに追加されます。add_HT をさまざまな方法で定義しようとしましたが、同じ結果が得られます。私は何を間違っていますか？

size = 10
HT = [ [] ] * size

def add_HT(data):
    index = hash(data) % size
    HT[index].append(data)

print HT

[[], [], [], [], [], [], [], [], [], []]

add_HT('hello')

[['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello'], ['hello']]
4

4 に答える 4

5

HT = [ [] ] * size同じリストsizeへのポインターの数を作成します。ここで問題ではありません。として定義する必要があります。add_HTHT[[] for i in xrange(size)]

于 2013-01-07T05:42:55.313 に答える
4

HT単一のリストへの 10 個の参照として定義しています。代わりに、次のように定義します。

HT = [[] for _ in xrange(size)]
于 2013-01-07T05:43:03.657 に答える
3

ボラティリティとキンダルがすでに説明したように、10個の異なる空ではなくHT = [ [] ] * size、同じ空の10個のコピーを作成します。アイデンティティは常に初心者のプログラマーを噛み、時には専門家さえも噛みます。listlistlist

彼らはすでに問題を解決し、10個listの異なる空を取得する方法を示しました。しかし、この問題を回避する別の方法があります。をまったく変更しないようにプログラムを書き直すことができる場合、listそれらが同じであるかどうかは関係ありません。

def add_HT(data):
    index = hash(data) % size
    HT[index] = HT[index] + [data]

今：

>>> add_HT('hello')
>>> add_HT('goodbye')
>>> HT
[['goodbye'], ['hello'], [], [], [], [], [], [], [], []]

ここで起こっていることは、追加するたびに新しいバケットを作成し、古いバケットを置き換えるため、バケットは不変です。（誤って変更しないように、tuplesではなくsとして保存することをお勧めします。）list

これをさらに進めて、それぞれをHT[i]不変にするだけでなく、HTそれ自体も不変にすることができます。

def add_HT(data):
    global HT
    index = hash(data) % size
    HT = [bucket if i != index else bucket + [data] for i, bucket in enumerate(HT)]

物事を不変にすることで、コードが単純になることもあれば、より複雑になることもあります。（この場合、最初の不変バージョンは可変バージョンとほぼ同じくらい単純だと思いますが、2番目のバージョンははるかに読みにくくなります。）コードが速くなることもあれば、遅くなることもあります。（この場合、簡単なテストでは、最初の速度はほぼ同じですが、2番目の速度は50倍遅く、より多くのメモリを使用します。一方、CPythonの代わりにPyPyを使用すると、15％と30％になります。それぞれ遅くなります…）しかし、それは常に推論を容易にします—オブジェクトのアイデンティティについて心配する必要はありません。書きやすく、読みやすく、高速になる場合を除いて、考慮しなければならないトレードオフがあります。しかし、それを行う方法を知ることは価値があります。

于 2013-01-07T06:05:44.380 に答える
0

正しいバージョンは次のとおりです。

size = 10
HT = [ [] for x in range(size)]

def add_HT(data):
    index = hash(data) % size
    HT[index].append(data)

print HT

add_HT('hello')
print HT

出力：

>>> 
[[], [], [], [], [], [], [], [], [], []]
[[], ['hello'], [], [], [], [], [], [], [], []]
>>>
于 2013-01-07T05:47:56.143 に答える