Acceso aleatorio

El acceso aleatorio (también llamado acceso directo ) es la capacidad de acceder a cualquier elemento de una secuencia en el mismo tiempo, o a cualquier dato de un conjunto de elementos direccionables , con la misma facilidad y eficiencia que cualquier otro, independientemente del número de elementos 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 podrían almacenarse conceptualmente 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 con la misma rapidez y facilidad que a cualquier otro. En este sentido, la elección del dato es arbitraria, ya que, independientemente del elemento que 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 ). Inicialmente, se utilizó el término "acceso aleatorio" porque el proceso debía ser capaz de encontrar registros sin importar el orden en que se requirieran. ^{[ 1 ]} Sin embargo, pronto se popularizó el término "acceso directo" porque se podía recuperar un registro directamente, independientemente de su posición. ^{[ 2 ]} El atributo fundamental, sin embargo, es que el dispositivo puede acceder a cualquier registro requerido inmediatamente bajo demanda. Lo opuesto es el acceso secuencial , donde el acceso a un elemento remoto lleva más tiempo. ^{[ 3 ]}

Un ejemplo típico de esta distinción es comparar un pergamino antiguo (secuencial; todo el material anterior a los datos necesarios debe desenrollarse) con un libro (directo: se puede abrir inmediatamente en cualquier página ). Un ejemplo más moderno es una cinta de casete (secuencial : hay que avanzar rápidamente por 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 reproduzca).

En estructuras de datos , el acceso directo implica la capacidad de acceder a cualquier elemento de una lista en tiempo constante (independientemente de su posición en la lista y del tamaño de la misma). Muy pocas estructuras de datos pueden garantizar esto, aparte de los arreglos (y estructuras relacionadas como los arreglos dinámicos ). 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 de datos eficientes. Los árboles de búsqueda binaria autoequilibrados pueden ofrecer una solución intermedia 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 solo logarítmicamente con su tamaño.

• flujo de datos
• Máquina de acceso aleatorio
• Memoria de acceso aleatorio, aunque la memoria caché y la memoria virtual hacen que ya no sea un acceso verdaderamente aleatorio.
• Localidad de referencia