El límite de memoria se refiere a una situación en la que el tiempo necesario para completar un problema computacional determinado se decide principalmente por la cantidad de memoria libre necesaria para almacenar los datos de trabajo . Esto contrasta con los algoritmos que están limitados por el cálculo , donde la cantidad de pasos de cálculo elementales es el factor decisivo.
Los límites de memoria y de cálculo a veces se pueden negociar entre sí, por ejemplo, guardando y reutilizando resultados preliminares o utilizando tablas de búsqueda .
Las funciones limitadas por la memoria y las funciones de memoria están relacionadas en el sentido de que ambas implican un acceso extenso a la memoria, pero existe una distinción entre las dos.
Las funciones de memoria utilizan una técnica de programación dinámica llamada memorización para aliviar la ineficiencia de la recursión que podría ocurrir. Se basa en la idea simple de calcular y almacenar soluciones a subproblemas para que las soluciones se puedan reutilizar más tarde sin tener que volver a calcular los subproblemas . El ejemplo más conocido que aprovecha la memorización es un algoritmo que calcula los números de Fibonacci . El siguiente pseudocódigo utiliza la recursión y la memorización, y se ejecuta en tiempo de CPU lineal :
Fibonacci ( n ) { para i = 0 a n -1 resultados [ i ] = -1 // -1 significa indefinido devuelve Fibonacci_Results ( resultados , n ); } Fibonacci_Results ( resultados , n ) { if ( resultados [ n ] != -1 ) // Si ya se ha resuelto antes, devuelve resultados [ n ] // búscalo. if ( n == 0 ) val = 0 else if ( n == 1 ) val = 1 else val = Fibonacci_Results ( resultados , n -2 ) + Fibonacci_Results ( resultados , n -1 ) resultados [ n ] = val // Guarda este resultado para reutilizarlo. devolver val } Compare lo anterior con un algoritmo que utiliza solo recursión y se ejecuta en tiempo de CPU exponencial :
Recursive_Fibonacci ( n ) { si ( n == 0 ) devuelve 0 si ( n == 1 ) devuelve 1 devuelve Fibonacci recursivo ( n -1 ) + Fibonacci recursivo ( n -2 ) } Si bien el algoritmo exclusivamente recursivo es más simple y elegante que el algoritmo que utiliza recursión y memorización, este último tiene una complejidad temporal significativamente menor que el primero.
El término "función limitada por la memoria" ha surgido recientemente y se utiliza principalmente para describir una función que utiliza XOR y consiste en una serie de cálculos en los que cada cálculo depende del cálculo anterior. Mientras que las funciones de memoria han sido durante mucho tiempo un actor importante en la mejora de la complejidad temporal, las funciones limitadas por la memoria han visto muchas menos aplicaciones. Recientemente [¿ cuándo? ] , sin embargo, los científicos han propuesto un método que utiliza funciones limitadas por la memoria como un medio para disuadir a los spammers de abusar de los recursos, lo que podría ser un gran avance en esa área.
Las funciones limitadas por la memoria podrían ser útiles en un sistema de prueba de trabajo que podría disuadir el spam , que se ha convertido en un problema de proporciones epidémicas en Internet .
En 1992, las científicas de investigación de IBM Cynthia Dwork y Moni Naor publicaron un artículo en CRYPTO 1992 titulado Pricing via Processing or Combatting Junk Mail (Fijación de precios mediante el procesamiento o la lucha contra el correo basura) , [1] en el que sugerían la posibilidad de utilizar funciones limitadas por la CPU para disuadir a los abusadores de enviar correo basura. El plan se basaba en la idea de que los usuarios de ordenadores tienen muchas más probabilidades de abusar de un recurso si el coste de abusar de él es insignificante: la razón subyacente por la que el correo basura se ha vuelto tan desenfrenado es que enviar un correo electrónico tiene un coste minúsculo para los spammers.
Dwork y Naor propusieron que el spam podría reducirse inyectando un costo adicional en forma de un costoso cálculo de CPU : las funciones limitadas por la CPU consumirían recursos de CPU en la máquina del remitente para cada mensaje, evitando así que se envíen grandes cantidades de spam en un período corto.
El esquema básico que protege contra los abusos es el siguiente:
se da un remitente, un destinatario y un mensaje de correo electrónico. Si el destinatario ha aceptado de antemano recibir un correo electrónico del remitente, el mensaje se transmite de la forma habitual. De lo contrario, el remitente calcula una función G(Mensaje) y envía (Mensaje, G(Mensaje)) al destinatario. El destinatario comprueba si lo que recibe del remitente tiene el formato (Mensaje, G(Mensaje)) . Si es así, el destinatario acepta el mensaje. De lo contrario, el destinatario rechaza el mensaje.
La función G() se selecciona de forma que la verificación por parte del Destinatario sea relativamente rápida (p. ej., que tarde un milisegundo) y que el cálculo por parte del Remitente sea algo lento (que requiera al menos varios segundos). Por lo tanto, se desalentará al Remitente de enviar un Mensaje a varios destinatarios sin acuerdos previos: el costo en términos de tiempo y recursos computacionales de calcular G() repetidamente será muy prohibitivo para un spammer que pretenda enviar muchos millones de correos electrónicos.
El principal problema de utilizar el esquema anterior es que las CPU rápidas calculan mucho más rápido que las CPU lentas. Además, los sistemas informáticos de gama alta también tienen tuberías sofisticadas y otras características ventajosas que facilitan los cálculos. Como resultado, un spammer con un sistema de última generación difícilmente se verá afectado por tal disuasión, mientras que un usuario típico con un sistema mediocre se verá afectado negativamente. Si un cálculo tarda unos segundos en un PC nuevo , puede tardar un minuto en un PC antiguo y varios minutos en un PDA , lo que puede ser una molestia para los usuarios de PC antiguos, pero probablemente inaceptable para los usuarios de PDA. La disparidad en la velocidad de la CPU del cliente constituye uno de los principales obstáculos para la adopción generalizada de cualquier esquema basado en una función limitada a la CPU. Por lo tanto, los investigadores se preocupan por encontrar funciones que la mayoría de los sistemas informáticos evalúen aproximadamente a la misma velocidad, de modo que los sistemas de alta gama puedan evaluar estas funciones algo más rápido que los sistemas de gama baja (de 2 a 10 veces más rápido, pero no de 10 a 100 veces más rápido), como podrían implicar las disparidades en la CPU. Estas proporciones son lo suficientemente " igualitarias " para las aplicaciones previstas: las funciones son eficaces para desalentar los abusos y no añaden un retraso prohibitivo a las interacciones legítimas, en una amplia gama de sistemas.
El nuevo enfoque igualitario consiste en confiar en funciones limitadas por la memoria. Como se ha dicho antes, una función limitada por la memoria es una función cuyo tiempo de cálculo está dominado por el tiempo empleado en acceder a la memoria. Una función limitada por la memoria accede a ubicaciones en una gran región de la memoria de una forma impredecible, de modo que el uso de cachés no resulta eficaz. En los últimos años, la velocidad de la CPU ha crecido drásticamente, pero ha habido un progreso comparativamente pequeño en el desarrollo de una memoria principal más rápida. Dado que las relaciones de latencia de la memoria de las máquinas construidas en los últimos cinco años no suelen ser mayores que dos, y casi siempre menores que cuatro, la función limitada por la memoria será igualitaria para la mayoría de los sistemas en el futuro previsible.