9

トライ データ構造には非常に大きな分岐要素があり、各サブツリーは他のサブツリーから完全に独立しているため、すべての単語を並列に追加することで、特定の辞書のトライ構築を大幅に高速化する方法が必要なようです。

これを行う方法に関する私の最初のアイデアは次のとおりです。ミューテックスをトライ内の各ポインター (ルートへのポインターを含む) に関連付けてから、各スレッドを通常のアルゴリズムに従ってトライに単語を挿入します。ただし、ポインターをたどる前に、スレッドは最初にそのポインターのロックを取得する必要があります。これにより、新しい子ノードをトライに追加する必要がある場合に、データ競合を引き起こすことなく追加できるようになります。

このアプローチの問題点は、膨大な数のロック (トライ内の各ポインターに 1 つ) を使用し、膨大な数の取得と解放 (各入力文字列の各文字に 1 つ) を使用することです。

ほとんど多くのロックを使用せずに並列にトライを構築する方法はありますか?

4

4 に答える 4

9

明らかなロックフリーアルゴリズムは次のようになります。

  1. 入力文字列を長さkのプレフィックスでバケットソートします（通常、k = 1ですが、アルファベットが小さい場合はkを増やします）。
  2. 文字ごとに、その文字で始まるすべての文字列のkサフィックスを含むトライを作成します。
  3. 前のステップの試行をマージします（k = 1の場合、ルートノードを追加するだけです）。

接頭辞が均一に分布していると仮定すると、これにより、アルファベットのサイズのk乗まで線形に高速化できます。

于 2013-01-15T17:09:06.770 に答える
4

ロックの代わりにポインターでアトミックなテストと設定操作を使用することで、これをロックフリーにすることができることに気付きました。具体的には、スレッドがポインターを追跡する場合、次のことを行います。

  1. ポインター値をアトミックに読み取ります。
  2. ポインターが null でない場合は、それに従います。あなたは終わった。
  3. それ以外の場合は、新しいノードを割り当てます。
  4. null のポインターをアトミックにテストし、null の場合は新しいノードに設定します。
  5. (注: ここでは、ポインターは間違いなく非 null です。設定したばかりか、別のスレッドによって設定されたものです)。
  6. ポインターに従ってください。

ハードウェアによっては、常にロックとロック解除の作業を回避し、スレッドが無期限に待機しないようにするため、これははるかに高速になる可能性があります。

1 つの欠点は、関連する割り当ての数が増えることです。これは、複数のスレッドがすべてノードを割り当ててトライの特定の場所に配置しようとする可能性があるためです。ただし、そこに配置できるのは 1 つだけです。幸いなことに、これは次の最適化によって軽減できます。スレッドがノードをすぐに解放するのではなく、不必要に割り当てた場合は、ノードを一時スペースに格納するだけです。後で新しいノードを割り当てる必要がある場合は、キャッシュされたノードを使用できます。そうでない場合は、最後に解放できます。

お役に立てれば！

于 2013-01-15T17:08:17.197 に答える
1

辞書の外観によっては、各スレッドに独立したサブツリーを構築させることができれば、ロックはまったく必要ない場合があります。これがオンラインアルゴリズムでない場合は、単語をプレフィックスで事前に並べ替えます（たとえば、スレッドが26未満の場合は最初の文字、スレッドが多い場合は最初と2番目、データのバランスが取れていないことがわかっている場合は、単語の90％など） A）から始めます。基本的に、これはO（n）演算であり、特定の文字で始まる単語の数をカウントするために1回のパスを実行し、次に（選択したプレフィックスで基数ソートの行に沿って）ソートするために1回のパスを実行します。次に、プレフィックスをスレッド間で分割し、各スレッドにこれらの独立したサブツリーを構築させます。最後に、1つのスレッドでこれらの各サブツリーをルートに追加します。以下の例を見ていきます。

あなたの辞書：
樹皮
アップル
クッキー
と
ベイビー
コーン
ブルー
ケーキ
ベーコン

並べ替え後：
アップル
アンド
バーク
ベイビー
ブルー
ベーコン
コーン
クッキー
ケーキ

次に、プレフィックスをスレッド間で分割します。この例では、プレフィックス[A] [B] [C]を取得し、次のツリーを構築する3つのスレッドがあります。

A-| B ------- | C ------- |    
PN |-A --- | LO --- | A
PDRBCUORK
LKYOEKNE
ENI
                                   E

そして、次のようにルートでこれらを組み合わせる1つのスレッドがあります。

|-----------ルート------------------|
A-| B ------- | C ------- |    
PN |-A --- | LO --- | A
PDRBCUORK
LKYOEKNE
ENI
                                   E

それが理にかなっていることを願っています。

この方法の利点：スレッドは基本的に独立して機能し、ロックの取得と解放を処理する必要がないというオーバーヘッドがありません。

この方法の欠点：辞書について何も知らない場合、深刻なワークロードの不均衡が発生する可能性があり、最悪の場合（たとえば、すべての単語が「A」で始まる）、基本的にシングルスレッドの構築に戻ります。木。これを改善する方法はいくつかあります。たとえば、1文字のプレフィックスを処理するときにワークロードが大幅に不均衡な場合に、最初の2文字を使用するように並べ替えるときにチェックを追加できますが、実際には可能です。バランスが取れていることを保証します。

また、20のスレッドがあり、最初の文字で並べ替えると、アイドル状態のスレッドが発生する場合があります。2つのサブツリーを実行する必要があるスレッドが6つあり、そのうちの14が半分の時間アイドル状態になります。これに対処するためにサブツリーをさらに細分化できる場合がありますが、それは前処理ステップに余分な時間を費やします。

とにかく、これがあなたの方法よりも速いという保証はありませんが、それは考慮すべきことです。

于 2013-01-15T17:31:55.950 に答える
1

まあ、一連のノード(1 つではなく)に対してロックを設定するという細かい粒度と粗い粒度の間には明らかなトレードオフがあります。

これを行う簡単な方法は、ハッシュを使用することです。m異なるロックを使用し、アクセスするノードごとに番号付きのロックを取得しますhash(node) % m。
このアプローチは基本的に、提案されたアプローチ (完全なハッシュと をn == m使用) とシリアル アプローチ ( を使用m == 1) の一般化であることに注意してください。

利用される可能性のあるもう1つのことは、楽観的な設計です-アプローチが実際にパフォーマンスを向上させるかどうかは、もちろん辞書の分布とトライのサイズに依存し、衝突が非常にまれである傾向がある場合（これはおそらく非常に長い単語の辞書の場合)。
アイデアは、同期せずに単語をトライに追加するだけで、衝突が発生した場合は、最後の既知の安定状態にロールバックします (もちろん、これにはデータのスナップショットを撮る必要があり、実行できない場合があります)。保存できないデータのストリームについて話します)。

于 2013-01-15T16:55:29.403 に答える