HolyJS 2019: Разбор задач от компании SEMrush (Часть 2)

Это вторая часть разбора задач от нашего стенда на конференции HolyJS, прошедшей в Санкт-Петербурге 24-25 мая. Для большего контекста рекомендуется сначала ознакомиться с первой частью настоящего материала. А если Countdown Expression уже пройден, то добро пожаловать на следующий этап.

В отличие от «мракобесия» в первой задаче, следующие две уже имеют некоторый намек на применимость в жизни нормальных приложений. JavaScript развивается все еще достаточно быстро и решения предложенных проблем подчеркивают некоторые новые возможности языка.

Задача 2 ~ Done by Ones

Предполагалось, что код поочередно выполнит и выведет в консоль ответы по трем запросам, а потом — «done». Но что-то пошло не так… Исправьте ситуацию.

;(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');
})();

Исследование проблемы

Что у нас тут? Это iterable объект iter, у которого определен well-known символ Symbol.iterator через функцию-генератор. В теле функции объявлен массив fs, элементы которого по очереди попадают в функцию fetch для отправки запроса и результат каждого вызова функции возвращается через yield. Какие запросы отправляет функция fetch? Все элементы массива fs — это относительные пути (path) к ресурсам с номерами 1, 2 и 3 соответственно. Значит полный URL будет получен путем конкатенации location.origin с очередным номером, например:

GET https://www.example.com/1

Далее мы хотим проитерировать объект iter через for-of, чтобы по очереди выполнить каждый запрос с выводом результата, после всех — вывести «done». Но так не работает! Проблема в том, что fetch — штука асинхронная и возвращает промис, а не респонс. Поэтому в консоли мы увидим что-то такое:

Promise {pending}
Promise {pending}
Promise {pending}
done

Собственно, задача сводится к резолву этих самых промисов.

У нас есть async/await

Первой мыслью может быть поиграться с Promise.all: отдать ему наш iterable объект, then вывод в консоль «done». Но он не обеспечит нам поочередное выполнение запросов (как того требует условие), а просто отправит их все и дождется последнего ответа перед общим резолвом.

Самым простым решением здесь будет await в теле for-of для ожидания резолва очередного промиса перед выводом в консоль:

for (const res of iter) {
  console.log(await res);
}

Чтобы await работал и «done» выводился в конце, необходимо сделать главную функцию асинхронной через async:

;(async function() {
  let iter = { /* ... */ };
  for (const res of iter) {
    console.log(await res);
  }
  console.log('done');
})();

В этом случае проблема уже решена (почти):

GET 1st
Response 1st
GET 2nd
Response 2nd
GET 3rd
Response 3rd
done


Асинхронный итератор и генератор

Оставим главную функцию асинхронной, а вот для await в этой задаче есть более элегантное место, нежели в теле for-of: это использование асинхронной итерации через for-await-of, а именно:

for await (const res of iter) {
  console.log(res);
}

Все будет работать! Но если обратиться к описанию этого proposal про асинхронную итерацию, то вот что интересно:

We introduce a variation of the for-of iteration statement which iterates over async iterable objects. Async for-of statements are only allowed within async functions and async generator functions

То есть наш объект должен быть не просто iterable, а «asyncIterable» через новый well-known символ Symbol.asyncIterator и, в нашем случае, уже асинхронную функцию-генератор:

let iter = {
  [Symbol.asyncIterator]: async function* iterf() {
    let fs = ['/1', '/2', '/3'];
    for (const req in fs) {
      yield await fetch(req);
    }
  }
};

Как же оно тогда работает на обычном итераторе и генераторе? Да просто неявно, как и многое другое в этом языке. Этот for-await-of — хитрый: если объект только iterable, то при асинхронной итерации он «конвертирует» объект в asyncIterable через оборачивание элементов (при необходимости) в Promise с ожиданием резолва. Более подробно рассказал в статье Axel Rauschmayer.

Наверно, через Symbol.asyncIterator все таки будет правильней, так как мы явно сделали объект asyncIterable для нашей асинхронной итерации через for-await-of, при этом оставили возможность при необходимости дополнить объект еще и обычным итератором для for-of. Если хочется почитать про асинхронные итерации в JavaScript что-то полезное и достаточное в одной статье, то вот она!

Асинхронный for-of находится еще частично в драфте, но уже поддерживается современными браузерами (кроме Edge) и Node.js от 10.x. Если кого-то это смущает, то всегда можно написать свой небольшой полифил для цепочки промисов, например для 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 = { /* iterable */ };
  await chain(iter, console.log);
  console.log('done');
})();

Таким и таким способами мы разобрались с поочередной отправкой запросов и обработкой ответов. Но в этой задаче есть еще одна небольшая, но досадная неувязка…

Тест на внимательность

Мы так увлеклись всей этой асинхронщиной, что, как это часто бывает, упустили из виду одну маленькую деталь. Те ли запросы отправляет наш скрипт? Посмотрим network:

GET https://www.example.com/0
GET https://www.example.com/1
GET https://www.example.com/2

Но ведь наши номера — это 1, 2, 3. Как будто бы произошел декремент. Почему так? Просто в исходном коде задачи есть еще одна проблема с итерацией, вот тут:

let fs = ['/1', '/2', '/3'];
for (const req in fs) {
  yield fetch(req);
}

Здесь используется for-in, который вместо значений массива обходит его перечислимые свойства: а это — индексы элементов от 0 до 2. Функция fetch все равно приводит их к строкам и, несмотря на отсутствие слэша перед (это уже не path), успешно резолвит относительно URL текущей страницы. Исправить — гораздо проще, чем заметить. Два варианта:

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]);
}

В первом мы использовали тот же for-of для итерации уже по значениям массива, во втором — обращение к элементу массива по индексу.

Мотивация

Мы рассмотрели 3 варианта решения: 1) через await в теле for-of, 2) через for-await-of и 3) через свой полифил (рекурсивная функция, конвейер pipe, прочее). Любопытно, что эти варианты поделили участников конференции примерно поровну и явный фаворит не выявился. В крупных проектах для подобных реальных задач обычно используется реактивная библиотека (например RxJS), но о современных нативных возможностях языка с асинхронной природой тоже стоит помнить.

Примерно половина участников не заметили ошибки в итерации по списку ресурсов, что тоже — интересное наблюдение. Фокусируясь на нетривиальной, но очевидной проблеме, мы можем легко пропустить такую, казалось бы, мелочь, но с потенциальными серьезными последствиями.

Задача 3 ~ Factor 19th

Сколько раз в записи числа 2019! (факториал от 2019) встречается число 19? Вместе с ответом, предоставьте решение на JavaScript.

Исследование проблемы

Проблема на поверхности: нам нужна запись очень большого числа, чтобы найти в ней количество всех вхождений подстроки «19». Решая задачу на number'ах, мы очень быстро упремся в Infinity (после 170) и ничего не получим. Кроме того, формат представления чисел float64 гарантирует точность лишь 15-17 знаков, а нам надо получить не только полную, но и точную запись числа. Значит, основная сложность — определить структуру для аккумулирования этого большого числа.

Большие целые

Если следить за нововведениями языка, то задача решается просто: вместо типа number можно использовать новый тип BigInt (stage 3), который позволяет работать с числами произвольной точности. С классической рекурсивной функцией расчета факториала и поиском совпадений через String.prototype.split первое решение выглядит так:

const fn = n => n > 1n ? n * fn(n - 1n) : 1n;
console.log(fn(2019n).toString().split('19').length - 1); // 50

Однако, две тысячи вызовов функции в стеке — уже может быть опасно. Даже если привести решение к хвостовой рекурсии, то Tail call optimization до сих пор поддерживает только Safari. Задачу факториала здесь приятнее решить через арифметический цикл или Array.prototype.reduce:

console.log([...Array(2019)].reduce((p, _, i) => p * BigInt(i + 1), 1n).toString().match(/19/g).length); // 50

Может показаться, что это безумно долгая процедура. Но это впечатление — обманчиво. Если прикинуть, то нам всего-то надо провести чуть больше двух тысяч умножений. На i5-4590 3.30GHz в хроме задача решается в среднем за 4-5мс (!).

Еще вариант поиска совпадений в строке с результатом вычисления — это String.prototype.match по регулярному выражению с флагом глобального поиска: /19/g.

Большая арифметика

А что, если у нас еще нет этого BigInt (и библиотек тоже)? В этом случае, длинную арифметику можно провернуть самостоятельно. Для решения проблемы нам достаточно реализовать только функцию умножения большого на маленькое (умножаем на числа от 1 до 2019). Большое число и результат умножения можем держать, например, в строке:

/**
 * @param {string} big
 * @param {number} int
 * @returns {string}
 */
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); // 50

Здесь мы просто умножаем столбиком по-разрядно с конца строки в начало, как нас учили в школе. Но решение требует уже порядка 170мс.

Мы можем несколько улучшить алгоритм, обрабатывая больше одной цифры в записи числа за раз. Для этого модифицируем функцию и заодно перейдем на массивы, чтобы не возиться каждый раз со строками:

/**
 * @param {Array<number>} big
 * @param {number} int
 * @param {number} digits
 * @returns {Array<number>}
 */
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();
}

Здесь большие числа представлены массивом, каждый элемент которого хранит информацию о digits цифрах из записи числа, используя number. Например, число 2016201720182019 при digits = 3, будет представлено как:

'2|016|201|720|182|019' => [2,16,201,720,182,19]

Преобразуя к строке перед джойном, необходимо помнить о ведущих нулях. Функция factor возвращает посчитанный факториал строкой, используя функцию mult с указанным количеством за раз обрабатываемых цифр в «массивном» представлении числа при вычислении:

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); // 50

«Коленочная» реализация через массивы оказалась быстрее, чем через строки, и с digits = 1 вычисляет ответ уже в среднем за 90мс, digits = 3 — за 35мс, digits = 6 — всего за 20мс. Однако помним, что увеличивая количество цифр, мы приближаемся к ситуации, когда умножение number на number «под капотом» может оказаться вне безопасного MAX_SAFE_INTEGER. Поиграться с этим можно здесь. Какое максимальное значение digits мы можем себе позволить для этой задачи?

Результаты уже вполне показательны, BigInt — правда довольно шустрый:

Мотивация

Классно, что 2/3 участников конференции использовали в решении новый тип BigInt (кто-то признался, что это был первый опыт). Оставшаяся треть решений содержала собственные реализации длинной арифметики на строках или массивах. Большая часть реализованных функций умножала большие числа на большие, когда для решения достаточно было умножать на «маленький» number и потратить несколько меньше времени. Ладно задача, а используете ли вы уже BigInt в своих проектах?

Благодарности

Эти два дня конференции были очень насыщены дискуссиями и изучением чего-то нового. Хотелось бы поблагодарить программный коммитет за очередную незабываемую конференцию и всех участников за уникальный нетворкинг и отличное настроение.