Quick check for a equal value in a integer vector

[danjiun]

Hi my friends,
i want to ask , if somebody know some instruction for make next code quicker :

bool haveFree(const vector<int> &F)
{
    for(int x : F) { if (x<0) return true;}
    return false;
}

Thanks for any help.
Daniel

[theturk1234]

No, I think this is about as optimized as it can get!
Is there any particular reason you need it this fast?

[danjiun]

Hi, thanks for your answer.
May be exist a assembler instruction to check iteratively in same range, and would be quicker (MMX?), but this may be would be mission of C++ to implement it for a standard library ("if_any") and for specialization for integer.
Reason is this because, a call from a kernel of a algorithm is to this function, and it is often. The algorithm' mission is to calculate a "minimal combination's of pih's", and this is part of a algorithm to found optimal algorithms for order elements by comparison. :)
I already try to minimize a call to this function, maintaining another array, which count how many place of F are less as 0.
greatings, Daniel

[ne555]

nolyc wrote:

You're trying to do X, and you thought of solution Y. So you're asking about solution Y, without even mentioning X. The problem is, there might be a better solution, but we can't know that unless you describe what X is.

[danjiun]

Even now it is not evident that solution Z is better as solution Y.
All depend of Y have a fast way or not, using processors capabilities.
If Y have a faster way, then Y would be better as Z, so i ask about this.
Even using solution Z is not vey much better as use solution without quick way.
Anyway i can give a code, from calling function. Explain everything would be very long.

int foundMinPihcInLine(int minPihc,int validLineI,int nextPihcsB)
{
    int lineI = m_validLines[validLineI];
    int lastP = m_lines[lineI];//point to last pihs,last pointers from this line
    if (haveFree(F)) {
        //so we can simply choice a minimal of F(x)
        int minLPih = pasa;
        int minLPihc = pasa;
        int minLPihPlace = 0;
        int size = m_freePihss[lineI].size();//freePihs.size();
        for(int t=0;t<size;t++) {
            int pih = m_freePihss[lineI][t];//freePihs[t];
            int pihc = convertPihToPihc(pih,m_Fs[lineI]);
            if (pihc<minLPihc) { minLPihc=pihc; minLPih=pih; minLPihPlace=t;}
        }
        if (minLPihc<minPihc) {
            minPihc = minLPihc;
            m_newValidLines.clear();
        }
        if (minLPihc<=minPihc) { //simply continue line
            m_pihs.push_back(minLPih);//data place 1
            m_pointers.push_back(lastP);//it is continuation from previous
            ivec newF(m_Fs[lineI]);//ivec newF(F);
            vector<int> newFreePihs(m_freePihss[lineI]);
            newFreePihs[minLPihPlace] = m_freePihss[lineI].back();//freePihs.back();
            newFreePihs.resize(size-1);
            m_lines.push_back(m_pihs.size()-1);//line data 1
            m_Fs.push_back(newF);//line data 2
            m_freePihss.push_back(newFreePihs);//line data 3
        }
        return minPihc;
    }
    //we collect all pih's which result in a minimal pihc (minPihc)
    ivec minPihs;
    ivec pihPlaces;//places inside freePihs
    int size = m_freePihss[lineI].size();//freePihs.size();
    for(int t=0;t<size;t++) {
        int pih = m_freePihss[lineI][t];//freePihs[t];
        int minPihcPih = foundMinPihcForPih(pih,m_Fs[lineI],lineI);//similar to foundMinRec2
        if (minPihcPih==minPihc) {
            minPihs.push_back(pih);
            pihPlaces.push_back(t);
        }
        else if (minPihcPih<minPihc) {
            minPihs.clear();
            minPihs.push_back(pih);
            minPihc = minPihcPih;
            pihPlaces.clear();
            pihPlaces.push_back(t);
            m_newValidLines.clear();//we invalidate all previous lines, which give a smaller pihc
        }
    }
    int xc = pairsP[minPihc].first;
    int yc = pairsP[minPihc].second;
    int lastFreePih = m_freePihss[lineI].back();//freePihs.back();
    //save all optimal results :
    for(int t=0;t<minPihs.size();t++) {
        int pih = minPihs[t];
        int line = m_lines.size();
        m_newValidLines.push_back(line);
        int pointTo = m_pihs.size();
        m_pihs.push_back(pih);//data place 1
        m_pointers.push_back(lastP);//data place 2
        ivec newF(m_Fs[lineI]);//ivec newF(F);
        newF[pairsP[pih].first] = xc;
        newF[pairsP[pih].second] = yc;
        //vector<int> newFreePihs(freePihs);
        vector<int> newFreePihs(m_freePihss[lineI]);
        newFreePihs[pihPlaces[t]] = lastFreePih;
        newFreePihs.resize(size-1);
        m_lines.push_back(pointTo);//line data 1
        m_Fs.push_back(newF);//line data 2
        m_freePihss.push_back(newFreePihs);//line data 3
    }
    return minPihc;
}

Anyway thanks for your try.
Daniel

[Duthomhas]

You aren't going to find a magic solution to doing an O(n) search any faster.

If you want to improve the speed, use a std::unordered_set to check for membership, and the std::vector for the sequence ordering. Notice the trade-off: use more memory for a faster membership predicate.

[danjiun]

A std::unordered_set is quick for check something, but use more memory and also, if i need to copy a unordered_set, its more slowly. Sometimes i need to copy everything.
So, at this moment my solution for this is use another array of counters, which count how many places of F are below of 0. Actually code look like :

int foundMinPihcInLine(int minPihc,int validLineI,int nextPihcsB)
{
    int lineI = m_validLines[validLineI];
    int lastP = m_lines[lineI];//point to last pihs,last pointers from this line
    if (m_FsFreeN[lineI]==0) {
        //so we can simply choice a minimal of F(x)
        int minLPih = pasa;
        int minLPihc = pasa;
        int minLPihPlace = 0;
        int size = m_freePihss[lineI].size();//freePihs.size();
        for(int t=0;t<size;t++) {
            int pih = m_freePihss[lineI][t];//freePihs[t];
            int pihc = convertPihToPihc(pih,m_Fs[lineI]);
            if (pihc<minLPihc) { minLPihc=pihc; minLPih=pih; minLPihPlace=t;}
        }
        if (minLPihc<minPihc) {
            minPihc = minLPihc;
            m_newValidLines.clear();
        }
        if (minLPihc<=minPihc) { //simply continue line
            m_pihs.push_back(minLPih);//data place 1
            m_pointers.push_back(lastP);//it is continuation from previous
            ivec newF(m_Fs[lineI]);//ivec newF(F);
            vector<int> newFreePihs(m_freePihss[lineI]);
            newFreePihs[minLPihPlace] = m_freePihss[lineI].back();//freePihs.back();
            newFreePihs.resize(size-1);
            m_lines.push_back(m_pihs.size()-1);//line data 1
            m_Fs.push_back(newF);//line data 2
            m_FsFreeN.push_back(0);
            m_freePihss.push_back(newFreePihs);//line data 3
        }
        return minPihc;
    }
    //we collect all pih's which result in a minimal pihc (minPihc)
    ivec minPihs;
    ivec pihPlaces;//places inside freePihs
    int size = m_freePihss[lineI].size();//freePihs.size();
    for(int t=0;t<size;t++) {
        int pih = m_freePihss[lineI][t];//freePihs[t];
        int minPihcPih = foundMinPihcForPih(pih,m_Fs[lineI],lineI);//similar to foundMinRec2
        if (minPihcPih==minPihc) {
            minPihs.push_back(pih);
            pihPlaces.push_back(t);
        }
        else if (minPihcPih<minPihc) {
            minPihs.clear();
            minPihs.push_back(pih);
            minPihc = minPihcPih;
            pihPlaces.clear();
            pihPlaces.push_back(t);
            m_newValidLines.clear();//we invalidate all previous lines, which give a smaller pihc
        }
    }
    int xc = pairsP[minPihc].first;
    int yc = pairsP[minPihc].second;
    int lastFreePih = m_freePihss[lineI].back();//freePihs.back();
    //save all optimal results :
    for(int t=0;t<minPihs.size();t++) {
        int pih = minPihs[t];
        int line = m_lines.size();
        m_newValidLines.push_back(line);
        int pointTo = m_pihs.size();
        m_pihs.push_back(pih);//data place 1
        m_pointers.push_back(lastP);//data place 2
        ivec newF(m_Fs[lineI]);//ivec newF(F);
        newF[pairsP[pih].first] = xc;
        newF[pairsP[pih].second] = yc;
        vector<int> newFreePihs(m_freePihss[lineI]);
        newFreePihs[pihPlaces[t]] = lastFreePih;
        newFreePihs.resize(size-1);
        m_lines.push_back(pointTo);//line data 1
        m_Fs.push_back(newF);//line data 2
        int FsFreeN = m_FsFreeN[lineI];
        if (m_Fs[lineI][pairsP[pih].first]<0) FsFreeN--;
        if (m_Fs[lineI][pairsP[pih].second]<0) FsFreeN--;
        m_FsFreeN.push_back(FsFreeN);
        m_freePihss.push_back(newFreePihs);//line data 3
    }
    return minPihc;
}

Thanks also for you idea Duoas.
Daniel

[danjiun]

I found some information about MMX,SIMD and similar instructions together with C++ :
One, is try to use a activation of a flag of compiler gcc with -03.
Information i found at :
https://gcc.gnu.org/projects/tree-ssa/vectorization.html
Below are examples in which gcc will be able to use vectorization.
Also : -O3 -mfpmath=sse
At
https://gcc.gnu.org/onlinedocs/gcc-4.5.3/gcc/i386-and-x86_002d64-Options.html
are compiler options.
A example at : http://tommesani.com/index.php/component/content/article/2-simd/42-mmx-examples.html
A real example using assembler with C++ :
http://www.codeproject.com/Articles/38519/Using-Assembler-and-SSE-SSE-instructions-for-dra
Another : http://www.codeproject.com/Articles/4662/High-performance-computing-from-C-to-MMX
Also exist a C++ interface for use MMX
More :
http://www.codeproject.com/Articles/4662/High-performance-computing-from-C-to-MMX
http://www.codeproject.com/Articles/12115/STL-like-template-based-coding-with-the-MMX-SSE-ex

I send this in case somebody have interest in it.

greating, Daniel

[Calcushtag]

I have a question in mind. Since the int is 4 byte, By using reference in for loop, Is it make the code quicker or not?
for(int& x: f) ...
Is using reference make code faster in bigger data type or it is just memory saver?

[Thomas1965]

According to Bjarne Stroustrup we should prefer the stl algorithms over loops. In this case probably find_if would be a better option.

[danjiun]

Thanks, it is also a idea.
But may be a good compiler already will compile like this, i dont know.
greatings, Daniel