4

チェーンを介して衝突解決を行う場合は、ハッシュテーブルの方が適していると思います。読み取りまたは書き込み操作では、ハッシュテーブルのそのエントリ (インデックスと値) のロックを取得する必要があるのに対し、 BST全体でロックを取得して、更新を行います。

BST構造全体をロックする必要があると思います。ツリーに新しいノードを挿入する必要があると想像してください。最初にトラバースして正しい親位置（ノードAなど）に到達する必要があり、取得していない場合ツリー構造をロックすると変更される可能性があり、最初からやり直す必要があります。

ハッシュ テーブルの場合、入力は常に同じ位置にハッシュされ、どのインデックスをロックするかがわかりますが、BST の場合は不明です。

私が間違っているところを修正し、正しい答えを見つけるのを手伝ってください。

PS: これは Amazon インタビューの質問です。

4

2 に答える 2

0

ハイブリッド ソリューションを実行できます。各スロットがバイナリ ツリーであるハッシュ テーブルを実行します。つまり、1024 個のスロットがあり、それぞれにバイナリ ツリーがあります。ハッシュの衝突はバイナリ ツリーに入ります。挿入時にすべてをロックする必要はありません。更新する必要があるツリーだけです。

さらに、アトミック操作といくつかの巧妙さを使用すると、ロックを完全に回避することで、さらに並行処理を行うことができます。新しいノードを挿入するためのアトミック更新。アトミック更新が失敗した場合、別のスレッドがノードを追加し、成功するまで単純にループします。

私はすでにこれを行ってい ます https://github.com/exodist/GSD/tree/master/Structures

これは高度な並行ハッシュ/ツリー ハイブリッドです。アトミック操作を使用し、ミューテックスは使用しません。挿入時にスピンできますが、既存のキーの読み取りまたは更新をブロックすることはありません。サイズ変更/バランス調整などを行うことができます。すべてのエントリなどをトラバースできます。独自のメモリを管理し、キー/値を参照カウントするためのコールバックがあります。また、あるディクショナリのキーを別のディクショナリに「リンク」して、最初のキーを更新すると 2 番目の値が変更されるようにすることもできます。

この設計では、実際には、問題に対してより多くのスレッドを投入するとパフォーマンスが向上します。

(T) はスレッドの数、MI は無視、slots は使用されているハッシュ スロットの数、Ops は挿入されているアイテムの数です (スレッドで割ると、各スレッドの処理量がわかります)

./performance.run
   T, MI,   Slots,      Ops:      Insert   Rebalance      Update      Resize      Lookup      Immute            
   4, 16,    1024,  5000000:  2.765500363  0.915232065  2.540659476  2.172654813  2.545409560  2.089993698
13.029449975
   4, 16,   32768,  5000000:  2.122459866  1.403548309  2.413483374  1.885083901  2.092272466  2.643681518
12.560529434
   4, 16, 1048576,  5000000:  1.700994809  1.063704010  2.030809367  2.457275707  1.453413924  3.671012425
12.377210242
  16, 16,    1024,  5000000:  0.785675781  2.311281904  1.805610753  0.621521146  0.549546473  0.744009412
6.817645469
  16, 16,   32768,  5000000:  0.497359638  0.316017553  1.257663142  0.610761414  0.390849355  0.825944608
3.898595710
  16, 16, 1048576,  5000000:  0.328308989  0.647632801  1.267230625  1.139402693  0.342399827  1.189220470
4.914195405
  64, 16,    1024,  5000000:  0.129407132  0.767262021  2.631929019  0.157977313  0.103848004  0.177964574
3.968388063
  64, 16,   32768,  5000000:  0.087656606  0.068330231  1.365794852  0.166261966  0.079112728  0.203542885
1.970699268
  64, 16, 1048576,  5000000:  0.074605680  0.284322979  1.372998607  0.650503349  0.084956938  0.828653807
3.296041360

注: 8 GB の RAM を搭載した i7 で 1 回実行。古い __sync から __atomic に切り替えるプロセスで、gcc アトミック ビルトインを使用します。これは、メモリ モデルのためにパフォーマンスを向上させる可能性があります。

于 2013-11-01T00:20:45.070 に答える
0

並行性の観点からは、あなたが言ったことは正しいと思います。ハッシュテーブルの方が良い選択ですが、シリアライゼーションに関しては、BSTの方が良いと思います. これは、BST ではデータ ノードのみを持つためですが、ハッシュ テーブルではデータのキーと値のペアの両方があり、値のないキーはほとんどありません。したがって、シリアル化すると、BST と比較してより多くのスペースが必要になります。

于 2013-02-21T09:27:21.537 に答える