Loading article…
ランダムアクセス（直接アクセスとも呼ばれる）とは、シーケンス内の任意の要素に等しい時間でアクセスできる機能、またはアドレス指定可能な要素群から任意のデータに、要素数に関係なく、他のデータとほぼ同じくらい容易かつ効率的にアクセスできる機能のことです。コンピュータサイエンスでは、データが格納された順序で取得されるシーケンシャルアクセスと対比されるのが一般的です。
例えば、データは、行のような単一のシーケンス、表面上の行と列のような2次元、または複数の次元で概念的に格納される可能性があります。しかし、すべての座標が与えられれば、プログラムは各レコードに他のレコードとほぼ同じ速さと容易さでアクセスできます。この意味で、データの選択は任意です。どの項目を探す場合でも、それを見つけるために必要なのはアドレス、つまり、行と列（または磁気ドラム上のトラックとレコード番号）などの位置座標だけです。当初、「ランダムアクセス」という用語は、レコードがどのような順序で要求されても、プロセスがレコードを見つけることができなければならないという理由で使用されました。[ 1 ]しかし、レコードの位置に関係なく直接レコードを取得できるため、すぐに「直接アクセス」という用語が好まれるようになりました。[ 2 ]ただし、重要な属性は、デバイスが必要なレコードに要求に応じてすぐにアクセスできることです。反対はシーケンシャルアクセスで、リモート要素へのアクセスに時間がかかります。[ 3 ]
この違いを典型的に示す例として、古代の巻物（順次的：必要なデータより前の部分をすべて巻き戻さなければならない）と書籍（直接的：任意のページをすぐに開くことができる）を比較してみましょう。より現代的な例としては、カセットテープ（順次的：後の曲にたどり着くには前の曲を早送りしなければならない）とCD（直接アクセス：目的のトラックにスキップでき、それが取得される曲であることがわかっている）が挙げられます。
データ構造において、直接アクセスとは、リスト内の任意のエントリに定数時間でアクセスできることを意味します（リスト内の位置やリストのサイズに依存しません）。配列（および動的配列などの関連構造）以外で、この保証ができるデータ構造はごくわずかです。直接アクセスは、二分探索、整数ソート、エラトステネスの篩の特定のバージョンなど、多くのアルゴリズムで必要、または少なくとも価値があります。[ 4 ]
連結リストなどの他のデータ構造は、データの効率的な挿入、削除、または並べ替えを可能にするために、直接アクセスを犠牲にしています。自己平衡二分探索木は、許容できる妥協点を提供する可能性があります。これは、コレクションのすべてのメンバーへのアクセス時間が等しくはないものの、特定のメンバーを取得する最大時間がそのサイズに対して対数的にしか増加しないためです。