リストランキング

並列アルゴリズムにおけるリストランキング問題では、リンクリスト内の各項目の位置、つまり順位を決定する必要があります。つまり、リストの最初の項目には番号 1 を割り当て、リストの 2 番目の項目には番号 2 を割り当てる、というように割り当てます。この問題は、リストを順番に走査する順次コンピュータで効率的に解くのは簡単ですが、並列で解くのはより複雑になります。Anderson と Miller (1990) が書いたように、この問題は、その多くの用途と、それを解決することで並列アルゴリズムに広く適用できる多くの重要なアイデアが生まれたことから、並列アルゴリズム コミュニティでは重要視されていました。

リストランキング問題は Wyllie (1979) によって提起され、対数時間と O( n log n ) の合計ステップ数 (つまり O( n ) プロセッサ) を使用する並列アルゴリズムで解決されました。その後の多くの論文を経て、最終的には、同期共有メモリ並列計算の最も制限的なモデルである排他的読み取り排他的書き込み PRAM (Vishkin 1984、Cole & Vishkin 1989、Anderson & Miller 1990) で線形ステップ数 ( O ( n/logn) プロセッサ) に改善されました。このステップ数は、シーケンシャル アルゴリズムと一致します。

リストのランキングは、与えられたリストに対してプレフィックス合計演算を実行することと同等と見なすことができます。このとき、合計される値はすべて 1 になります。リストのランキング問題は、オイラー ツアー技法を介してツリーに関する多くの問題を解決するために使用できます。この技法では、ツリーの各エッジのコピーを各方向に 1 つずつ含むリンク リストを作成し、リストのランキングを使用してこのリストのノードを順序付けられた配列に配置し、順序付けられた配列に対してプレフィックス合計計算を実行します (Tarjan & Vishkin 1985)。たとえば、ツリーの各ノードの高さは、プレフィックス合計が下向きのエッジごとに 1 を加算し、上向きのエッジごとに 1 を減算するこのタイプのアルゴリズムによって計算できます。

• アンダーソン、リチャード J.; ミラー、ゲイリー L. (1990)、「リストランキングのための単純なランダム化並列アルゴリズム」、情報処理レター、33 (5): 269–273、doi :10.1016/0020-0190(90)90196-5。
• コール、リチャード;ヴィシュキン、ウジ(1989)、「より高速な最適並列プレフィックス合計とリストランキング」、情報と計算、81 (3): 334–352、doi : 10.1016/0890-5401(89)90036-9。
• ロバート・E・タージャン; Vishkin、Uzi (1985)、「効率的な並列双接続アルゴリズム」、SIAM Journal on Computing、14 (4): 862–874、CiteSeerX  10.1.1.465.8898、doi :10.1137/0214061、S2CID  7231609。
• Vishkin, Uzi (1984)、「並列計算におけるランダム化による高速化」、第 16 回 ACM コンピューティング理論シンポジウム議事録 - STOC '84、pp. 230–239、doi :10.1145/800057.808686、ISBN 0-89791-133-4、S2CID  17475781。
• Wyllie, JC (1979)、「並列計算の複雑さ」、コーネル大学コンピュータサイエンス学部博士論文。