Suche schnellen Suchalgorithmus auf 10000 Record-Einträge

[Der_Ventilator]

Hi, für meinen Software-Mp3-Player brauche ich eine Methode die sehr schnell (<50 ms wären toll) 10000 Einträge eines Records durchsuchen kann.

Zur Zeit gehe ich per for-to-do das ganze Array durch und vergleiche jeden Eintrag:

Delphi-Quellcode:

     if (CurrentSearch<>'')  and(

      ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].Filename ) ) <>0 )
      or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].Path ) ) <>0 )
      or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.Titel ) ) <>0 )
      or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.Artist ) ) <>0 )
      or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.Album) ) <>0 )
     or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.Genre) ) <>0 )
     or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.Comment) ) <>0 )
     or
       ( pos( ansilowercase( CurrentSearch ) ,
         ansilowercase(  Mp3Daten[ListenNummer,ElementNummer].id3tag.year) ) <>0 )
                                  )
       then match:=true else match:=false;

Das geht bei 2000 Einträge noch fast instantan, aber bei 10000 Einträgen dauert es über 250ms, was man optisch an einer Verzögerung sieht (ich suche nach jedem KeyDown im Suchfeld). Außerdem habe ich eine ODER-Suche und eine UND-Suche programmiert, sodass ich mitunter mehrmals das Array durchlaufen muss.

Wie kann ich die Suche beschleunigen?

Eine bessere pos-Funktion?
Oder gibt es einen schnelleren Algorithmus? Aber ich muss doch alle Items ansprechen=> Items irgendwie anders gestalten=>Hash-Werte?=> das dürfte aber bei einer Volltextsuche nicht funktionieren...

[Mavarik]

Hallo!

Wie wäre es mit vorsortierten Indexlisten und dann mit Intervalschachtelung?

Frank :coder:

[SirThornberry]

mir viel als erstes folgendes auf:

Delphi-Quellcode:

ansilowercase( CurrentSearch )

Bei jedem Aufruf von Pos führst du AnsiLowercase auf "CurrentSearch" aus. Es wäre sinnvoller das einmal vor allen Bedingungen zu machen. Dann spaarst du dir Pro Schleifendurchlauf 8 mal das AnsiLowerCase und das 10000 mal (für jeden Schleifendurchlauf). Also insgesammt nur 1 mal AnsiLowerCase anstelle von 80000 mal.

[omata]

Schau doch mal hier

[Der_Ventilator]

Ok, das mit ansilowercase ist richtig. Mal sehen wie viel das bringt.


Die 'binären Suche' von Wikipedia (Danke an omata) :

Zitat:

Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise sortiert sind.
Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Das funktioniert nicht, weil ich nicht den ganzen String suche, sondern Teilstücke.
Z.B. könnte ich nach Bandnamen sortieren, dann würde ich aber nicht 'Subway to Sally' finden, wenn ich nur 'Sally', 'Sal' oder 'way' eingebe.