批处理查询

2756. 批处理查询

将多个小查询批处理为单个大查询可以是一种有用的优化。请编写一个名为 QueryBatcher 的类来实现这个功能。

它的构造函数应接受两个参数：

一个异步函数 queryMultiple ，它接受一个字符串键的数组作为输入。它将返回一个与输入数组长度相同的值数组。每个索引对应于与 input[i] 相关联的值。可以假设该异步函数永远不会被拒绝。
一个以毫秒为单位的节流时间t。

该类有一个方法：

async getValue(key)：接受一个字符串键，并返回一个解析后的字符串值。传递给此函数的键值最终应传递给 queryMultiple 函数。在 t 毫秒内不应连续调用 queryMultiple 。第一次调用 getValue 时，应立即使用该单个键调用 queryMultiple 。如果在 t 毫秒后再次调用了 getValue ，则所有传递的键应传递给 queryMultiple ，并返回最终结果。可以假设传递给该方法的每个键都是唯一的。

下图说明了节流算法的工作原理。每个矩形代表 100毫秒。节流时间为 400毫秒。

Throttle info

示例 1：

输入：
queryMultiple = async function(keys) { 
  return keys.map(key => key + '!');
}
t = 100 
calls = [
 {"key": "a", "time": 10}, 
 {"key": "b", "time": 20}, 
 {"key": "c", "time": 30}
]
输出：[
 {"resolved": "a!", "time": 10},
 {"resolved": "b!", "time": 110},
 {"resolved": "c!", "time": 110}
]
解释：
const batcher = new QueryBatcher(queryMultiple, 100);
setTimeout(() => batcher.getValue('a'), 10); // "a!" at t=10ms
setTimeout(() => batcher.getValue('b'), 20); // "b!" at t=110ms
setTimeout(() => batcher.getValue('c'), 30); // "c!" at t=110ms

queryMultiple 简单地给键添加了"!"。 
在 t=10ms 时，调用 getValue('a')，立即调用 queryMultiple(['a']) 并立即返回结果。 
在 t=20ms 时，调用 getValue('b')，但查询需要等待。 
在 t=30ms 时，调用 getValue('c')，但查询需要等待。 
在 t=110ms 时，调用 queryMultiple(['b', 'c']) 并立即返回结果。

示例 2；

输入：
queryMultiple = async function(keys) {
  await new Promise(res => setTimeout(res, 100));
  return keys.map(key => key + '!');
}
t = 100
calls = [
 {"key": "a", "time": 10},
 {"key": "b", "time": 20},
 {"key": "c", "time": 30}
]
输出：[
  {"resolved": "a!", "time": 110},
  {"resolved": "b!", "time": 210},
  {"resolved": "c!", "time": 210}
]
解释：
这个例子与示例 1 相同，只是在 queryMultiple 中有一个 100ms 的延迟。结果也相同，只是 promise 的解析时间延迟了 100ms。

示例 3：

输入：
queryMultiple = async function(keys) { 
  await new Promise(res => setTimeout(res, keys.length * 100)); 
  return keys.map(key => key + '!');
}
t = 100
calls = [
  {"key": "a", "time": 10}, 
  {"key": "b", "time": 20}, 
  {"key": "c", "time": 30}, 
  {"key": "d", "time": 40}, 
  {"key": "e", "time": 250}
  {"key": "f", "time": 300}
]
输出：[
  {"resolved":"a!","time":110},
  {"resolved":"e!","time":350},
  {"resolved":"b!","time":410},
  {"resolved":"c!","time":410},
  {"resolved":"d!","time":410},
  {"resolved":"f!","time":450}
]
解释：
在 t=10ms 时，调用 queryMultiple(['a']) ，在 t=110ms 时解析。 
在 t=110ms 时，调用 queryMultiple(['b', 'c', 'd']) ，在 t=410ms 时解析。 
在 t=250ms 时，调用 queryMultiple(['e']) ，在 t=350ms 时解析。 
在 t=350ms 时，调用 queryMultiple(['f']) ，在 t=450ms 时解析。

提示：

0 <= t <= 1000
0 <= calls.length <= 10
1 <= key.length <= 100
所有的键值都是唯一的

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

/** * @param {Function} queryMultiple * @param {number} t * @return {void} */ var QueryBatcher = function(queryMultiple, t) { }; /** * @param {string} key * @return {Promise<string>} */ QueryBatcher.prototype.getValue = async function(key) { }; /** * async function queryMultiple(keys) { * return keys.map(key => key + '!'); * } * * const batcher = new QueryBatcher(queryMultiple, 100); * batcher.getValue('a').then(console.log); // resolves "a!" at t=0ms * batcher.getValue('b').then(console.log); // resolves "b!" at t=100ms * batcher.getValue('c').then(console.log); // resolves "c!" at t=100ms */

javascript 解法, 执行用时: 68 ms, 内存消耗: 41.4 MB, 提交时间: 2023-10-15 14:41:23

/**
 * @param {Function} queryMultiple
 * @param {number} t
 */
var QueryBatcher = function(queryMultiple, t) {
    this.fn = queryMultiple
    this.cooldown = t
    this.batch = []
    this.cooling = false
};

QueryBatcher.prototype.queryBatched = async function() {
    const batch = this.batch
    this.batch = []
    const keys = batch.map(v => v[1])
    const results = await this.fn(keys)
    for (const [i, res] of results.entries()) {
        batch[i][0](res)
    }
}

QueryBatcher.prototype.consume = async function() {
    if (this.batch.length === 0) return
    if (this.cooling) return
    this.queryBatched()
    this.cooling = true
    setTimeout(() => {
        this.cooling = false
        this.consume()
    }, this.cooldown)
}

/**
 * @param {string} key
 * @returns Promise<string>
 */
QueryBatcher.prototype.getValue = async function(key) {
    return new Promise((resolve, reject) => {
        this.batch.push([resolve, key])
        this.consume()
    })
};

/**
 * async function queryMultiple(keys) { 
 *   return keys.map(key => key + '!');
 * }
 *
 * const batcher = new QueryBatcher(queryMultiple, 100);
 * batcher.getValue('a').then(console.log); // resolves "a!" at t=0ms 
 * batcher.getValue('b').then(console.log); // resolves "b!" at t=100ms 
 * batcher.getValue('c').then(console.log); // resolves "c!" at t=100ms 
 */

上一题

下一题

详情