如何提高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);
                }
            }
        }
    }
}

我花了很多时间处理 passed.contains() 步骤！

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

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

Answer 1

QVector中的元素必须按顺序存储吗？如果不是，请尝试 QSet 或 std::unordered_set。哈希在搜索时效果很好。

如果必须按顺序存储这些索引，有以下方法：

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

Answer 2

使用这个：

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;
                }
            }
        }
    }
}

如何提高QVector查找的效率？

How to improve the efficiency of QVector lookup？

c++

qt

opencv

vector