El acceso aleatorio (más precisamente y más generalmente llamado 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 aproximadamente tan fácil y eficientemente como cualquier otro, sin importar cuántos elementos puedan existir. estar en el set. En informática, normalmente se contrasta con el acceso secuencial , que requiere que los datos se recuperen en el orden en que se almacenaron.
Por ejemplo, los datos podrían almacenarse teóricamente en una única 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 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 pista y número de 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 fueran requeridos. [1] Sin embargo, pronto el término "acceso directo" ganó popularidad porque se podía recuperar directamente un registro, sin importar cuál fuera su posición. [2] Sin embargo, el atributo operativo es que el dispositivo puede acceder a cualquier registro requerido inmediatamente cuando lo solicite. Lo contrario es el acceso secuencial , donde un elemento remoto tarda más en acceder. [3]
Una ilustración típica de esta distinción es comparar un pergamino antiguo (secuencial; todo el material antes de la información necesaria debe ser desenrollado) y el libro (directo: se puede abrir inmediatamente en cualquier página arbitraria ). Un ejemplo más moderno es una cinta de casete (secuencial: hay que avanzar rápidamente a través de las canciones anteriores para llegar a las posteriores) y un CD (acceso directo: uno puede saltar a la pista deseada, sabiendo que será la que se recuperará).
En estructuras de datos , el acceso directo implica la capacidad de acceder a cualquier entrada en 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 ofrecer esta garantía además 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 clasificación de números enteros o ciertas versiones del tamiz de Eratóstenes . [4]
Otras estructuras de datos, como las listas enlazadas , sacrifican el acceso directo para permitir inserciones, eliminaciones o reordenamiento de datos eficientes. Los árboles de búsqueda binarios autoequilibrados pueden proporcionar un compromiso aceptable, donde el tiempo de acceso no es igual para todos los miembros de una colección, pero el tiempo máximo para recuperar un miembro determinado crece sólo logarítmicamente con su tamaño.