javascript - 如何使用字典提高性能?
问题描述
我的问题是,我在这段代码中没有最快的性能。我有 30 个测试,我必须用这段代码来解决,但我只解决了 28 个,直到它抛出一个错误,因为它需要很长时间。
那是我的示例输入:
queryType: ["insert", "insert", "addToValue", "addToKey", "get"]
query: [[1,2], [2,3], [2], [1], [3]]
If queryType[i] === "insert" -> Add at query[i][0] value query[i][1].
If queryType[i] === "addToValue" -> Add query[i][0] to every value.
If queryType[i] === "addToKey" -> Add offset.
If queryType[i] === "get" -> Add query[i][0] to result value.
那是我当前的代码:
function testHashMap(queryType, query) {
let hash = {};
let result = 0;
let offset = 0;
let len = queryType.length;
for (let i = 0; i < len; ++i) {
let querys = query[i][0];
switch (queryType[i]) {
case "insert":
hash[querys] = query[i][1];
break;
case "addToValue":
for (let key in hash) {
hash[key] += querys;
}
break;
case "addToKey":
offset += querys;
break;
case "get":
result += hash[querys - offset];
break;
}
}
return result;
}
有人知道如何提高此功能的速度吗?感谢您的时间!
解决方案
正如 Matt Timmermans 在评论中指出的那样,加速的一种方法可能不是实际增加每个值。假设我们的起始值为
[1, 1, 1, 1]
现在为每个元素添加 3,我们记录一个 general offset
, 3。
假设我们现在得到一个插入,[2, 4]
. 我们想将第三个元素设置为 4,所以我们首先减去我们的偏移量。4 - 3 = 1 所以我们实际上根本不改变第三个元素!
现在我们被请求到get
索引 2 处的元素。我们添加我们的一般偏移量:
1 + 3 = 4
正如预期的那样。
这样,所有更新都保持O(1)
时间复杂度,这应该会运行得更快。
推荐阅读
- r - 是否有基于列返回行值的 R 函数?
- python - cartopy 模块不会更新到版本 0.20.0
- amazon-web-services - 创建指标警报失败:ValidationError:MetricName 不得包含非 ASCII 字符
- reactjs - Reacjs如何在datagrid中返回选定的行
- amazon-web-services - 有没有办法在同一区域将 lightsail vpc 与 aws vpc 对等/连接?
- .net-core - 两种关系都可以使用 MatchId 作为外键
- reactjs - React Table 7 错误:有条件地调用“React.useCallback”
- javascript - React/JS 如何将特定的映射元素分配给状态?
- pandas - read_sql() 有效,但 to_sql 给出错误 Orcale DB sqlalchemy
- react-native - 使用 Expo-three 加载 .obj 文件?