Acceso aleatorio

Acceso aleatorio en comparación con el acceso secuencial

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 cualquier dato de una población de elementos direccionables con la misma facilidad y eficiencia que cualquier otro, sin importar cuántos elementos haya en el conjunto. 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 pueden almacenarse teóricamente en una sola secuencia, como una fila, en dos dimensiones, como filas y columnas en una superficie, o en varias dimensiones. Sin embargo, dadas todas las coordenadas, un programa puede acceder a cada registro con la misma rapidez y facilidad que cualquier otro. En este sentido, la elección del dato es arbitraria en el sentido de que sea cual sea el elemento que se busque, lo único 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, el término "acceso aleatorio" se utilizó porque el proceso tenía que ser capaz de encontrar registros sin importar en qué secuencia se requerían. Sin embargo, pronto el término "acceso directo" ganó favor porque uno podía recuperar directamente un registro, sin importar cuál podría ser su posición. El atributo operativo, sin embargo, es que el dispositivo puede acceder a cualquier registro requerido inmediatamente bajo demanda. Lo contrario es el acceso secuencial, donde un elemento remoto tarda más tiempo en acceder.

Una ilustración típica de esta distinción es comparar un pergamino antiguo (secuencial; se debe desenrollar todo el material anterior a los datos necesarios) y el 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 por las canciones anteriores para llegar a las posteriores) y un CD (acceso directo: se puede saltar a la pista deseada, sabiendo que sería la recuperada).

En las 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 garantizar esta garantía que no sean matrices (y estructuras relacionadas, como matrices dinámicas). Se requiere acceso directo, o al menos es valioso, en muchos algoritmos, como la búsqueda binaria, la clasificación de enteros o ciertas versiones del tamiz de Eratóstenes.

Otras estructuras de datos, como las listas enlazadas, sacrifican el acceso directo para permitir inserciones, eliminaciones o reordenaciones 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 solo logarítmicamente con su tamaño.