Esta é a segunda parte da análise de tarefas de nosso estande na conferência
HolyJS , realizada em São Petersburgo, de 24 a 25 de maio. Para um contexto maior, é recomendável que você leia
primeiro a
primeira parte deste material. E se a
Expressão de contagem regressiva já tiver sido concluída, bem-vindo ao próximo passo.
Diferentemente do obscurantismo na primeira tarefa, os próximos dois já têm alguma dica da aplicabilidade das aplicações normais na vida. O JavaScript ainda está desenvolvendo bastante rápido e as soluções para os problemas sugeridos destacam alguns dos novos recursos da linguagem.
Tarefa 2 ~ Feito por Uns
Supunha-se que o código executasse e imprimisse respostas para o console em resposta a três solicitações e depois "concluído". Mas algo deu errado ... Corrija a situação.
;(function() { let iter = { [Symbol.iterator]: function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); } } }; for (const res of iter) { console.log(res); } console.log('done'); })();
Problema de pesquisa
O que temos aqui? Este é um objeto
iterável iterável que possui um símbolo
conhecido Symbol.iterator definido por meio de
uma função geradora . Uma matriz
fs é declarada no corpo da função, cujos elementos se enquadram na função de
busca , por sua vez, para enviar uma solicitação e o resultado de cada chamada de função é retornado através do
rendimento . Quais solicitações a função de
busca envia? Todos os elementos da matriz
fs são caminhos relativos aos recursos com os números 1, 2 e 3, respectivamente. Portanto, o URL completo será obtido concatenando
location.origin com o próximo número, por exemplo:
GET https://www.example.com/1
A seguir, queremos iterar o objeto
iter por
for-of , para executar cada solicitação por vez com a saída do resultado, afinal - imprimir “done”. Mas isso não funciona! O problema é que a
busca é uma coisa assíncrona e retorna uma promessa, não uma resposta. Portanto, no console, veremos algo assim:
Promise {pending}
Promise {pending}
Promise {pending}
done
Na verdade, a tarefa se resume a resolver essas mesmas promessas.
Temos assíncrono / aguardamos
O primeiro pensamento pode ser brincar com o
Promise.all : forneça nosso objeto
iterável e , em
seguida ,
envie para o console "pronto". Mas ele não nos fornecerá a execução seqüencial de solicitações (conforme exigido pela condição), mas simplesmente enviará todas e aguardará a última resposta antes da resolução geral.
A solução mais simples aqui seria
aguardar no corpo
for- for aguardar a resolução da próxima promessa antes da saída para o console:
for (const res of iter) { console.log(await res); }
Para
aguardar o trabalho e "concluído" ser exibido no final, você precisa tornar a função principal assíncrona via
async :
;(async function() { let iter = { }; for (const res of iter) { console.log(await res); } console.log('done'); })();
Nesse caso, o problema já foi resolvido (quase):
GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done
Iterador e Gerador Assíncrono
Deixaremos a função principal assíncrona, mas, por
aguardar, há um lugar mais elegante nessa tarefa do que no corpo
for-for : esse é o uso da iteração assíncrona através do
for-waitit of , a saber:
for await (const res of iter) { console.log(res); }
Tudo vai dar certo! Mas se você se voltar para a descrição
desta proposta sobre iteração assíncrona, eis o que é interessante:
Introduzimos uma variação da declaração de iteração for-iterate sobre objetos iteráveis assíncronos. Instruções assíncronas para-de-somente são permitidas nas funções assíncronas e funções geradoras assíncronas
Ou seja, nosso objeto não deve ser apenas
iterável , mas
"assíncrono" através do novo símbolo
bem conhecido Symbol.asyncIterator e, no nosso caso, já uma função geradora assíncrona:
let iter = { [Symbol.asyncIterator]: async function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield await fetch(req); } } };
Como funciona, então, em um iterador e gerador regulares? Sim, apenas implicitamente, como muito mais neste idioma. Isso é difícil: se o objeto é apenas
iterável , durante a iteração assíncrona "converte" o objeto em
asyncIterable envolvendo os elementos (se necessário) no
Promise com a expectativa de resolução. Ele falou
com mais detalhes
em um artigo de Axel Rauschmayer .
Provavelmente, por meio do
Symbol.asyncIterator , ainda estará mais correto, pois criamos explicitamente o objeto
asyncIterable para nossa iteração assíncrona por meio
de aguardar , deixando a oportunidade de suplementar o objeto com um iterador regular para
for , se necessário. Se você quiser ler algo útil e suficiente em um artigo sobre iterações assíncronas em JavaScript,
aqui está ele !
O
for-of assíncrono ainda está parcialmente em rascunho, mas já é suportado por navegadores modernos (exceto Edge) e Node.js da 10.x. Se isso incomoda alguém, você sempre pode escrever seu próprio pequeno polifile para uma cadeia de promessas, por exemplo, para um objeto
iterável :
const chain = (promises, callback) => new Promise(resolve => function next(it) { let i = it.next(); i.done ? resolve() : i.value.then(res => { callback(res); next(it); }); }(promises[Symbol.iterator]()) ); ;(async function() { let iter = { }; await chain(iter, console.log); console.log('done'); })();
Dessa maneira, descobrimos o envio de solicitações e o processamento de respostas. Mas neste problema há mais um problema pequeno, mas irritante ...
Teste de atenção plena
Ficamos tão empolgados com todo esse assincronismo que, como costuma acontecer, perdemos de vista um pequeno detalhe. Essas solicitações são enviadas pelo nosso script? Vamos ver a
rede :
GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2
Mas nossos números são 1, 2, 3. Como se houvesse decréscimo. Porque Apenas no código-fonte da tarefa, há outro problema com a iteração, aqui:
let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); }
Aqui
é usado um
for-in , que, em vez de valores de matriz, ignora suas propriedades enumeradas: e estes são os índices de elementos de 0 a 2. A função de
busca ainda os leva a seqüências de caracteres e, apesar da ausência de uma barra antes (esse não é mais o
caminho ), ele resolve relativamente URL da página atual. Consertar é muito mais fácil do que perceber. Duas opções:
let fs = ['/1', '/2', '/3']; for (const req of fs) { yield fetch(req); } let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(fs[req]); }
No primeiro, usamos o mesmo
for-of para iterar sobre os valores da matriz, na segunda - acesso ao elemento da matriz por índice.
Motivação
Foram consideradas três soluções: 1) através de
aguardar no corpo
for-for , 2) através
de aguardar-for e 3) através de nosso polyfile (função recursiva,
tubulação de tubulação, etc.). É curioso que essas opções dividissem os participantes da conferência aproximadamente igualmente e que nenhum favorito óbvio foi revelado. Em projetos grandes, para tarefas reais, geralmente é usada uma biblioteca reativa (por exemplo,
RxJS ), mas vale a pena lembrar sobre os recursos nativos modernos de uma linguagem de natureza assíncrona.
Cerca de metade dos participantes não notou erros na iteração na lista de recursos, o que também é uma observação interessante. Concentrando-se em um problema não trivial, mas óbvio, podemos facilmente ignorar esse aspecto aparentemente trivial, mas com possíveis consequências graves.
Problema 3 ~ Fator 19
Quantas vezes existem nos números 2019! (fatorial a partir de 2019) ocorre o número 19? Juntamente com a resposta, forneça uma solução JavaScript.
Problema de pesquisa
O problema está na superfície: precisamos de um registro de um número muito grande para encontrar nele o número de todas as ocorrências da subcadeia “19”. Resolvendo o problema nos
números , rapidamente encontramos o
Infinity (após 170) e não conseguimos nada. Além disso, o formato para representar números
float64 garante a precisão de apenas 15 a 17 caracteres, e precisamos obter não apenas um registro completo, mas também um registro preciso do número. Portanto, a principal dificuldade é determinar a estrutura para o acúmulo desse grande número.
Inteiros grandes
Se você segue as inovações da linguagem, o problema é resolvido simplesmente: em vez do
número do tipo
, você pode usar o novo tipo
BigInt (estágio 3) , que permite trabalhar com números de precisão arbitrários. Com a função fatorial recursiva clássica e a busca de correspondências por meio de
String.prototype.split, a primeira solução fica assim:
const fn = n => n > 1n ? n * fn(n - 1n) : 1n; console.log(fn(2019n).toString().split('19').length - 1);
No entanto, duas mil chamadas de função na pilha já podem
ser perigosas . Mesmo se você levar a solução à
recursão final , a
otimização de chamada final ainda suporta apenas o Safari. O problema fatorial aqui é mais agradável de resolver por meio de um ciclo aritmético ou
Array.prototype.reduce :
console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length);
Isso pode parecer um procedimento insanamente longo. Mas essa impressão é enganosa. Se você estimar, basta gastar um pouco mais de duas mil multiplicações. Em i5-4590 a 3,30GHz no chrome, o problema é resolvido em média em 4-5ms (!).
Outra opção para encontrar correspondências em uma sequência com o resultado de um cálculo é
String.prototype.match por expressão regular com o sinalizador de pesquisa global:
/ 19 / g .
Aritmética grande
Mas e se ainda não tivermos esse
BigInt (e também as
bibliotecas )? Nesse caso, você pode fazer a aritmética longa sozinho. Para resolver o problema, basta implementarmos a função de multiplicar grande por pequeno (multiplicamos por números de 1 a 2019). Podemos conter um número grande e o resultado da multiplicação, por exemplo, na linha:
const mult = (big, int) => { let res = '', carry = 0; for (let i = big.length - 1; i >= 0; i -= 1) { let prod = big[i] * int + carry; res = prod % 10 + res; carry = prod / 10 | 0; } return (carry || '') + res; } console.log([...Array(2019)].reduce((p, _, i) => mult(p, i + 1), '1').match(/19/g).length);
Aqui, simplesmente multiplicamos a coluna em bits, do final da linha ao início, como fomos ensinados na escola. Mas a solução já requer cerca de 170ms.
Podemos melhorar um pouco o algoritmo processando mais de um dígito em um registro numérico por vez. Para fazer isso, modificamos a função e, ao mesmo tempo, vamos para as matrizes, para não mexer nas linhas todas as vezes:
const mult = (big, int, digits = 1) => { let res = [], carry = 0, div = 10 ** digits; for (let i = big.length - 1; i >= 0 || carry; i -= 1) { let prod = (i < 0 ? 0 : big[i] * int) + carry; res.push(prod % div); carry = prod / div | 0; } return res.reverse(); }
Aqui, números grandes são representados por uma matriz, cada elemento armazenando informações sobre dígitos do registro numérico, usando o
número . Por exemplo, o número 2016201720182019 com
dígitos = 3 será representado como:
'2|016|201|720|182|019' => [2,16,201,720,182,19]
Ao converter para uma linha antes de uma junção, é necessário lembrar os zeros à esquerda. A função
fator retorna o fatorial calculado por uma sequência, usando a função
mult com o número especificado de dígitos processados por vez na representação "maciça" do número ao calcular:
const factor = (n, digits = 1) => [...Array(n)].reduce((p, _, i) => mult(p, i + 1, digits), [1]) .map(String) .map(el => '0'.repeat(digits - el.length) + el) .join('') .replace(/^0+/, ''); console.log(factor(2019, 3).match(/19/g).length);
A implementação "na altura do joelho" por meio de matrizes acabou sendo mais rápida do que por meio de strings, e com
dígitos = 1 calcula a resposta já em média em 90ms,
dígitos = 3 em 35ms,
dígitos = 6 em apenas 20ms. No entanto, lembre-se de que, aumentando o número de dígitos, estamos nos aproximando de uma situação em que multiplicar
número por
número "sob o capô" pode estar fora do cofre
MAX_SAFE_INTEGER . Você pode brincar
aqui . Qual é o valor máximo de
dígitos que podemos pagar para esta tarefa?
Os resultados já são bastante indicativos, o
BigInt é realmente muito rápido:
Motivação
É legal que 2/3 dos participantes da conferência usaram o novo tipo
BigInt na solução (alguém admitiu que essa foi a primeira experiência). O terço restante das soluções continha suas próprias implementações de aritmética longa em cadeias ou matrizes. A maioria das funções implementadas multiplicou números grandes por números grandes, quando para uma solução bastava multiplicar por um
número "pequeno" e gastar um pouco menos de tempo. Certo, você já
usa o BigInt em seus projetos?
Agradecimentos
Esses dois dias da conferência foram muito cheios de discussões e aprendendo algo novo. Gostaria de agradecer ao comitê do programa a próxima conferência inesquecível e a todos os participantes por suas redes únicas e bom humor.