El acceso aleatorio (denominado de forma más precisa y general acceso directo ) es la capacidad de acceder a un elemento arbitrario de una secuencia en el mismo tiempo o a cualquier dato de una población de elementos direccionables con la misma facilidad y eficiencia que cualquier otro, sin importar cuántos elementos pueda haber en el conjunto. En informática, se suele contrastar con el acceso secuencial , que requiere que los datos se recuperen en el orden en que se almacenaron.
Por ejemplo, los datos pueden almacenarse nocionalmente en una sola secuencia como una fila, en dos dimensiones como filas y columnas en una superficie, o en múltiples dimensiones. Sin embargo, dadas todas las coordenadas, un programa puede acceder a cada registro tan rápida y fácilmente como a cualquier otro. En este sentido, la elección del dato es arbitraria en el sentido de que no importa qué elemento se busque, todo lo que se necesita para encontrarlo es su dirección, es decir, las coordenadas en las que se encuentra, como su fila y columna (o su número de pista y registro en un tambor magnético ). Al principio, se utilizó el término "acceso aleatorio" porque el proceso tenía que ser capaz de encontrar registros sin importar en qué secuencia se requirieran. [1] Sin embargo, pronto ganó popularidad el término "acceso directo" porque uno podía recuperar directamente un registro, sin importar cuál pudiera ser su posición. [2] El atributo operativo, sin embargo, es que el dispositivo puede acceder a cualquier registro requerido inmediatamente cuando se lo solicita. Lo opuesto es el acceso secuencial , donde un elemento remoto tarda más tiempo en acceder. [3]
Un ejemplo típico de esta distinción es comparar un pergamino antiguo (secuencial: se debe desenrollar todo el material anterior a los datos necesarios) y un libro (directo: se puede abrir inmediatamente en cualquier página arbitraria ). Un ejemplo más moderno es una cinta de casete (secuencial: se debe avanzar rápidamente a través de las canciones anteriores para llegar a las posteriores) y un CD (acceso directo: se puede saltar a la pista deseada, sabiendo que será la que se recuperará).
En las estructuras de datos , el acceso directo implica la capacidad de acceder a cualquier entrada de una lista en tiempo constante (independientemente de su posición en la lista y del tamaño de la lista). Muy pocas estructuras de datos pueden hacer esta garantía aparte de las matrices (y estructuras relacionadas como las matrices dinámicas ). El acceso directo es necesario, o al menos valioso, en muchos algoritmos como la búsqueda binaria , la ordenación de enteros o ciertas versiones de la criba de Eratóstenes . [4]
Otras estructuras de datos, como las listas enlazadas , sacrifican el acceso directo para permitir inserciones, eliminaciones o reordenamientos eficientes de los datos. Los árboles binarios de búsqueda autoequilibrados pueden proporcionar un compromiso aceptable, en el que el tiempo de acceso no es igual para todos los miembros de una colección, sino que el tiempo máximo para recuperar un miembro determinado crece solo logarítmicamente con su tamaño.