¿Qué motiva el modelo RAM?
Parece que la mayoría de los análisis de algoritmos actuales se realizan en modelos con acceso aleatorio en tiempo constante, como el modelo de RAM de palabras. No sé mucho sobre física, pero de fuentes populares he escuchado que se supone que hay un límite en el almacenamiento de información por volumen y en la velocidad de viaje de la información, por lo que las RAM no parecen ser físicamente realizables. Las computadoras modernas tienen todos estos niveles de caché, lo que yo diría que los hace no muy parecidos a la RAM. Entonces, ¿por qué deberían establecerse algoritmos teóricos en RAM?
Respuestas
Permítanme darle una opinión diferente a la de vonbrand. Todo lo que dijiste es cierto: el modelo RAM no es realista por varias razones, y si bien es posible defender diferentes aspectos del mismo, tal defensa no llega realmente al meollo del asunto.
El meollo del asunto, y la respuesta a su pregunta, es que el modelo RAM es lo mejor que tenemos. En comparación con otros modelos aceptados, modela con mayor precisión el cálculo de la vida real. En particular, la razón por la que adoptamos el modelo RAM fue principalmente una respuesta a las máquinas de Turing, ya que descubrimos que el uso de máquinas de Turing conduce a que los problemas sean artificialmente difíciles de resolver en términos de complejidad temporal. El modelo RAM resuelve claramente este problema evidente y, por lo tanto, ha sido aceptado, aunque está lejos de ser perfecto.
Un ejemplo clásico que ilustra el problema evidente con las máquinas de Turing es el problema de la igualdad de cadenas: entrada dada
$$ w_1 \# w_2$$
dónde $w_1, w_2$ son secuencias binarias y $\#$ es un separador, determinando si $w_1 = w_2$. Se puede demostrar que cualquier máquina de Turing para el problema de igualdad toma$O(n^2)$hora. Esto es incómodo, porque las máquinas de Turing son lo que todos consideran el modelo universal de computación; sin embargo, ningún ingeniero de software o investigador de algoritmos cree que la igualdad de cadenas realmente requiere$O(n^2)$hora. Entonces, ¿qué pasa? La igualdad de cadenas debe ser lineal, por lo que inventamos un nuevo modelo donde está, y la mejor solución disponible en este momento son las máquinas RAM de palabras.
Quizás algún día en el futuro se nos ocurra un modelo mejor, uno que sea simple, conceptualmente claro y mejore la capacidad de la RAM para modelar la complejidad computacional de la vida real. Por ahora, solo podemos conformarnos con lo mejor que tenemos.
Como primera aproximación aproximada, puede tomarse el tiempo para acceder a una palabra en la memoria como constante, independientemente de los accesos anteriores. Es decir, el modelo RAM.
Tiene razón, las máquinas de hoy en día no son similares a la RAM, vale la pena (incluso muy bien) organizar el acceso a los datos para que sea lo más secuencial posible o extraer el último bit de información de un segmento de memoria (¡corto!) Antes de manipularlo. el siguiente. Pero rara vez tiene el margen para hacerlo, sus accesos a la memoria son esencialmente aleatorios y el modelo no está tan lejos de la verdad. Además, las máquinas actuales tienen muchas más de una CPU, el modelo solo tiene una. Y luego está el procesamiento de vectores (haciendo la misma operación en un vector de datos, no uno por uno) como lo hacen las "instrucciones multimedia" (y aún más usando tarjetas gráficas para el procesamiento).
La búsqueda binaria de Khoung da un poco de discusión, por ejemplo, es un caso patológico de cachés . Como puede ver, analizar incluso algoritmos simples y bien entendidos bajo modelos de tiempo de acceso a la memoria más realistas es abrumador.
El modelo RAM está motivado por el análisis asintótico de algoritmos que están diseñados como cálculos en memoria de un solo subproceso.
Optimizar el rendimiento para conjuntos de instrucciones específicos, cachés y todo eso es una cosa. La otra cosa es estar preparado para el crecimiento del tamaño del problema. Para estimar qué tan bien se escala su algoritmo en memoria, probablemente desee ignorar los factores pequeños y concentrarse en los grandes$\mathcal{O}$notación. Grande$\mathcal{O}$ no va a optimizar todo para usted, pero al menos puede decirle que su solución se adapta bien (o que debería probar algo diferente).
RAM asume un pequeño conjunto de instrucciones fijas, donde cada operación funciona en $\mathcal{O}(1)$. Tenga en cuenta que este es un buen modelo si solo nos preocupamos por el crecimiento asintótico:
El conjunto de instrucciones de una CPU moderna no es pequeño, pero podemos fingir que realmente lo es. Esos códigos de operación adicionales no hacen diferencia en los grandes$\mathcal{O}$ notación.
Las CPU pueden tener instrucciones cuyo tiempo de ejecución depende de la entrada. Nuevamente, podemos ignorarlos, porque podemos modelarlos usando instrucciones más simples sin afectar grandes$\mathcal{O}$complejidad. Lo mismo ocurre con los niveles de caché: su rendimiento todavía está limitado por una pequeña constante, por lo que funcionan en$\mathcal{O}(1)$ por definición.
Sí, no puede acceder a la memoria en tiempo constante si sigue creciendo. Afortunadamente, esto nunca es necesario gracias al sentido común. Nadie está indexando todo Internet en la memoria no persistente de una máquina solitaria de un solo subproceso.