2650. 设计可取消函数

🔴   🔗 力扣 LeetCode

题目

Sometimes you have a long running task, and you may wish to cancel it before it completes. To help with this goal, write a function cancellable that accepts a generator object and returns an array of two values: a cancel function and a promise.

You may assume the generator function will only yield promises. It is your function's responsibility to pass the values resolved by the promise back to the generator. If the promise rejects, your function should throw that error back to the generator.

If the cancel callback is called before the generator is done, your function should throw an error back to the generator. That error should be the string "Cancelled" (Not an Error object). If the error was caught, the returned promise should resolve with the next value that was yielded or returned. Otherwise, the promise should reject with the thrown error. No more code should be executed.

When the generator is done, the promise your function returned should resolve the value the generator returned. If, however, the generator throws an error, the returned promise should reject with the error.

An example of how your code would be used:

function* tasks() {
	const val = yield new Promise((resolve) => resolve(2 + 2));

	yield new Promise((resolve) => setTimeout(resolve, 100));

	return val + 1; // calculation shouldn't be done.
}

const [cancel, promise] = cancellable(tasks());

setTimeout(cancel, 50);

promise.catch(console.log); // logs "Cancelled" at t=50ms

If instead cancel() was not called or was called after t=100ms, the promise would have resolved 5.

Example 1:

Input:

generatorFunction = function* () {
	return 42;
};

cancelledAt = 100;

Output:

Explanation:

const generator = generatorFunction();

const [cancel, promise] = cancellable(generator);

setTimeout(cancel, 100);

promise.then(console.log); // resolves 42 at t=0ms

The generator immediately yields 42 and finishes. Because of that, the returned promise immediately resolves 42. Note that cancelling a finished generator does nothing.

Example 2:

Input:

generatorFunction = function* () {
	const msg = yield new Promise((res) => res('Hello'));

	throw `Error: ${msg}`;
};

cancelledAt = null;

Output:

Explanation:

A promise is yielded. The function handles this by waiting for it to resolve and then passes the resolved value back to the generator. Then an error is thrown which has the effect of causing the promise to reject with the same thrown error.

Example 3:

Input:

generatorFunction = function* () {
	yield new Promise((res) => setTimeout(res, 200));

	return 'Success';
};

cancelledAt = 100;

Output:

Explanation:

While the function is waiting for the yielded promise to resolve, cancel() is called. This causes an error message to be sent back to the generator. Since this error is uncaught, the returned promise rejected with this error.

Example 4:

Input:

generatorFunction = function* () {
	let result = 0;

	yield new Promise((res) => setTimeout(res, 100));

	result += yield new Promise((res) => res(1));

	yield new Promise((res) => setTimeout(res, 100));

	result += yield new Promise((res) => res(1));

	return result;
};

cancelledAt = null;

Output:

Explanation:

4 promises are yielded. Two of those promises have their values added to the result. After 200ms, the generator finishes with a value of 2, and that value is resolved by the returned promise.

Example 5:

Input:

generatorFunction = function* () {
	let result = 0;

	try {
		yield new Promise((res) => setTimeout(res, 100));

		result += yield new Promise((res) => res(1));

		yield new Promise((res) => setTimeout(res, 100));

		result += yield new Promise((res) => res(1));
	} catch (e) {
		return result;
	}

	return result;
};

cancelledAt = 150;

Output:

Explanation:

The first two yielded promises resolve and cause the result to increment. However, at t=150ms, the generator is cancelled. The error sent to the generator is caught and the result is returned and finally resolved by the returned promise.

Example 6:

Input:

generatorFunction = function* () {
	try {
		yield new Promise((resolve, reject) => reject('Promise Rejected'));
	} catch (e) {
		let a = yield new Promise((resolve) => resolve(2));

		let b = yield new Promise((resolve) => resolve(2));

		return a + b;
	}
};

cancelledAt = null;

Output:

Explanation:

The first yielded promise immediately rejects. This error is caught. Because the generator hasn't been cancelled, execution continues as usual. It ends up resolving 2 + 2 = 4.

Constraints:

• cancelledAt == null or 0 <= cancelledAt <= 1000
• generatorFunction returns a generator object

题目大意

有时候你会有一个长时间运行的任务，并且你可能希望在它完成之前取消它。为了实现这个目标，请你编写一个名为 cancellable 的函数，它接收一个生成器对象，并返回一个包含两个值的数组：一个 取消函数 和一个 promise 对象。

你可以假设生成器函数只会生成 promise 对象。你的函数负责将 promise 对象解析的值传回生成器。如果 promise 被拒绝，你的函数应将该错误抛回给生成器。

如果在生成器完成之前调用了取消回调函数，则你的函数应该将错误抛回给生成器。该错误应该是字符串 "Cancelled"（而不是一个 Error 对象）。如果错误被捕获，则返回的 promise 应该解析为下一个生成或返回的值。否则，promise 应该被拒绝并抛出该错误。不应执行任何其他代码。

当生成器完成时，您的函数返回的 promise 应该解析为生成器返回的值。但是，如果生成器抛出错误，则返回的 promise 应该拒绝并抛出该错误。

提示：

• cancelledAt == null or 0 <= cancelledAt <= 1000
• generatorFunction 返回一个生成器对象

解题思路

1. 创建取消函数：

   • 首先，定义一个取消函数 cancel，这个函数会在被调用时使一个 Promise 被拒绝，拒绝原因是字符串 "Cancelled"。
   • 使用 Promise 的构造函数创建一个 cancelPromise，将拒绝逻辑绑定到 cancel 函数上。

2. 设置 promise 的异步执行：

   • 定义一个立即执行的异步函数，用于处理生成器的执行。
   • 在异步函数内，通过 generator.next() 开始执行生成器，并获取第一个结果。

3. 处理生成器的输出：

   • 使用 Promise.race 来处理生成器产生的 Promise 和 cancelPromise。这意味着如果 cancelPromise 被拒绝，生成器将会立即停止执行。
   • 如果生成器的当前 Promise 被解决，使用该值调用 generator.next() 继续执行生成器。如果发生错误，则调用 generator.throw() 传递错误并继续。

4. 返回结果：

   • 当生成器完成时，异步函数返回的值将成为返回的 Promise 的解决值。
   • 最后，返回包含取消函数和 Promise 的数组。

复杂度分析

• 时间复杂度：O(n)，其中 n 是生成器的步骤数。每次调用 next() 或 throw() 都是常量时间 O(1) 操作，复杂度与生成器的执行步骤数成正比。
• 空间复杂度：O(1)，空间复杂度主要来自于 Promise 的使用和生成器的状态，由于生成器的状态会保留在堆栈中，且每次调用 next() 或 throw() 时都会创建新的 Promise，因此整体空间复杂度为 O(1)，不随输入大小变化。

代码

/**
 * @param {Generator} generator
 * @return {[Function, Promise]}
 */
var cancellable = function (generator) {
	let cancel;
	const cancelPromise = new Promise((_, reject) => {
		cancel = () => reject('Cancelled');
	});
	// 每一个 promise rejection 都需要被 catch
	cancelPromise.catch(() => {});

	const promise = (async () => {
		let next = generator.next();
		while (!next.done) {
			try {
				next = generator.next(await Promise.race([next.value, cancelPromise]));
			} catch (error) {
				next = generator.throw(error);
			}
		}
		return next.value;
	})();
	return [cancel, promise];
};

/**
 * function* tasks() {
 *   const val = yield new Promise(resolve => resolve(2 + 2));
 *   yield new Promise(resolve => setTimeout(resolve, 100));
 *   return val + 1;
 * }
 * const [cancel, promise] = cancellable(tasks());
 * setTimeout(cancel, 50);
 * promise.catch(console.log); // logs "Cancelled" at t=50ms
 */

相关题目

题号	标题	题解	标签	难度
2648	生成斐波那契数列	[✓]
2649	嵌套数组生成器	[✓]