Optimierung eines Suchalgorithmus

Nukularfüsiker

array und word const machen. Die strlens aus der Schleife rausnehmen.

PrematureOptimizations

/// this function returns the index number of the first letter of the matching word 
static inline std::size_t SearchArray(const char *array, const char *word)
{
    std::size_t length((std::strlen(array));
    std::size_t word_length(std::strlen(word));
    std::size_t suc(0);
    for (std::size_t i(0);i!=length;++i)
    { 
        std::size_t j(0);
        if (array[i] == word[j]) 
            for (std::size_t z(i);z!=length;++z) 
            { 
                if (j == word_length)
                    break; 
                if (array[z] == word[j]) 
                { 
                    ++suc; 
                    ++j; 
                } 
                else 
                    suc=0; 
            }
        else 
            suc=0;
        if (suc == word_length)
            return i;
    } 
    return 0;
}

mazal

volkard schrieb:

An sich ist die ganz ok.
Bei einmaliger Suche gehts in Richtung Boyer-Moore und wird um so schneller, je länger das zu suchende word ist.
Bei vielmaliger Suche gehts in Richtung Präfix-Baum und wird extrem lecker.

Meinst du Präfix-Baum oder Suffix-Baum? Also eine Art Index auf dem String der durchsucht wird. Wobei wahrscheinlich ein Suffix-Baum oversized ist und man auch ganz toll eine Suffix-Array benutzen kann. Was auch fix zu implementieren ist und oft unterschätzt wird, ist ein q-Gramm-Index.

Sonst noch ein paar Stichwörter zum Suchen von Substrings

KMP, Rabin-Karp, Z-Box

Beim Suchen von mehreren Substrings in einem String gibt es den Aho-Corasick-Algorithmus.

wobei das schon genannte Boyer-Moore wahrscheinlich am einfachsten ist und KMP & Co. schlagen wirst, fall du nicht extream komische Strings benutzt.

volkard

Ich meinte Präfix-Baum und Boyer-Moore, weil sie furchtbar wichtige Tricks offenbaren und noch recht handlich zu implemetieren sind. Und es viele Quellen gibt, sie sozusagen die Klassiker sind. Naja, handlich kann auch fünfzehn Tage sein, wenn man das noch nie gemacht hat.
Es war in der Annahme, daß lekos sowas noch nie gemacht hat und er mit den beiden Suchworten neue Welten betritt.
Im Allgemeinen sind die beiden schon recht fix und können selbst mit den allerheftigsen Tricks nicht wirklich deklassiert werden. Soll heißen, mit der ersten funktionierenden Implementierung hat lekos schon fast das Optimum. Das macht mich froh. Danach noch 5% mehr Speed zu suchen, ist eine für uns beide höchst erquickliche Beschäftigung und ich würde mich freuen, wenn lekos dafür auch noch Zeit erübrigen könnte.

Du kannst in der zweiten for-Schleife noch suc == j als Laufbedingung einfügen. Dann wird abgebrochen, sobald der erste Buchstabe nicht passt.

/// this function returns the index number of the first letter of the matching word
static inline std::size_t SearchArray(const char *array, const char *word)
{
    std::size_t length(std::strlen(array));
    std::size_t word_length(std::strlen(word));
    std::size_t suc(0);
    for (std::size_t i(0); i!=length; ++i)
    {
        std::size_t j(0);
        if (array[i] == word[j])
            for (std::size_t z(i); z!=length && j == suc; ++z)
            {
                if (j == word_length)
                    break;
                if (array[z] == word[j])
                {
                    ++suc;
                    ++j;
                }
                else
                    suc=0;
            }
        else
            suc=0;
        if (suc == word_length)
            return i;
    }
    return 0;
}

Hallo Lekos:

strstr leistet das was du von hand programmierst - glaub ich - schon.
strstr ist sehr schnell ...

Gruß Frank

life

Oder auch: http://de.wikipedia.org/wiki/Knuth-Morris-Pratt-Algorithmus

strstr gibt den Zeiger im Feld zurück, man müsste also noch die Differenz zum Anfang bilden. Allerdings funktioniert strstr für den Fall, dass direkt an der ersten Stelle ein Match auftritt eindeutig.

Die Funktion, die hier beschrieben ist, gibt zwar dann 0 zurück (korrekt) man kann es aber nicht von einem "nix gefunden" unterscheiden. Sie sollte also zumindest -1 o.ä. für "nicht gefunden" zurück geben.

strstr liefert eindeutige Informationen.

Wenn man andere returns benötigt,
kann man diese einfach und schnell umrechnen.

strstr funktioniert leider nicht mit binär Daten.
In diesem Fall müsste man dann selbst was eigenes programmieren ...

strstr ist auf vielen Systemen extrem schnell,
es ist schwierig bis unmöglich etwas schnelleres,
mit c/c++ selbst zu programmieren ...

Wie auch immer man sollte die Performance der eigenen Implementierung mit strstr Vergleichen.

Gruß Frank

Th69

Volkard schrieb:

Soll heißen, mit der ersten funktionierenden Implementierung hat lekos schon fast das Optimum. Das macht mich froh. Danach noch 5% mehr Speed zu suchen, ...

Dann am besten gleich die Boyer-Moore-Horspool-Variante benutzen (Suchrichtung umdrehen): http://en.wikipedia.org/wiki/Boyer–Moore–Horspool_algorithm