如何提高QVector查找的效率?

Question

由于某种原因，我需要多次遍历一张图像，并且我需要知道我处理了哪些像素点。

所以我使用QVector来存储我每次处理的像素点的位置，这样我就可以使用它来确定下一次迭代的时间。

示例如下:

QVector<int> passed;
for(int n = 0; n < 10; n++) { // Multiple traversals
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
if(......) { // Meeting certain conditions
if(!passed.contains(y*width+x)) {
// do something
passed.append(y*width+x);
}
}
}
}
}

我花了很多时间来处理传入的.contains()步骤!

你知道如何优化搜索速度吗?

或者有更好的方法让我更容易地确定已处理的某些像素?

Answer 1

使用

QVector<bool> passed(height * width, false);
for(int n = 0; n < 10; n++) { // Multiple traversals
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
if(......) { // Meeting certain conditions
int pos = y*width+x;
if(!passed.at(pos)) {
// do something
passed[pos] = true;
}
}
}
}
}

或者你可以通过重新排序内部条件来更快。如果计算if(......)不是微不足道的，它可能会快得多。但是你必须确保这个改变不会影响你的算法。

QVector<bool> passed(height * width, false);
for(int n = 0; n < 10; n++) { // Multiple traversals
for(int y = 0; y < height; y++) {
for(int x = 0; x < width; x++) {
int pos = y*width+x;
if(!passed.at(pos)) {
if(......) { // Meeting certain conditions
// do something
passed[pos] = true;
}
}
}
}
}

Answer 2

QVector中的元素必须按顺序存储吗?如果没有，请尝试QSet或std::unordered_set。

如果必须按顺序存储这些索引，有两种方法:

1. 将vector替换为列表，如std::list<>，当附加
时速度更快
2. 继续使用QVector，但调用reserve以避免在附加
时无用的复制。
3. 一种新的顺序存储方式:创建一个与图像大小相同的qvector, vector中的每个元素都记录该元素的顺序。例如，第4个元素为32表示第4个像素是第33个访问像素。