QT开发积累——通过利用hash显著提高程序运行的效率
原创QT开发积累——通过利用hash显著提高程序运行的效率
原创
Arya
发布于 2024-07-23 17:35:51
发布于 2024-07-23 17:35:51
引出
QT开发积累——通过利用hash显著提高程序运行的效率
巧妙利用hash显著 提高程序运行效率
for(PointData &point: DataPoint001){
// 点周围的线
QList<int> lineIndex;
for(LineData &line:DataLine001){
if(line.pointIndex.contains(point.pointIndex)){
lineIndex.append(line.lineIndex);
}
}
point.lineIndex = lineIndex;
// 点周围的面
QList<int> faceIndex;
for(FaceData &face:DataFace001){
if(face.points.contains(point.point)){
faceIndex.append(face.faceIndex);
}
}
point.faceIndex = faceIndex;
}将嵌套的循环拆开并优化，有可能显著提高运行速度。当前的嵌套循环的时间复杂度是 O(n⋅m)O(n⋅m)（其中 n 是 DataPoint001 的大小，m 是 DataLine001 或 DataFace001 的大小）。拆开循环并使用适当的数据结构，可以降低时间复杂度，从而提高性能。
优化思路
- **使用哈希表（散列表）优化查找**：将
DataLine001和DataFace001中的点与线、面的对应关系预处理为哈希表，这样可以在常数时间内完成查找。 - **避免重复的查找**：一次性构建索引，然后使用这些索引来填充每个点的数据。
优化后的代码
以下是优化后的代码示例：
// 假设PointData、LineData、FaceData结构如下：
struct PointData {
int pointIndex;
QList<int> lineIndex;
QList<int> faceIndex;
// 其他成员
};
struct LineData {
int lineIndex;
QList<int> pointIndex;
// 其他成员
};
struct FaceData {
int faceIndex;
QList<int> points;
// 其他成员
};
// 初始化数据结构
QList<PointData> DataPoint001;
QList<LineData> DataLine001;
QList<FaceData> DataFace001;
// 预处理：构建点到线、点到面的映射
QHash<int, QList<int>> pointToLinesMap;
QHash<int, QList<int>> pointToFacesMap;
// 预处理线数据
for (const LineData& line : DataLine001) {
for (int pointIndex : line.pointIndex) {
pointToLinesMap[pointIndex].append(line.lineIndex);
}
}
// 预处理面数据
for (const FaceData& face : DataFace001) {
for (int point : face.points) {
pointToFacesMap[point].append(face.faceIndex);
}
}
// 更新每个点的lineIndex和faceIndex
for (PointData& point : DataPoint001) {
point.lineIndex = pointToLinesMap.value(point.pointIndex);
point.faceIndex = pointToFacesMap.value(point.pointIndex);
}解释
- **预处理**：使用两个哈希表
pointToLinesMap和pointToFacesMap分别存储每个点到相关联的线索引和面索引的映射。这一步只需要遍历一次DataLine001和DataFace001，时间复杂度是 O(m)O(m)，其中 m 是DataLine001或DataFace001的大小。 - **查找**：在更新每个点的
lineIndex和faceIndex时，通过哈希表进行查找。这样，每次查找都是常数时间 O(1)O(1)，总的时间复杂度是 O(n)O(n)，其中 n 是DataPoint001的大小。
优化效果
原始代码的时间复杂度是 O(n⋅m)O(n⋅m)，优化后的代码时间复杂度是 O(n+m)O(n+m)，显著降低了计算量，尤其是在数据量较大的情况下，性能提升会更加明显。
总结
QT开发积累——通过利用hash显著提高程序运行的效率
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
