La historia de un problema: el recordatorio de JavaScript más corto

Fue por la tarde, en la víspera de la conferencia anual HolyJS en San Petersburgo. Nuestra empresa ha sido patrocinador durante varios años: en consecuencia, también tiene su propio stand con interesantes intereses para la mente inquisitiva de los desarrolladores interesados. Cuando el plato principal estuvo listo y todas las tareas fueron revisadas y completadas por abogados, decidí lanzar a mis colegas algo más de comida intelectual por la noche:

Escriba un recordatorio: una función de decorador que guarda los resultados de ejecutar una función ajustada para evitar cálculos repetidos. Tienes solo 50 caracteres.

El lenguaje es, por supuesto, JavaScript . La tarea en sí es un clásico, pero el límite de 50 caracteres se convirtió en un verdadero desafío.

En los descansos del primer día de la conferencia, discutimos opciones para lograr el objetivo, reduciendo gradualmente la respuesta. Todo el bombo se coronó con la idea de compartir la tarea con todos los participantes de la conferencia, y en el segundo día visualizamos la tarea (ver el apéndice) y comenzamos a distribuir formularios a quienes quisieran. Como resultado, obtuvimos alrededor de 40 soluciones y una vez más nos convencimos de la extraordinaria comunidad de desarrolladores de js, pero el registro de Dmitry Kataev (SEMrush) de 53 caracteres permaneció. ¡Vamos a resolverlo!

Implementación habitual

function memoize(f) { let cache = {}; return function ret() { let key = JSON.stringify(arguments); if (!cache.hasOwnProperty(key)) { cache[key] = f.apply(this, arguments); } return cache[key]; } } 

Resultado: ~ 190 caracteres

• memorizar - nuestro recordatorio
• f - decorada, función envuelta
• ret - función resultante

Para obtener la respuesta, el tamaño de la función, utilizamos:

 memoize.toString().replace(/\s+/g, ' ').length 

Al evaluar el tamaño de una función, prestamos atención a su cuerpo y a una lista de parámetros. Si la función es anónima, la declaración no se tiene en cuenta.

Pruebas simples para evaluar la salud después del abuso:

 const log = memoize(console.log); const inc = memoize(o => ox + 1); 

A continuación, el resultado de cada implementación estará marcado por el resultado de la prueba.

Implementación neta

En primer lugar, quiero deshacerme de la Declaración de funciones a favor de la función de flecha, ya que no estamos interesados ​​en este contexto, no apelamos a argumentos, y como constructores no tenemos la intención de llamar a nuevos . Al mismo tiempo, reduciremos los nombres de las variables locales utilizadas:

 const memoize = f => { let c = {}; return function() { let k = JSON.stringify(arguments); if (!c.hasOwnProperty(k)) { c[k] = f.apply(this, arguments); } return c[k]; } } 

Resultado: 154 , pruebas aprobadas

Entonces podemos llevar a cabo una operación similar con la función resultante, pero allí necesitamos argumentos . Aquí el operador de propagación viene al rescate, lo que nos permite reemplazar el objeto iterable pasado de los argumentos con la variable de matriz a . Además, ya no pasaremos este contexto a la función que se está decorando: si es necesario, Function.prototype.bind o nuestro polyfil ayudarán.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); if (!c.hasOwnProperty(k)) { c[k] = f(...a); } return c[k]; } } 

Resultado: 127 , pruebas aprobadas

Ahora pasamos al cuerpo de la función resultante. Obviamente, encontrar la clave en el caché y devolver el valor es engorroso. Intentemos reducir cómo:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c[k] || (c[k] = f(...a)); } } 

Resultado: 101 , cayeron las pruebas 3 y 4

Aquí abandonamos el método hasOwnProperty . Podemos permitirlo, porque el resultado de serializar la matriz de argumentos a través de JSON.stringify siempre será "[...]" y es poco probable que dicha propiedad aparezca en el caché prototipo ( Object ).

A continuación, usamos la función del operador OR "lógico" para devolver la primera expresión si se puede convertir a verdadero , o de lo contrario, la segunda con el cálculo de la función anterior.

Y aquí caemos las pruebas 3 y 4. Esto sucedió porque la función decorada console.log no devuelve un valor: el resultado será indefinido . Ponemos esto en la memoria caché, y cuando intentamos verificar a través de la función disyuntor cuando llamamos de nuevo, obtenemos implícitamente falso en el primer operando y, en consecuencia, entramos en el segundo, lo que conduce a la llamada a la función. Este efecto tendrá lugar para todos los resultados reducidos a falso : 0, "", nulo, NaN , etc.

En lugar de OR y if, podemos usar un operador ternario condicional:

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return c.hasOwnProperty(k) ?c[k] :c[k] = f(...a); } } 

Resultado: 118 , pruebas aprobadas

Reducido muy ligeramente. Pero, ¿qué pasa si usa Map como almacenamiento en lugar de un objeto simple? También hay un método corto tiene :

 const memoize = f => { let c = new Map; return (...a) => { let k = JSON.stringify(a); return (c.has(k) ?c :c.set(k, f(...a))).get(k); } } 

Resultado: 121 , pruebas aprobadas

Reducir completamente fallido. Pero descartar Map inmediatamente no vale la pena. Esta implementación del almacenamiento de valores clave le permite usar objetos como clave. Y eso significa, ¿deberíamos renunciar a JSON.stringify ?

 const memoize = f => { let c = new Map; return (...a) => (c.has(a) ?c :c.set(a, f(...a))).get(a); } 

Resultado: 83 , cayeron las pruebas 3 y 4

¡Se ve muy prometedor! Sin embargo, las pruebas 3 y 4 comenzaron a caer nuevamente, debido a que la comparación de claves en el objeto Map se implementa utilizando el algoritmo SameValueZero . Si omite los detalles con NaN, -0 y 0 , entonces funciona de manera similar al operador de comparación estricto ( === ). Y tenemos una nueva matriz de argumentos (y, por lo tanto, un objeto) para cada llamada de la función ajustada, incluso con los mismos valores. La comparación se realiza de acuerdo con la referencia del objeto y, por lo tanto, el método Map.prototype.has nunca encontrará nada.

Por lo tanto, el uso de Map no nos ha reducido hasOwnProperty o JSON.stringify .

En operador viene al rescate, que comprueba la presencia de una propiedad en un objeto o en la cadena de sus prototipos. Por qué no podemos tener miedo de la búsqueda en prototipos se ha explicado anteriormente.

 const memoize = f => { let c = {}; return (...a) => { let k = JSON.stringify(a); return k in c ?c[k] :c[k] = f(...a); } } 

Resultado: 105 , pruebas aprobadas

El cuerpo del memorador y la función resultante consta de dos expresiones con la necesidad de declarar e inicializar una variable local antes de la lógica en la declaración de retorno . ¿Es posible reducir el cuerpo de la función de flecha a una expresión aquí? Por supuesto, usando el patrón IIFE ( expresión de función invocada inmediatamente ):

 const memoize = f => (c => (...a) => (k => k in c ?c[k] : c[k] = f(...a))(JSON.stringify(a)) )({}); 

Resultado: 82 , pruebas aprobadas

Es hora de deshacerse de los espacios adicionales:

 f=>(c=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)))({}); 

Resultado: 68 , pruebas aprobadas

Obviamente, el cuello de botella ahora es el largo método JSON.stringify , que serializa recursivamente el objeto en una cadena JSON, que usamos como clave. De hecho, no necesitamos una función de serialización, sino una función hash con la que podamos verificar la igualdad de los objetos, ya que funciona en otros idiomas. Pero, desafortunadamente, no hay una solución nativa en JavaScript, y el polifilo autoescrito hashCode en el prototipo de Object está claramente más allá del alcance.

Hmm, ¿por qué tenemos que serializarnos? Al agregar un elemento a un objeto por clave, se llamará implícitamente a toString. Dado que nos negamos a usar el objeto de argumentos iterables a favor de la matriz a través del operador de propagación , la llamada aString no será de Object.prototype , sino de Array.prototype , en el que se redefine y separa por coma sus elementos. Por lo tanto, para un conjunto diferente de argumentos obtenemos una clave diferente.

 f=>(c=>(...a)=>a in c?c[a]:c[a]=f(...a))({}); 

Resultado: 44 , cayó la prueba 6

La prueba 6 está empezando a caer, parece que el valor de retorno es el resultado de una llamada a una función anterior en la prueba 5. ¿Por qué está sucediendo esto? Sí, pasamos por alto la llamada a String para el objeto de argumentos , pero no tomamos en cuenta que cualquier argumento también puede ser un objeto complejo, llamando a String de donde obtenemos el [objeto Object] favorito de todos. Esto significa que los argumentos {x: 1} y {x: 2} usarán la misma clave en el hash.

El btoa utilizado para convertir a base64 parecía un buen competidor para la función de serialización. Pero él conduce primero a la cuerda, así que no hay posibilidad. Pensamos en la dirección de generar un URI y formar un ArrayBuffer , cualquier función para obtener un valor hash o serializado. Pero se quedaron en su lugar.

Por cierto, JSON.stringify tiene sus propias peculiaridades: Infinito, NaN, indefinido, Símbolo se convertirá en nulo . Lo mismo vale para las funciones. Si es posible, se produce una llamada implícita a JSON desde el objeto, y Map and Set se representará mediante elementos simplemente enumerados. Es comprensible, dado el formato final: JSON.

Que sigue

Modificación tóxica

Ciertamente, todos amamos las funciones puras, pero ante el problema, tal requisito no vale la pena. Y esto significa que es hora de agregar una pizca de efectos secundarios.

Primero, ¿por qué no iniciar el caché de la siguiente manera?

 (f,c={})=>(...a)=>(k=>k in c?c[k]:c[k]=f(...a))(JSON.stringify(a)); 

Resultado: 66 , pruebas aprobadas

Aquí usamos el parámetro predeterminado en la función de flecha. Por supuesto, le damos al cliente la oportunidad de configurar su caché, ¿y qué? Pero redujimos 2 caracteres.

¿De qué otra forma puedo iniciar un caché para que se decore una función? La respuesta correcta: ¿por qué necesitamos iniciarlo? ¿Por qué no usar algo listo en el contexto de una función para envolver? Pero, ¿y si la función en sí? Todos sabemos que las funciones en JavaScript también son objetos:

 f=>(...a)=>(k=>k in f?f[k]:f[k]=f(...a))(JSON.stringify(a)); 

Resultado: 59 , pruebas aprobadas

Aquí JSON.stringify nos protegerá de la intersección con otras propiedades y métodos del objeto (función), envolviendo los argumentos en "[...]".

En este mismo momento, el patrón IIFE aplicado anteriormente ya no se justifica a sí mismo. Pero es urgente mantener una sola expresión para la función de flecha para evitar una declaración de retorno :

 f=>(...a)=>(k=JSON.stringify(a),k in f?f[k]:f[k]=f(...a)); 

Resultado: 57 , pruebas aprobadas

Como no usamos la instrucción de bloque en la función de flecha, no podemos declarar una variable ( var o let ), pero podemos usar el contexto global - ¡efecto secundario! Aquí el conflicto ya tiene algunas posibilidades de ser.

Usando el operador de coma, concatenamos dos expresiones en una: los operandos se evalúan de izquierda a derecha, y el resultado es el valor de este último.

 f=>(...a)=>(k=JSON.stringify(a))in f?f[k]:f[k]=f(...a); 

Resultado: 54 , pruebas aprobadas

Entonces, al reorganizar solo un paréntesis, eliminamos tres caracteres a la vez. El operador de agrupación al calcular la clave nos permitió combinar ambos operandos de la expresión en una sola expresión, y el corchete de cierre eliminó el espacio antes del operador in .

Y finalmente:

 f=>(...a)=>f[k=JSON.stringify(a)]=k in f?f[k]:f(...a); 

Resultado: 53 , pruebas aprobadas

¿Por qué no calcular la clave al acceder al valor? Y luego, el mismo operador ternario y la misma asignación. Total: 53 caracteres!

¿Es posible eliminar los 3 caracteres restantes?

Comprensión

¿Por qué todo esto? Esta tarea simple y la cadena posterior de conversiones de lo habitual a lo indecente demuestran un número considerable de características del lenguaje JavaScript. En nuestras discusiones, tocamos cosas como:

• Expresión de la función de flecha
• Alcance léxico y IIFE
• Objeto de argumentos tipo matriz
• Difusión, coma u operadores
• Operador de comparación estricto
• JSON.stringify y toString
• En operador y hasOwnProperty
• Operador de agrupación y declaración de bloque
• Objeto del mapa
• y algo mas

Tales historias son una buena razón para sumergirse en el estudio de los detalles de un idioma, ayudar a comprenderlo mejor (o viceversa). Y, por supuesto, ¡solo por diversión!

App

En sus aventuras, Rick a menudo tiene que calibrar su arma portal. El procedimiento lleva tiempo, pero la entrada a menudo se repite. El científico está tratando de memorizar los resultados ya obtenidos una vez para no hacer cálculos repetidamente, pero el alcoholismo y la senilidad senil afectan fuertemente su memoria. Le pidió a Morty que mejorara el módulo de configuración de armas, agregando una función de memoria. Esta función debe guardar los resultados de la función que se está decorando para evitar cálculos repetidos. Solo Morty tiene pánico y teme a las funciones largas. Ayúdelo a resolver el problema de la manera más compacta posible . La función que se está decorando puede tomar enteros, cadenas, booleanos y objetos como argumentos.