[Перевод] Решение задач Front End с интервью. Promise Pool
В данной статье хочется разобрать задачу Promise Pool (Leetcode 2636)
Условие задачи
Дан массив асинхронных функций functions и максимальный размер пула n. Необходимо написать асинхронную функцию promisePool. Она должна возвращать Promise, который разрешается, когда разрешаются все функции из массива functions.
Размер пула определяет максимальное число Promise, которые могут одновременно выполняться. Функция PromisePool должна начать выполнение максимально возможного количества функций из массива functions и брать новые функции на выполнение, когда какие-то из выполняющихся Promise разрешатся. Функции необходимо выполнять в порядке их следования в массиве functions. Когда последний Promise перейдет в состояние resolved, promisePool также должен перейти в состояние resolved.
Например, если n = 1, promisePool будет выполнять по одной функции последовательно. Однако если n = 2, он сначала начнут выполняться две функции. Когда любая из двух функций разрешается, должна начать выполняться третья функция (если она есть в массиве) и так далее, пока не останется функций для выполнения.
По условию задачи, все функции из массива всегда успешно переходят в состояние resolved. В качестве результата, результирующий Promise функции promisePool может вернуть любое значение.
Пример
Входные данные:
functions = [
() => new Promise(res => setTimeout(res, 300)),
() => new Promise(res => setTimeout(res, 400)),
() => new Promise(res => setTimeout(res, 200))
]
n = 2
Результат: [[300,400,500],500]
Объяснение:
Во входном массиве 3 функции. В них вызывается setTimeout на 300мс, 400мс, и 200mмс соответственно.
Они переходят в resolved в 300мс, 400мс, и 500мс соответственно. Результирующий promise завершается в 500мс.
В t=0, первые 2 функции начинают выполнение. Размер пула 2.
В t=300, 1-я функция завершает выполнение, а 3-я функция начинает. Размер пула 2.
В t=400, 2-я функция завершает выполнение. Больше функций в массиве functions не осталось. Размер пула 1.
В t=500, 3-я функция завершает выполнение. Размер пула 0, и результирующий promise закже завершается.Решение
Пусть i — выполняемая в данный момент функция, availPool — число оставшихся ресурсов для выполнения Promise, completedCount — число завершенных Promise.
В случае если массив функций пустой — мы можем завершить результирующий Promise.
В ином случае, мы запускаем рекурсивную функцию executeNext, в которой:
Берем следующие k функций, где k равно числу доступных ресурсов.
Мы уменьшаем число свободных ресурсов availPool на k (availPool -= k) и запускаем k функций на выполнение.
По завершении каждой функции, мы освобождаем ресурс (availPool += 1) и увеличиваем на 1 число завешенных функций (completedCount += 1).
Если все функции завершились, мы завершаем итоговый promise, иначе рекурсивно запускаем функцию executeNext.
var promisePool = function(functions, n) {
let i = 0;
let availPool = n;
let completedCount = 0;
return new Promise((resolve, reject) => {
if(functions.length === 0){
resolve();
return;
}
const executeNext = () => {
const pendingFunctions = functions.slice(i, i + availPool);
i += pendingFunctions.length;
availPool = 0;
pendingFunctions.forEach(func => {
func().then(() => {
availPool++;
completedCount++;
if(completedCount === functions.length){
resolve();
} else {
executeNext();
}
})
});
}
executeNext();
});
};
/**
* const sleep = (t) => new Promise(res => setTimeout(res, t));
* promisePool([() => sleep(500), () => sleep(400)], 1)
* .then(console.log) // After 900ms
*/Похожая задача мне встречалась на Контесте перед Two Day Offer от Yandex. Там задача была усложнена дополнительными деталями и видоизменена, но для ее решения было важно знать данную задачу (Promise Pool), а также быть знакомым с Heap / Priority Queue.
