Datensätze finden

Im letzten Blogpost habe ich festgestellt, dass man einige tausend oder auch zigtausend Datensätze recht schnell in den Speicher laden kann. Dieses Mal möchte untersuchen, wie schnell man innerhalb einer solchen Liste Datensätze finden kann.

Autocomplete

Als Anwendungsfall habe ich eine Suche mit Autovervollständigung im Auge: Der User gibt einzelne (Teil-)wörter mit Leerzeichen getrennt ein. Er bekommt nach jedem Tastendruck eine Vorschlagsliste mit möglichen Treffern angezeigt.

Die Listenklasse aus dem letzten Blog wird dazu um die Funktion „Query“ erweitert. Diese Funktion erwartet einen Suchstring z.B. „spark hanno“. Sie sucht innerhalb der Liste nach Datensätzen, die alle Teilwörter enthalten. Ist eine vorgegebene Anzahl an Treffern erreicht oder die Liste bis zum Ende durchsucht, bricht die Suche ab und gibt die Trefferliste zurück.

Function: Query
    Returns
        listBlz: cBlz
    Parameters
        String: sQuery
        Number: nMaxResult
    Local variables
        String: asQueryParts[*]
        Number: nCountQueryParts
        Number: nListIdx
        Number: nQueryPartIdx
        listBlz: listBlzResult
        Boolean: bNotFound
    Actions
        ! Clean Query
        Call SalStrTrim( sQuery, sQuery )
        ! Tokenize Query-String to single words
        Set nCountQueryParts = SalStrTokenize( sQuery, '', ' ', asQueryParts )
        If ( nCountQueryParts = 0 )
            ! return empty list
            Return listBlzResult
        ! Validate / normalize parameters
        If (nMaxResult <= 0 )
            ! default to max 10 hits
            Set nMaxResult = 10
        ! Query all interesting Fields of our list
        While (nListIdx < __nLength )
            Set bNotFound = FALSE
            Set nQueryPartIdx = 0
            While ( nQueryPartIdx < nCountQueryParts )
                ! check if QueryPart can be found in one of the fields
                ! SalStrScan ist case insensitive - so there is no need for lower or upper strings
                If (
                            (SalStrScan(__acBlz[nListIdx].sBezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sOrt, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sKurzbezeichnung, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBlz, asQueryParts[nQueryPartIdx]) = -1)
                        AND    (SalStrScan(__acBlz[nListIdx].sBic, asQueryParts[nQueryPartIdx]) = -1)
                        )
                    Set bNotFound = TRUE
                    ! Querypart could not be found so current item does not match -> break inner while
                    Break
                Set nQueryPartIdx = nQueryPartIdx + 1
            ! Add item to list if every querypart matched
            If ( NOT bNotFound )
                Call listBlzResult.Add( __acBlz[nListIdx] )
                ! break outer while if we have enough items in the resulting list
                If ( listBlzResult.Length() >= nMaxResult )
                    Break
            Set nListIdx = nListIdx + 1
        Return listBlzResult

Performanceanalyse

Um die Leistungsfähigkeit der oben gezeigten Funktion zu messen, habe ich zunächst 1.000 Queries vorbereitet. Diese enthält jeweils ein bis drei Teilwörter verschiedener Länge, die wiederum zufällig aus der Liste der Daten ausgewählt werden. Die Suche kann sehr schnell beendet sein wenn z.B. nur ein Buchstabe angegeben wurde, dann ist die Trefferliste höchstwahrscheinlich nach wenigen untersuchten Listeneinträgen gefüllt und die Suche kann abgebrochen werden. Hat man hingegen viele Teilwörter angegeben kann es vorkommen, dass die komplette Liste durchsucht werden muss, bis die Suche zwangsläufig abgebrochen werden kann. Ausgewertet werden die Zeiten für jeden der 1.000 Beispielquerys und als Histogramm aufgetragen. Interessant sind die mittlere und die maximale Suchzeit. Beides dürfte sich auf die „User Experience“ (UX) auswirken. Einmal wurde die Suche in einer Liste mit etwas über 4.000 Einträgen vorgenommen, ein zweites Mal war die Liste knapp 20.000 Einträge lang. Ausgeführt wurden die Messungen auf einem handelsüblichen Desktoprechner.

Ergebnis

Bei einer Listengröße von 4.000 Elementen liegt die durchschnittliche Zeit pro Query bei 0,03 Sekunden und die längste Suche dauerte nicht länger als 0,1 Sekunden. Auch bei 20.000 Elementen ist die Suchgeschwindigkeit immer noch sehr ordentlichen mit 0,1 Sekunden. Sie kann aber auch bis zu einer halben Sekunde dauern.

TimePerQuery

Fazit

Die Volltextsuche innerhalb von 20.000 Datensätzen im Speicher ist selbst mit einer einfachen Implementierung performant. Damit steht der Entwicklung einer Autocomplete-Picklist nichts mehr im Weg. Diese möchte ich im nächsten Blogpost vorstellen.

Advertisements

Über thomasuttendorfer
Ich bin Entwicklungsleiter bei der Softwarefirma [ frevel & fey ] in München. Wir entwickeln Business-Software für Verlage und verwenden dafür den Gupta Team-Developer sowie Visual Studio.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: