ランダムアクセス

ランダム アクセス(より正確には、より一般的には直接アクセスと呼ばれます) とは、セット内の要素の数に関係なく、シーケンスの任意の要素に同じ時間でアクセスしたり、アドレス指定可能な要素の集合から任意のデータに他の要素とほぼ同じくらい簡単かつ効率的にアクセスしたりする機能です。コンピューター サイエンスでは、通常、データを格納された順序で取得する必要があるシーケンシャル アクセスと対比されます。

たとえば、データは、概念的には行のような単一のシーケンス、表面上の行と列のような 2 次元、または複数の次元に格納される可能性があります。ただし、すべての座標が与えられれば、プログラムは各レコードに他のレコードとほぼ同じくらい迅速かつ簡単にアクセスできます。この意味では、データの選択は任意であり、どの項目を検索するかに関係なく、それを見つけるために必要なのは、そのアドレス、つまり行と列 (または磁気ドラム上のトラックとレコード番号)などの、その項目が配置されている座標だけです。最初は、プロセスがレコードをどのようなシーケンスで要求されても見つけることができなければならなかったため、「ランダム アクセス」という用語が使用されました。^[1]しかし、すぐに「直接アクセス」という用語が好まれるようになりました。これは、レコードの位置に関係なく、レコードを直接取得できるためです。^[2]ただし、実際の属性は、デバイスが要求に応じて必要なレコードにすぐにアクセスできることです。その反対は、リモート要素へのアクセスに長い時間がかかるシーケンシャル アクセスです。 ^[3]

この違いの典型的な例は、古代の巻物（順次的。必要なデータより前の資料はすべて広げなければならない）と本（直接的。任意のページにすぐに開くことができる）を比較することです。より現代的な例としては、カセットテープ（順次的。後の曲を聴くには前の曲を早送りする必要がある）とCD（直接アクセス。必要なトラックにスキップでき、それが取得されるトラックであることがわかっている）があります。

データ構造において、直接アクセスとは、リスト内の任意のエントリに一定時間でアクセスできることを意味します（リスト内の位置やリストのサイズとは無関係）。配列（および動的配列などの関連構造）以外でこれを保証できるデータ構造はほとんどありません。直接アクセスは、二分探索、整数ソート、エラトステネスのふるいの特定のバージョンなど、多くのアルゴリズムで必須、または少なくとも価値があります。^[4]

リンク リストなどの他のデータ構造では、データの効率的な挿入、削除、または並べ替えを可能にするために、直接アクセスが犠牲になっています。自己バランス型バイナリ検索ツリーは、コレクションのすべてのメンバーのアクセス時間が等しくないが、特定のメンバーを取得する最大時間がそのメンバーのサイズに対して対数的にしか増加しない場合に、許容できる妥協案を提供する可能性があります。

• データストリーム
• ランダムアクセスマシン
• ランダム アクセス メモリですが、キャッシュと仮想メモリにより、真のランダム アクセスではなくなります。
• 参照の地域