Finding Records

In the last blog post, I found out that  one can load pretty quickly several thousand or even tens of thousands records to memeory. This time I would like to examine how quickly you can find records within such a list.

Autocomplete

As a use case, I have a picklist with auto-completion in mind. The user enters separately (partial) words separated by spaces. He receives a list with possible matches after each key down.

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

Performance analysis

To measure the performance of the method shown above, I’ve prepared 1,000 queries. These contain up to three words of different length again randomly selected from the list of data. The search can be quickly finished if only one letter is specified. Then the hit list is most likely filled after a few queried list entries and the search can be cancelled. However, given many words it can happen that the complete list must be queried before the search inevitably finishes. I will evaluate the times for each of the 1,000 queries and show them as a histogram. Most interesting are the average and maximum search time. Both could affect the „user experience“ (UX). The performance analysis will be made with a list of 4,000 entries and another one with 20,000 entries. The measurement was carried out on a standard desktop computer.

Result

With a list size of 4,000 items the average time per query is 0.03 seconds and the longest search lasted not more than 0.1 seconds. Even with 20,000 items the search speed is still very neat taking about 0.1 seconds on average. But it may take up to half a second in the worst case.

TimePerQuery

Conclusion

The full-text search within 20,000 records in memory is pretty fast even with a simple implementation. In the next blog post I will show an autocomplete picklist based on the query function above.
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: