Acesso aleatório

Em ciência da computação, acesso aleatório (mais precisamente e mais geralmente chamado de acesso direto) é a capacidade de acessar um elemento arbitrário de uma sequência, em tempo igual, ou qualquer dado de uma população de elementos endereçáveis, de maneira tão fácil e eficiente quanto qualquer outro, não importa quantos elementos possam estar no conjunto. É, normalmente, contrastado com o acesso sequencial, que exige que os dados sejam recuperados na ordem em que foram armazenados. Por exemplo, os dados podem ser armazenados, nocionalmente, em uma única sequência, como uma linha, em duas dimensões, como linhas e colunas em uma superfície, ou em várias dimensões. No entanto, dadas todas as coordenadas, um programa pode acessar cada registro com a mesma rapidez e facilidade que qualquer outro. Nesse sentido, a escolha do dado é arbitrária no sentido de que, independentemente de qual item é procurado, tudo o que é necessário para encontrá-lo é o seu endereço, ou seja, as coordenadas em que ele está localizado, como sua linha e coluna (ou seu número de rastreamento e registro em uma ). A princípio, o termo "acesso aleatório" era usado porque o processo precisava ser capaz de encontrar registros, independentemente da sequência em que fossem requeridos. No entanto, logo o termo "acesso direto" ganhou preferência, pois era possível recuperar diretamente um registro, independentemente de qual fosse sua posição. O atributo operativo, no entanto, é que o dispositivo pode acessar qualquer registro necessário imediatamente sob demanda. O oposto é o acesso sequencial, onde um elemento remoto leva mais tempo para acessar. Uma ilustração típica dessa distinção é comparar um pergaminho antigo (sequencial; todo o material anterior aos dados necessários deve ser desenrolado) e o livro (direto: pode ser imediatamente aberto para qualquer página arbitrária). Um exemplo mais moderno é uma fita cassete (sequencial - é preciso avançar rapidamente nas músicas anteriores para chegar às posteriores) e um CD (acesso direto - pode-se pular para a faixa desejada, sabendo que ela seria a que foi recuperada). Nas estruturas de dados, o acesso direto implica a capacidade de acessar qualquer entrada em uma lista em tempo constante (independentemente de sua posição na lista e do tamanho da lista). Muito poucas estruturas de dados podem fazer essa garantia além das matrizes (e estruturas relacionadas, como ). O acesso direto é necessário, ou pelo menos valioso, em muitos algoritmos, como pesquisa binária, ou certas versões do crivo de Eratóstenes. Outras estruturas de dados, como listas ligadas, sacrificam o acesso direto para permitir inserções, exclusões ou reordenamentos de dados eficientes. As árvores de pesquisa binária com auto balanceamento podem fornecer um compromisso aceitável, onde o tempo de acesso não é igual para todos os membros de uma coleção, mas o tempo máximo para recuperar um determinado membro cresce apenas logaritmicamente com seu tamanho.