🚀 go-pugleaf

Hallo,

Ik heb een hier een C++ functie gemaakt die controleert of een (kleinere)
std::vector voorkomt in een andere, grotere std::vector (in de originele
volgorde).

Je vindt de code onderaan dit bericht, dit doet perfect wat het moet doen
(is ook niet moeilijk ;-)
Nu is echter die 'findPattern(...)' zowat de belangrijkste functie uit mijn
programma en wordt voortdurend opgeroepen met (grote) vectors. (Er worden in
totaal tientallen tot honderden megabytes doorzocht...)

Het probleem is dat mijn stukje (sequentiele) code niet echt snel is, en ik
ben dus op zoek naar elke mogelijke optimalizatie.

In eerste instantie dacht ik aan <algorithm> uit de C++ Standard Library:

'find' doorzoekt een sequentie/container naar 1 bepaalde waarde, terwijl we
zoeken naar een andere sequentie/container...

'find_first_of' onderzoekt of 1 van de elementen uit de 2e
sequentie/container in de 1e zit, terwijl we dus willen weten of de
volledige 2e sequentie/container in de 1e zit...

'includes' veronderstelt een gesorteerde input (of op zijn minst een
operator< ?)
Maar sorteren mag niet want dan gaat de betekenis van de vector verloren...
Een (zelf gemaakte) binaire search kan dus ook niet, want de vector is niet
gesorteerd (en moet in de originele orde blijven).


Dus weet iemand of ik mijn 'findPattern(...)' kan formuleren als een call
naar de Standard Library? (in de hoop dat die code efficienter is)

Of weet iemand een URL/library/... met optimalizaties voor dit soort zoeken?

De functie, zoals ze hieronder staat, moet eigenlijk niet letterlijk. Dwz
een boolean als return als de 2e vector in de 1e vector voorkomt, volstaat
al.

Alvast bedankt !



// Search for 'pattern' in large 'string' 'dump'
// return number of matches
int findPattern(const vector<BYTE>& dump, const vector<BYTE>& pattern) {
    int nMatches = 0;

    if (dump.size() >= pattern.size())

        int i = 0;
        while (i < dump.size())

        // not yet at end of dump
            if (dump[i] == pattern[0])

            // first byte of pattern matches a byte of dump
                int j = 0;
                while ((j < pattern.size()) && (dump[i+j] == pattern[j])) {
                // not yet at end of pattern
                    ++j;
                }
                if (j == pattern.size()) {  // reached end of pattern
                    // perfect match from dump[i] tot dump[i+j-1]
                    ++nMatches;
                }
            }
            ++i;      // move to next byte
        }
    }
    return nMatches;
}