A história de um problema: o menor memorizador de JavaScript

Foi à noite, na véspera da conferência anual do HolyJS em São Petersburgo. Nossa empresa é patrocinadora há vários anos: portanto, também possui um estande próprio com interesses interessantes para a mente inquisitiva de desenvolvedores preocupados. Quando o prato principal estava pronto e todas as tarefas foram revisadas e concluídas por advogados, decidi oferecer aos meus colegas um pouco mais de comida intelectual à noite:

Escreva um memorizador - uma função decoradora que salva os resultados da execução de uma função agrupada para evitar cálculos repetidos. Você tem apenas 50 caracteres.

A linguagem é, obviamente, JavaScript . A tarefa em si é um clássico, mas o limite de 50 caracteres se transformou em um verdadeiro desafio.

Nos intervalos do primeiro dia da conferência, discutimos opções para atingir a meta, reduzindo gradualmente a resposta. Todo o hype foi coroado com a idéia de compartilhar a tarefa com todos os participantes da conferência e, no segundo dia, visualizamos a tarefa (veja o apêndice) e começamos a distribuir formulários para aqueles que desejavam. Como resultado, obtivemos cerca de 40 soluções e mais uma vez convencemos-nos da extraordinária comunidade de desenvolvedores de js, mas o registro de 53 caracteres de Dmitry Kataev (SEMrush) permaneceu. Vamos descobrir!

Implementação 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

• memoize - nosso memorizador
• f - função decorada e embrulhada
• ret - função resultante

Para obter a resposta - o tamanho da função - usamos:

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

Ao avaliar o tamanho de uma função, prestamos atenção ao seu corpo e a uma lista de parâmetros. Se a função for anônima, a declaração não será levada em consideração.

Testes simples para testar a saúde após abuso:

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

Em seguida, o resultado de cada implementação será marcado pelo resultado do teste.

Implementação líquida

Antes de tudo, quero me livrar da Declaração de Função em favor da função de seta, uma vez que não estamos interessados nesse contexto, não apelamos a argumentos e , como construtor, não pretendemos chamar de novo . Ao mesmo tempo, reduziremos os nomes das variáveis ​​locais usadas:

 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 , testes aprovados

Então, podemos realizar uma operação semelhante com a função resultante, mas precisamos de argumentos . Aqui o operador spread vem em socorro, permitindo substituir o objeto iterável passado dos argumentos pela variável de matriz a . Além disso, não passaremos mais esse contexto para a função que está sendo decorada: se necessário, Function.prototype.bind ou nosso polyfil ajudará.

 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 , testes aprovados

Agora nos voltamos para o corpo da função resultante. Obviamente, encontrar a chave no cache e retornar o valor é complicado. Vamos tentar reduzir como:

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

Resultado: 101 , testes 3 e 4 caíram

Aqui abandonamos o método hasOwnProperty . Podemos pagar, porque o resultado da serialização da matriz de argumentos via JSON.stringify sempre será "[...]" e é improvável que essa propriedade apareça no cache do protótipo ( Object ).

Em seguida, usamos o recurso do operador OR "lógico" para retornar a primeira expressão, se puder ser convertida em true , ou de outra forma, a segunda com o cálculo da função anterior.

E aqui caímos nos testes 3 e 4. Isso aconteceu porque a função decorada console.log não retorna um valor: o resultado será indefinido . Colocamos isso no cache e, quando tentamos verificar o recurso disjuntor quando o chamamos novamente, somos implicitamente exibidos como falsos no primeiro operando e, consequentemente, entramos no segundo, o que leva à chamada da função. Este efeito ocorrerá para todos os resultados reduzidos a falso : 0, "", nulo, NaN , etc.

Em vez de OR e if, podemos usar um operador ternário 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 , testes aprovados

Reduzido muito ligeiramente. Mas e se você usar o Map como um armazenamento em vez de um objeto simples? Há também um método has curto:

 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 , testes aprovados

Reduzir completamente falhou. Mas descartar o Map imediatamente não vale a pena. Essa implementação do armazenamento de valor-chave permite usar objetos como chave. E isso significa que devemos desistir do JSON.stringify ?

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

Resultado: 83 , testes 3 e 4 caíram

Parece muito promissor! No entanto, os testes 3 e 4. começaram a cair novamente, porque a comparação de chaves no objeto Map é implementada usando o algoritmo SameValueZero . Se você omitir os detalhes com NaN, -0 e 0 , funcionará de maneira semelhante ao operador de comparação estrita ( === ). E temos uma nova matriz de argumentos (e, portanto, um objeto) para cada chamada da função agrupada, mesmo com os mesmos valores. A comparação ocorre de acordo com a referência do objeto e, portanto, o método Map.prototype.has nunca encontrará nada.

Portanto, o uso do Map não nos reduziu hasOwnProperty ou JSON.stringify .

No operador, trata-se do resgate, que verifica a presença de uma propriedade em um objeto ou na cadeia de seus protótipos. Por que não podemos ter medo da pesquisa em protótipos foi explicado acima.

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

Resultado: 105 , testes aprovados

O corpo do memoizer e da função resultante consiste em duas expressões com a necessidade de declarar e inicializar uma variável local antes da lógica na instrução de retorno . É possível reduzir o corpo da função de seta para uma expressão aqui? Obviamente, usando o padrão IIFE ( expressão de função imediatamente chamada ):

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

Resultado: 82 , testes aprovados

É hora de se livrar de espaços extras:

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

Resultado: 68 , testes aprovados

Obviamente, o gargalo agora é o método JSON.stringify longo, que serializa recursivamente o objeto em uma string JSON, que usamos como chave. De fato, não precisamos de uma função de serialização, mas de uma função hash com a qual pudemos verificar a igualdade de objetos, pois ela funciona em outros idiomas. Infelizmente, porém, não há solução nativa no JavaScript, e o polifile auto-escrito hashCode no protótipo Object está claramente além do escopo.

Hmm, por que precisamos nos serializar? Ao adicionar um elemento a um objeto por chave, seu toString será chamado implicitamente. Como nos recusamos a usar o objeto de argumentos iteráveis ​​em favor da matriz por meio do operador spread , a chamada toString não será de Object.prototype , mas de Array.prototype , na qual ela é redefinida e seus elementos são separados por vírgula. Assim, para um conjunto diferente de argumentos, obtemos uma chave diferente.

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

Resultado: 44 , o teste 6 caiu

O teste 6. está começando a cair.Parece que o valor de retorno é o resultado de uma chamada de função anterior no teste 5. Por que isso está acontecendo? Sim, ignoramos a chamada toString para o objeto de argumentos , mas não levamos em conta que qualquer argumento também pode ser um objeto complexo, chamando paraString a partir da qual obtemos o [objeto objeto] favorito de todos. Isso significa que os argumentos {x: 1} e {x: 2} usarão a mesma chave no hash.

O btoa usado para converter em base64 parecia um bom candidato para a função de serialização. Mas ele leva primeiro à corda, então não há chance. Pensamos na direção de gerar um URI e formar um ArrayBuffer , quaisquer funções para obter um valor hash ou serializado. Mas eles permaneceram no lugar.

A propósito, o JSON.stringify tem suas próprias peculiaridades: Infinito, NaN, indefinido, Símbolo será convertido em nulo . O mesmo vale para funções. Se possível, ocorre uma chamada implícita a JSON do objeto, e Map e Set serão representados por elementos simplesmente enumerados. É compreensível, dado o formato final: JSON.

O que vem depois?

Modificação tóxica

Todos nós certamente amamos funções puras, mas diante do problema, esse requisito não vale a pena. E isso significa que é hora de adicionar uma pitada de efeitos colaterais.

Primeiro, por que não iniciar o cache da seguinte maneira:

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

Resultado: 66 , testes aprovados

Aqui usamos o parâmetro padrão na função de seta. Obviamente, damos ao cliente a oportunidade de definir seu cache, e daí? Mas reduzimos 2 caracteres.

De que outra forma posso iniciar um cache para que uma função seja decorada? A resposta correta: por que precisamos iniciá-lo? Por que não usar algo pronto no contexto de uma função a ser quebrada. Mas e se a própria função? Todos sabemos que funções em JavaScript também são objetos:

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

Resultado: 59 , testes aprovados

Aqui, o JSON.stringify nos protegerá da interseção com outras propriedades e métodos do objeto (função), envolvendo os argumentos em "[...]".

Neste exato momento, o padrão IIFE aplicado anteriormente não está mais se justificando. Mas manter uma expressão única para a função de seta é urgentemente necessária para evitar uma declaração de retorno :

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

Resultado: 57 , testes aprovados

Como não usamos a instrução block na função arrow, não podemos declarar uma variável ( var ou let ), mas podemos usar o contexto global - efeito colateral! Aqui o conflito já tem algumas chances de acontecer.

Utilizando o operador vírgula, concatenamos duas expressões em uma: os operandos são avaliados da esquerda para a direita e o resultado é o valor do último.

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

Resultado: 54 , testes aprovados

Então, reorganizando apenas um suporte, nos livramos de três caracteres ao mesmo tempo. O operador de agrupamento no cálculo da chave nos permitiu combinar os dois operandos da expressão em apenas uma expressão, e o colchete de fechamento removeu o espaço antes do operador in .

E finalmente:

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

Resultado: 53 , testes aprovados

Por que não calcular a chave ao acessar o valor. E então - o mesmo operador ternário e atribuição. Total: 53 caracteres!

É possível remover os 3 caracteres restantes?

Compreensão

Por que tudo isso? Esta tarefa simples e a subsequente cadeia de conversões do habitual para indecente demonstra um número considerável de recursos da linguagem JavaScript. Em nossas discussões, abordamos coisas como:

• Expressão da função de seta
• Escopo lexical e IIFE
• Objeto de argumentos do tipo matriz
• Spread, vírgula ou operadores
• Operador de comparação estrita
• JSON.stringify & toString
• No operador & hasOwnProperty
• Operador de agrupamento e instrução de bloco
• Objeto de mapa
• e outra coisa

Tais histórias são uma boa razão para mergulhar no estudo das especificidades de um idioma, ajudar a entendê-lo melhor (ou vice-versa). E, claro, apenas por diversão!

App

Em suas aventuras, Rick geralmente precisa calibrar sua arma portal. O procedimento leva tempo, mas a entrada é frequentemente repetida. O cientista está tentando memorizar os resultados já obtidos uma vez para não fazer cálculos repetidamente, mas o alcoolismo e a senilidade senil afetam fortemente sua memória. Ele pediu a Morty para melhorar o módulo de configurações da pistola, adicionando uma função de memorizador. Esta função deve salvar os resultados da função que está sendo decorada para evitar cálculos repetidos. Apenas Morty está em pânico com medo de longas funções. Ajude-o a resolver o problema da forma mais compacta possível . A função que está sendo decorada pode usar números inteiros, seqüências de caracteres, booleanos e objetos como argumentos.