ワードラム

理論計算機科学において、ワードRAM（ワードランダムアクセスマシン）モデルは、ランダムアクセスマシンがwビットのワードに対して算術演算とビット演算を行う計算モデルである。マイケル $・$ フレッドマンとダン・ウィラードは、Cのようなプログラミング言語をシミュレートするために1990年にこれを作成した。^[¹^]

モデル

ワード RAM モデルは、ランダムアクセスマシンに似た抽象マシンですが、メモリとワード長が有限です。最大 $w$ ビットのワードで動作し、最大で 10 ビットまでの整数を格納できます。 $2^{w}-1$ モデルは単語のサイズが問題のサイズと一致すると仮定しているため、つまり、サイズ $n$ の問題の場合、 $w\geq \log n$ RAMモデルは、二分法モデルです。^{[ 2 ]}このモデルでは、算術演算と論理シフトを含むビット演算の両方を定数時間で実行できます（モデルを使用するアルゴリズムや証明で想定される正確な命令セットは異なる場合があります）。

アルゴリズムとデータ構造

ワード RAM モデルでは、整数のソートはかなり効率的に行うことができます。Yijie Han とMikkel Thorup は、整数を (ビッグ O 表記で)の期待時間でソートするランダム化アルゴリズムを作成しました。 $O(n{\sqrt {\log \log n}})$ ^{[ 3 ]}一方で、 Hanは実行時間付きの決定論的バリアントも作成した。 $O(n\log \log n)$ [ ⁴^]

動的な先行問題も、ワード RAM モデルでよく分析されており、このモデルの本来の動機でした。ダン・ウィラードは、 y-fast トライを使用してこれを解決しました。 $O(\log w)$ 時間、あるいはより正確には、 $O(\log \log U)$ ここで、 $U$ は格納される値の上限です。^{[ 5 ]}マイケル・フレッドマンとウィラードも融合木を使用して問題を解決しました。 $O(\log _{w}n)$ 時間。^{[ 1 ]}指数探索木を使用すると、クエリは $O({\sqrt {\log n/\log \log n}})$ [ ⁶^]

「RAMモデル」という単語に関する追加の結果は、範囲検索に関する記事に記載されています。

ワードRAMアルゴリズムに適用可能な下限は、セルプローブモデルで証明されることが多い。

参考文献

1 2 Fredman, Michael ; Willard, Dan (1990). 「融合木による情報理論的障壁の突破」. Symposium on Theory of Computing : 1– 7.
↑実際には、通常は $nが$ 以下より小さいと $2w$ それによって、対象となるデータ構造は $w$ ビットのアドレスでインデックス付けできるようになります。
↑ Han, Yijie; Thorup, M. (2002), "Integer sorting in $O($ $n$ $\sqrt$ $log log$ $n$ $)$ expected time and linear space", Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002) , IEEE Computer Society, pp. 135– 144, CiteSeerX 10.1.1.671.5583 , doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0
↑ Han, Yijie (2004), "Deterministic sorting in $O$ $($ $n$ $log log$ $n$ $)$ time and linear space", Journal of Algorithms , 50 (1): 96– 105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585
↑ Willard, Dan E. (1983). "Log-logarithmic worst-case range queries are possible in space Θ (N)". Information Processing Letters . 17 (2): 81– 84. doi : 10.1016/0020-0190(83)90075-3 .
↑ Andersson, Arne; Thorup, Mikkel (2007). "指数探索木による動的順序付きセット". Journal of the ACM . 54 (3): 13. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 .

[Fredman90-1] 1 2 Fredman, Michael ; Willard, Dan (1990). 「融合木による情報理論的障壁の突破」. Symposium on Theory of Computing : 1– 7.

[2] 実際には、通常は $nが$ 以下より小さいと $2w$ それによって、対象となるデータ構造は $w$ ビットのアドレスでインデックス付けできるようになります。

[Han02-3] Han, Yijie; Thorup, M. (2002), "Integer sorting in $O($ $n$ $\sqrt$ $log log$ $n$ $)$ expected time and linear space", Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002) , IEEE Computer Society, pp. 135– 144, CiteSeerX 10.1.1.671.5583 , doi : 10.1109/SFCS.2002.1181890 , ISBN 978-0-7695-1822-0

[Han04-4] Han, Yijie (2004), "Deterministic sorting in $O$ $($ $n$ $log log$ $n$ $)$ time and linear space", Journal of Algorithms , 50 (1): 96– 105, doi : 10.1016/j.jalgor.2003.09.001 , MR 2028585

[5] Willard, Dan E. (1983). "Log-logarithmic worst-case range queries are possible in space Θ (N)". Information Processing Letters . 17 (2): 81– 84. doi : 10.1016/0020-0190(83)90075-3 .

[6] Andersson, Arne; Thorup, Mikkel (2007). "指数探索木による動的順序付きセット". Journal of the ACM . 54 (3): 13. arXiv : cs/0210006 . doi : 10.1145/1236457.1236460 .

[

[ 2 ]

[ 3 ]

4

[ 5 ]

6

ワードラム

モデル

アルゴリズムとデータ構造

関連項目

参考文献

関連するトピック

理論計算機科学

マイケル

マン

ダン