RAMモデルの動機は何ですか？
今日のアルゴリズム分析のほとんどは、ワードRAMモデルなど、一定時間のランダムアクセスを持つモデルで行われているようです。物理についてはよくわかりませんが、人気のある情報源から、ボリュームあたりの情報ストレージと情報の移動速度に制限があると聞いているため、RAMは物理的に実現できないようです。最近のコンピューターにはこれらすべてのキャッシュレベルがあり、RAMのようなものではないと思います。では、なぜ理論的アルゴリズムをRAMに設定する必要があるのでしょうか。
回答
vonbrandとは違う見方をさせてください。あなたが言ったことはすべて真実です。RAMモデルはいくつかの理由で現実的ではなく、そのさまざまな側面を防御することは可能ですが、そのような防御は実際には問題の核心にはなりません。
問題の核心-そしてあなたの質問への答え-はRAMモデルが私たちが持っている最高のものであるということです。受け入れられている他のモデルと比較して、実際の計算をより正確にモデル化します。特に、RAMモデルを採用した理由は、チューリングマシンを使用すると時間計算量の点で人為的に解決が困難になることがわかったため、主にチューリングマシンへの対応でした。RAMモデルはこの明白な問題を明確に解決しているため、完全にはほど遠いものの、受け入れられています。
チューリングマシンの明白な問題を説明する古典的な例は、文字列の同等性の問題です：与えられた入力
$$ w_1 \# w_2$$
どこ $w_1, w_2$ バイナリシーケンスであり、 $\#$ はセパレータであり、 $w_1 = w_2$。平等問題のためのチューリングマシンはどれもかかることを示すことができます$O(n^2)$時間。チューリングマシンは誰もが計算の普遍的なモデルと考えているため、これは不快ですが、ソフトウェアエンジニアやアルゴリズム研究者は、文字列の同等性が実際に必要であるとは考えていません。$O(n^2)$時間。では、何が得られるのでしょうか？文字列の等式は線形である必要があるため、新しいモデルを発明しました。現在利用可能な最善のソリューションは、ワードRAMマシンです。
おそらく将来のある日、より良いモデルを思いつくでしょう。それは、単純で、概念的に明確で、実際の計算の複雑さをモデル化する能力においてRAMを改善するものです。今のところ、私たちは自分たちが持っている最善のものでしかやり遂げることができません。
最初の大まかな概算として、先行するアクセスとは関係なく、メモリ内の単語に定数としてアクセスするのに時間をかけることができます。つまり、RAMモデルです。
確かに、今日のマシンはRAMに似ていません。データアクセスを可能な限りシーケンシャルに整理したり、（短い！）メモリセグメントから情報の最後のビットを絞り出してから操作したりすることで（見事にさえ）報われます次。しかし、そうする余地はめったにありません。メモリアクセスは本質的にランダムであり、モデルは真実からそれほど遠くありません。さらに、今日のマシンには複数のCPUが搭載されており、モデルには1つしか搭載されていません。そして、「マルチメディア命令」（さらには処理にグラフィックカードを使用）と同じベクトル処理（データのベクトルに対して1つずつではなく同じ操作を実行）があります。
たとえば、Khoungのバイナリ検索はキャッシュの病理学的ケースです。ご覧のとおり、より現実的なメモリアクセス時間モデルの下で、単純でよく理解されているアルゴリズムでさえ分析するのは困難です。
RAMモデルは、シングルスレッドのメモリ内計算として設計されたアルゴリズムの漸近解析によって動機付けられています。
特定の命令セット、キャッシュなどのパフォーマンスを最適化することは1つのことです。もう1つは、問題のサイズが大きくなることに備えることです。インメモリアルゴリズムのスケーリングを見積もるには、小さな要素を無視して大きな要素に焦点を当てたいと思うでしょう。$\mathcal{O}$表記。大きい$\mathcal{O}$ すべてを最適化するわけではありませんが、少なくとも、ソリューションの拡張性が高い（または別の方法を試す必要がある）ことがわかる場合があります。
RAMは、各操作が機能する小さな固定命令セットを想定しています。 $\mathcal{O}(1)$。これは、漸近的な成長のみを考慮する場合に適したモデルであることに注意してください。
現代のCPUの命令セットは小さくはありませんが、実際にそうであるように見せかけることができます。これらの追加のオペコードは、大きな違いはありません$\mathcal{O}$ 表記。
CPUには、実行時間が入力に依存する命令がある場合があります。繰り返しますが、大きな影響を与えることなく、より単純な命令を使用してモデル化できるため、無視できます。$\mathcal{O}$複雑。キャッシュレベルについても同じことが言えます。それらのパフォーマンスはまだいくつかの小さな定数によって制限されているため、$\mathcal{O}(1)$ 定義により。
はい、メモリが増え続けると、一定の時間でメモリにアクセスすることはできません。幸いなことに、これは常識のおかげで必要になることはありません。孤独なシングルスレッドマシンの非永続メモリにインターネット全体のインデックスを作成している人は誰もいません。