Home > Enterprise >  How to improve the efficiency of QVector lookup?
How to improve the efficiency of QVector lookup?

Time:10-29

For some reason, I need to traverse an image many times and I need to know which pixel points I have processed.

So I use a QVector to store the location of the pixel points I have processed each time so I can use it to determine the next time I iterate.

Examples are as follows。

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

I spent a lot of time processing the passed.contains() step!

Do you know how I can optimize the search speed?

Or is there a better way to make it easier for me to determine certain pixels that have been processed?

CodePudding user response:

Use this:

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

Or maybe you can get even faster by reordering the inner conditions. It could be significantly faster if evaluation if(......) is not trivial. But you must be sure that this change does not affect your algorithm.

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

CodePudding user response:

Is elements in QVector must be stored in order? if not, try QSet or std::unordered_set. Hash works well when searching.

If you must store these indices in order, there's to ways:

  1. replace vector with a list, like std::list<>, it's faster when appending
  2. keep using QVector but call reserve to avoid useless copying when appending
  3. a new way to store with order: create a qvector the same size as the image, and each element in the vector recored the order of this element. For example, the 4rd element is 32 means the 4rd pixel is the 33th visited pixel.
  • Related