Esta es la segunda parte del análisis de tareas desde nuestro stand en la conferencia
HolyJS , celebrada en San Petersburgo del 24 al 25 de mayo. Para un contexto más amplio, se recomienda que primero lea la
primera parte de este material. Y si
Countdown Expression ya se ha completado, bienvenido al siguiente paso.
A diferencia del oscurantismo en la primera tarea, las dos siguientes ya tienen algún indicio de la aplicabilidad de las aplicaciones normales en la vida. JavaScript todavía se está desarrollando bastante rápido y las soluciones a los problemas sugeridos resaltan algunas de las nuevas características del lenguaje.
Tarea 2 ~ Hecho por unos
Se suponía que el código se ejecutaría e imprimiría respuestas a la consola en respuesta a tres solicitudes, y luego "hecho". Pero algo salió mal ... Corrija la situación.
;(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 investigación
Que tenemos aqui Este es un objeto
iterativo iterativo que tiene un símbolo
Symbol.iterator bien conocido definido a través de
una función generadora . Se declara una matriz
fs en el cuerpo de la función, cuyos elementos caen en la función de
búsqueda a su vez para enviar una solicitud y el resultado de cada llamada de función se devuelve a través de
rendimiento . ¿Qué solicitudes envía la función de
búsqueda ? Todos los elementos de la matriz
fs son rutas relativas a los recursos con los números 1, 2 y 3, respectivamente. Por lo tanto, la URL completa se obtendrá concatenando
location.origin con el siguiente número, por ejemplo:
GET https://www.example.com/1
A continuación, queremos iterar el objeto
iter a través de
for-of , para ejecutar cada solicitud a su vez con la salida del resultado, después de todo, imprima "hecho". ¡Pero eso no funciona! El problema es que
buscar es una cosa asincrónica y devuelve una promesa, no una respuesta. Por lo tanto, en la consola veremos algo como esto:
Promise {pending}
Promise {pending}
Promise {pending}
done
En realidad, la tarea se reduce a resolver estas mismas promesas.
Tenemos async / aguardando
El primer pensamiento puede ser jugar con
Promise.all : darle nuestro objeto
iterable ,
luego la salida a la consola está "hecha". Pero no nos proporcionará la ejecución secuencial de las solicitudes (según lo requiera la condición), sino que simplemente las enviará todas y esperará la última respuesta antes de la resolución general.
La solución más simple aquí sería
esperar en el cuerpo
del cuerpo para esperar la resolución de la próxima promesa antes de enviarla a la consola:
for (const res of iter) { console.log(await res); }
Para
que el trabajo
en espera y "hecho" se muestre al final, debe hacer que la función principal sea asíncrona a través de
asíncrono :
;(async function() { let iter = { }; for (const res of iter) { console.log(await res); } console.log('done'); })();
En este caso, el problema ya se ha resuelto (casi):
GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done
Iterador asíncrono y generador
Dejaremos la función principal asincrónica, pero para
esperar hay un lugar más elegante en esta tarea que en el cuerpo
for-of : este es el uso de la iteración asincrónica a través de
for-wait-of , a saber:
for await (const res of iter) { console.log(res); }
¡Todo funcionará! Pero si recurre a la descripción de
esta propuesta sobre iteración asincrónica, entonces esto es lo interesante:
Introducimos una variación de la declaración de iteración for-of que itera sobre objetos iterables asíncronos. Las declaraciones for-of asincrónicas solo se permiten dentro de las funciones asincrónicas y las funciones generadoras asincrónicas
Es decir, nuestro objeto no solo debe ser
iterable , sino
"asyncIterable" a través del nuevo símbolo
conocido Symbol.asyncIterator y, en nuestro caso, ya una función generadora asíncrona:
let iter = { [Symbol.asyncIterator]: async function* iterf() { let fs = ['/1', '/2', '/3']; for (const req in fs) { yield await fetch(req); } } };
¿Cómo funciona entonces en un iterador y generador regular? Sí, solo implícitamente, como mucho más en este idioma. Esto es difícil: si el objeto solo es
iterable , entonces cuando itera asincrónicamente, "convierte" el objeto en
asyncIterable envolviendo los elementos (si es necesario) en
Promise con la expectativa de resolución. Habló
con más detalle
en un artículo de Axel Rauschmayer .
Probablemente, a través de
Symbol.asyncIterator todavía será más correcto, ya que creamos explícitamente el objeto
asyncIterable para nuestra iteración asincrónica a través de
for-wait-of , mientras dejamos la oportunidad de complementar el objeto con un iterador regular para
for , si es necesario. Si desea leer algo útil y suficiente en un artículo sobre iteraciones asíncronas en JavaScript, ¡
aquí está !
For
-of asíncrono todavía está parcialmente en borrador, pero ya es compatible con los navegadores modernos (excepto Edge) y Node.js de 10.x. Si esto molesta a alguien, siempre puede escribir su propio pequeño polifilo para una cadena de promesas, por ejemplo, para un objeto
iterable :
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'); })();
De esta y otras formas, descubrimos el envío de solicitudes y el procesamiento de respuestas a su vez. Pero en este problema hay un problema más pequeño pero molesto ...
Prueba de atención plena
Estábamos tan impresionados por todo este asincronismo que, como sucede a menudo, perdimos de vista un pequeño detalle. ¿Son esas solicitudes enviadas por nuestro script? Veamos la
red :
GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2
Pero nuestros números son 1, 2, 3. Como si hubiera ocurrido una disminución. Por qué Solo en el código fuente de la tarea hay otro problema con la iteración, aquí:
let fs = ['/1', '/2', '/3']; for (const req in fs) { yield fetch(req); }
Aquí
se usa un
for-in , que en lugar de los valores de la matriz omite sus propiedades enumeradas: y estos son los índices de elementos del 0 al 2. La función
fetch todavía los lleva a cadenas y, a pesar de la ausencia de una barra inclinada antes (esto ya no es una
ruta ), se resuelve relativamente URL de la página actual. Arreglarlo es mucho más fácil que darse cuenta. Dos opciones:
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]); }
En el primero, utilizamos el mismo
for-of para iterar sobre los valores de la matriz, en el segundo: acceso al elemento de la matriz por índice.
Motivación
Consideramos 3 soluciones: 1) a través de
esperar en el cuerpo
for-for , 2) a través de
for-wait-of, y 3) a través de nuestro polyfile (función recursiva,
tubería , etc.). Es curioso que estas opciones dividieron a los participantes de la conferencia aproximadamente por igual y no se reveló ningún favorito obvio. En proyectos grandes, para tareas tan reales, generalmente se usa una biblioteca reactiva (por ejemplo,
RxJS ), pero vale la pena recordar las características nativas modernas de un lenguaje de naturaleza asincrónica.
Aproximadamente la mitad de los participantes no notaron errores en la iteración de la lista de recursos, lo cual también es una observación interesante. Centrándonos en un problema no trivial pero obvio, podemos omitir fácilmente este truco aparentemente, pero con posibles consecuencias graves.
Problema 3 ~ Factor XIX
¡Cuántas veces en el registro del número 2019! (factorial de 2019) ¿aparece el número 19? Junto con la respuesta, proporcione una solución de JavaScript.
Problema de investigación
El problema está en la superficie: necesitamos un registro de un número muy grande para encontrar en él el número de todas las ocurrencias de la subcadena "19". Al resolver el problema en los
números , nos encontramos rápidamente con
Infinity (después de 170) y no obtuvimos nada. Además, el formato para representar números
float64 garantiza la precisión de solo 15-17 caracteres, y necesitamos no solo un registro completo, sino también exacto del número. Por lo tanto, la dificultad principal es determinar la estructura para la acumulación de este gran número.
Grandes enteros
Si sigue las innovaciones del lenguaje, el problema se resuelve simplemente: en lugar del
número de tipo
, puede usar el nuevo tipo
BigInt (etapa 3) , que le permite trabajar con números de precisión arbitrarios. Con la función recursiva clásica para calcular factorial y encontrar coincidencias a través de
String.prototype.split, la primera solución se ve así:
const fn = n => n > 1n ? n * fn(n - 1n) : 1n; console.log(fn(2019n).toString().split('19').length - 1);
Sin embargo, dos mil llamadas de función en la pila ya pueden
ser peligrosas . Incluso si lleva la solución a la
recursividad de cola , la
optimización de llamadas de cola solo es compatible con Safari. El problema factorial aquí es más agradable de resolver a través de un ciclo aritmético o
Array.prototype.reduce :
console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length);
Esto puede parecer un procedimiento increíblemente largo. Pero esta impresión es engañosa. Si estima, entonces solo necesitamos gastar un poco más de dos mil multiplicaciones. En i5-4590 3.30GHz en cromo, el problema se resuelve en promedio en 4-5ms (!).
Otra opción para encontrar coincidencias en una cadena con el resultado de un cálculo es
String.prototype.match por expresión regular con el indicador de búsqueda global:
/ 19 / g .
Aritmética grande
Pero, ¿qué
pasa si todavía no tenemos este
BigInt (y las
bibliotecas también)? En este caso, puede hacer la aritmética larga usted mismo. Para resolver el problema, nos basta con implementar solo la función de multiplicar grande por pequeña (multiplicamos por números del 1 al 2019). Podemos mantener un gran número y el resultado de la multiplicación, por ejemplo, en la línea:
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);
Aquí simplemente multiplicamos la columna en bits desde el final de la línea hasta el principio, como nos enseñaron en la escuela. Pero la solución ya requiere unos 170 ms.
Podemos mejorar algo el algoritmo procesando más de un dígito en un registro de números a la vez. Para hacer esto, modificamos la función y al mismo tiempo vamos a las matrices, para no perder el tiempo con las líneas cada vez:
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(); }
Aquí, los números grandes están representados por una matriz, cada elemento del cual almacena información sobre
dígitos dígitos del registro de números, usando el
número . Por ejemplo, el número 2016201720182019 con
dígitos = 3 se representará como:
'2|016|201|720|182|019' => [2,16,201,720,182,19]
Al convertir a una línea antes de una unión, debe recordar los ceros iniciales. La función
factor devuelve el factorial calculado por una cadena, utilizando la función
múltiple con el número especificado de dígitos procesados a la vez en la representación "masiva" del número al 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);
La implementación "hasta la rodilla" a través de matrices resultó ser más rápida que a través de cadenas, y con
dígitos = 1 calcula la respuesta ya en promedio en 90ms,
dígitos = 3 en 35ms,
dígitos = 6 en solo 20ms. Sin embargo, recuerde que al aumentar el número de dígitos, nos estamos acercando a una situación en la que multiplicar el
número por el
número "debajo del capó" puede estar fuera de la caja fuerte
MAX_SAFE_INTEGER . Puedes jugar con eso
aquí . ¿Cuál es el valor máximo de
dígitos que podemos permitirnos para esta tarea?
Los resultados ya son bastante indicativos,
BigInt es realmente bastante rápido:
Motivación
Es genial que 2/3 de los participantes de la conferencia usaron el nuevo tipo
BigInt en la solución (alguien admitió que esta fue la primera experiencia). El tercio restante de las soluciones contenía sus propias implementaciones de aritmética larga en cadenas o matrices. La mayoría de las funciones implementadas multiplicaron números grandes por números grandes, cuando para una solución fue suficiente multiplicar por un número "pequeño" y pasar un poco menos de tiempo. Bien, ¿ya
usas BigInt en tus proyectos?
Agradecimientos
Estos dos días de la conferencia estuvieron muy llenos de discusiones y aprendiendo algo nuevo. Me gustaría agradecer al comité del programa por la próxima conferencia inolvidable y a todos los participantes por su trabajo en red único y su buen humor.