O que motiva o modelo RAM?
Parece que a maior parte da análise de algoritmo atual é feita em modelos com acesso aleatório em tempo constante, como a palavra modelo RAM. Eu não sei muito sobre física, mas de fontes populares, ouvi dizer que deve haver um limite no armazenamento de informações por volume e na velocidade de viagem de informações, então os RAMs não parecem ser fisicamente realizáveis. Os computadores modernos têm todos esses níveis de cache, o que eu diria que os torna não muito parecidos com RAM. Então, por que os algoritmos teóricos devem ser configurados na RAM?
Respostas
Deixe-me dar uma opinião diferente sobre vonbrand. Tudo o que você disse é verdade: o modelo RAM não é realista por uma série de razões e, embora seja possível defender diferentes aspectos dele, tal defesa não chega realmente ao cerne da questão.
O cerne da questão - e a resposta à sua pergunta - é que o modelo RAM é a melhor coisa que temos. Comparado a outros modelos aceitos, ele modela com mais precisão a computação da vida real. Em particular, o motivo pelo qual adotamos o modelo RAM foi principalmente uma resposta às máquinas de Turing, pois descobrimos que o uso de máquinas de Turing torna os problemas artificialmente difíceis de resolver em termos de complexidade de tempo. O modelo RAM claramente resolve este problema gritante e, portanto, foi aceito, embora esteja longe de ser perfeito.
Um exemplo clássico que ilustra o problema flagrante com as máquinas de Turing é o problema da igualdade das strings: dada entrada
$$ w_1 \# w_2$$
Onde $w_1, w_2$ são sequências binárias e $\#$ é um separador, determinando se $w_1 = w_2$. Pode ser mostrado que qualquer máquina de Turing para o problema de igualdade leva$O(n^2)$Tempo. Isso é desconfortável, porque as máquinas de Turing são o que todos pensam como o modelo universal de computação - ainda que nenhum engenheiro de software ou pesquisador de algoritmos acredite que a igualdade das strings realmente$O(n^2)$Tempo. Então, o que dá? A igualdade das strings deve ser linear, então inventamos um novo modelo onde ela está, e a melhor solução disponível agora são as máquinas de RAM de palavras.
Talvez algum dia no futuro possamos apresentar um modelo melhor - um que seja simples, conceitualmente claro e que aprimore a RAM em sua capacidade de modelar a complexidade computacional da vida real. Por enquanto, só podemos nos contentar com o melhor que temos.
Como uma primeira aproximação, você pode aproveitar o tempo para acessar uma palavra na memória como constante, independente dos acessos anteriores. Ou seja, o modelo de RAM.
Você está certo, as máquinas de hoje não são muito semelhantes à RAM, vale a pena (mesmo generosamente) organizar o acesso aos dados para ser o mais sequencial possível ou espremer o último pedaço de informação de um (curto) segmento de memória antes de manipular nas próximas. Mas você raramente tem liberdade para fazer isso, seus acessos à memória são essencialmente aleatórios e o modelo não está muito longe da verdade. Além disso, as máquinas de hoje têm muito mais de uma CPU, o modelo possui apenas uma. E então há o processamento vetorial (fazendo a mesma operação em um vetor de dados, não um por um) que as "instruções multimídia" (e ainda mais usando placas gráficas para processamento) fazem.
Um pouco de discussão é dada, por exemplo, por Khoung's Binary search é um caso patológico para caches . Como você pode ver, analisar até mesmo algoritmos simples e bem compreendidos em modelos de tempo de acesso à memória mais realistas é assustador.
O modelo de RAM é motivado pela análise assintótica de algoritmos projetados como cálculos na memória de thread único.
Otimizar o desempenho para um conjunto de instruções específico, caches e outros enfeites é uma coisa. A outra coisa é estar preparado para o crescimento do tamanho do problema. Para estimar o quão bem o seu algoritmo in-memory dimensiona, você provavelmente deseja ignorar pequenos fatores e se concentrar em grandes$\mathcal{O}$notação. grande$\mathcal{O}$ não vai otimizar tudo para você, mas pelo menos pode dizer que sua solução se adapta bem (ou que você deve tentar algo diferente).
RAM assume pequeno conjunto de instruções fixas, onde cada operação trabalha em $\mathcal{O}(1)$. Observe que este é um bom modelo se nos preocupamos apenas com o crescimento assintótico:
O conjunto de instruções de uma CPU moderna não é pequeno, mas podemos fingir que realmente é. Esses códigos operacionais adicionais não fazem diferença no grande$\mathcal{O}$ notação.
CPUs podem ter instruções cujo tempo de execução depende da entrada. Novamente, podemos ignorá-los, porque podemos modelá-los usando instruções mais simples, sem afetar grandes$\mathcal{O}$complexidade. O mesmo vale para os níveis de cache: seu desempenho ainda é limitado por alguma pequena constante, portanto, funcionam em$\mathcal{O}(1)$ por definição.
Sim, você não pode acessar a memória em tempo constante se ela continuar crescendo. Felizmente, isso nunca é necessário graças ao bom senso. Ninguém está indexando toda a Internet na memória não persistente de uma máquina solitária de um único thread.