最も近い小さい値すべて

コンピュータサイエンスにおいて、最も近くてより小さい値の問題とは、一連の数字の各位置について、前の位置の中からより小さい値を含む最後の位置を検索するというタスクです。この問題は、並列アルゴリズムと非並列アルゴリズムの両方で効率的に解決できます。この手順が他の並列プログラムの便利なサブルーチンであることを最初に特定した Berkman、Schieber、Vishkin (1993) は、並列ランダムアクセスマシンモデルでこの問題を解く効率的なアルゴリズムを開発しました。また、スタックベースのアルゴリズムを使用して、非並列コンピュータで線形時間で解くこともできます。その後、研究者は並列計算の他のモデルでこの問題を解くアルゴリズムを研究しました。

入力が2進数のファンデルコルプットシーケンスであると仮定する

0、8、4、12、2、10、6、14、1、9、5、13、3、11、7、15。

シーケンスの最初の要素 (0) には、前の値がありません。8 と 4 の前の最も近い (唯一の) 小さい値は 0 です。12 の前の 3 つの値はすべて小さいですが、最も近いのは 4 です。同様に、このシーケンスの最も近い前の小さい値 (ダッシュで前の小さい値が存在しないことを示します) は次のとおりです。

—、0、0、4、0、2、2、6、0、1、1、5、1、3、3、7。

ほとんどのアプリケーションでは、値自体ではなく、最も近い小さい値の位置を計算する必要があり、多くのアプリケーションでは、シーケンス内で最も近い次の小さい値を見つけるために、シーケンスの逆順に同じ計算を行う必要があります。

Berkman、Schieber、Vishkin (1993) は、最も近い小さい値の計算を使用して並列で効率的に解決できる他の多くの問題に言及しています。その中には、次のものが含まれます。

• マージ アルゴリズム、マージ ソートのマージ ステップを計算します。これらのアルゴリズムへの入力は、2 つのソートされた数値配列で構成されます。目的の出力は、1 つのソートされた配列内の同じ数値セットです。2 つのソートされた配列を連結すると (最初の配列は昇順、2 番目の配列は降順)、出力内の各値の前の値は、最も近い前の小さい値か、最も近い次の小さい値 (2 つのうち大きい方) のいずれかになり、ソートされた出力配列内の各値の位置は、これら 2 つの最も近い小さい値の位置から簡単に計算できます。
• デカルト木の構築。デカルト木は、Vuillemin (1980) によって導入され、範囲検索アプリケーション用に Gabow、Bentley、Tarjan (1984) によってさらに研究されたデータ構造です。デカルト木は、バイナリ検索用のtreapおよびランダム化バイナリ検索木データ構造の定義にも使用されます。値のシーケンスのデカルト木には、値ごとにノードがあります。木のルートはシーケンスの最小値です。他のすべてのノードについては、ノードの親は、そのノードに最も近い前のより小さい値か、そのノードに最も近い次のより小さい値 (2 つのうちのどちらか大きい方) のいずれかです。したがって、デカルト木は、すべての最も近いより小さい値のアルゴリズムに基づいて線形時間で構築できます。
• 対応する括弧。開き括弧と閉じ括弧の文字のシーケンスが入力として指定され、各括弧の入れ子の深さも指定されている場合、各開き括弧に一致するのは、入れ子の深さがそれより深くない次の閉じ括弧であるため、閉じ括弧を優先して同点の場合は最も近い小さい値をすべて計算することで見つけることができます。入れ子の深さが指定されていない場合は、プレフィックスの合計計算を使用して計算できます。

同様の技術は、多角形の三角分割、凸包の構築（逐次グラハムスキャン凸包アルゴリズムの並列化）、2つの木の走査順序からの木の再構築、および四分木の構築などの問題にも適用できます。^[1]

シーケンシャル コンピュータでは、スタック データ構造を使用して、最も近い小さい値をすべて見つけることができます。スタックを使用して、これまでに処理された値のうち、すでに処理された後続の値よりも小さい値のサブシーケンスを維持しながら、シーケンス順に値を処理し、擬似コードでアルゴリズムを説明します。

S =入力シーケンス内の xの新しい空のスタックデータ構造
。S
    が空でなく、S の先頭要素が x より大きいか等しい場合。
        ポップS
    Sが空の場合
        x にはそれより小さい値が存在しない
    それ以外
        xに最も近い小さい値はSのトップ要素である
    xをSにプッシュする

ネストされたループ構造を持つにもかかわらず、このアルゴリズムの実行時間は線形です。これは、内側のループの各反復で、外側のループの以前の反復で追加された項目が削除されるためです。これは、スタックを使用したソートのKnuthアルゴリズム(この方法でソートできる入力の場合) と密接に関連しています。[ ^2]

さらに単純な線形時間シーケンシャルアルゴリズム (Barbay、Fischer、Navarro (2012)、補題 1) ではスタックさえ必要ありません。このアルゴリズムでは、入力シーケンスがA[1,n]サイズ の配列として与えられ、^番目の値の前の小さい値のnインデックスをに格納すると想定します。 で全体の最小値を人為的に想定します。 jiA[i]P[i]A[0]

i は 1 から n までです:
    ｊ＝ｉ−１
    A[j] >= A[i]の場合:
        j = P[j]
    P[i] = j

Berkman、Schieber & Vishkin (1993) は、同時読み取り同時書き込み並列ランダム アクセス マシンで、最も近い小さい値すべての問題を効率的に解く方法を示しました。配列として格納されたn個の値のシーケンスに対して、彼らは二重対数木を使用して、線形の総作業量を使用して、問題が O(log log  n ) の時間で解ける可能性があることを示しました。すべての値が区間 [1, s ]内の整数であるシーケンスに対して、Berkman、Matias & Ragde (1998) はこの境界を O(log log log  s ) に改善しました。また、十分に大きいsの値に対して、以前の二重対数時間境界が問題に対して達成できる最良のものであることも示しました。この研究以来、すべての最も近い小さい値問題の並列アルゴリズムは、ハイパーキューブ構造の通信ネットワークを備えた並列コンピュータ^[3]やバルク同期並列モデル^[4]など、他の並列計算モデルでも開発されています。

• Barbay, Jeremy; Fischer, Johannes; Navarro, Gonzalo (2012)、「LRM ツリー: 圧縮インデックス、適応ソート、および圧縮順列」、理論計算機科学、459 : 26–41、arXiv : 1009.5863、doi :10.1016/j.tcs.2012.08.010。
• Berkman, Omer; Matias, Yossi; Ragde, Prabhakar (1998)、「小さな領域における最小値と範囲の最小値に対する 3 対数並列上限と下限」、Journal of Algorithms、28 (2): 197–215、doi :10.1006/jagm.1997.0905。
• Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993)、「最も近い小さい値をすべて見つけることに基づく最適な二重対数並列アルゴリズム」、Journal of Algorithms、14 (3): 344–37​​0、doi :10.1006/jagm.1993.1018。
• Bern, Marshall; Eppstein, David ; Teng, Shang-Hua (1999)、「並列四分木の構築と高品質の三角測量」(PDF)、International Journal of Computational Geometry & Applications、9 (6)、World Scientific Publishing Company: 517–532、doi :10.1142/S0218195999000303。
• Gabow, Harold N. ; Bentley, Jon Louis ; Tarjan, Robert E. (1984)、「幾何学問題に対するスケーリングと関連技術」、第 16 回 ACM コンピューティング理論シンポジウム議事録 - STOC '84、ニューヨーク、ニューヨーク、米国: ACM、pp. 135–143、doi :10.1145/800057.808675、ISBN 0-89791-133-4、S2CID  17752833。
• He, Xin; Huang, Chun-Hsi (2001)、「最も近い小さい値すべてに対する通信効率の良い BSP アルゴリズム」、Journal of Parallel and Distributed Computing、61 (10): 1425–1438、doi :10.1006/jpdc.2001.1741。
• Kravets, D.; Plaxton, CG (1996)、「ハイパーキューブ上の最も近い小さい値すべて」、IEEE Trans. Parallel and Distributed Systems、7 (5): 456–462、doi :10.1109/71.503770。
• Vuillemin, Jean (1980)、「データ構造の統一的考察」、Commun. ACM、23 (4)、ニューヨーク、NY、米国：ACM：229–239、doi：10.1145/358841.358852。