Speedproblem beim Durchsuchen von Strings
-
Hallo,
in meinem aktuellen Projekt ist es notwendig, dass eine Liste von Strings daraufhin durchsucht wird, ob ein String schon vorhanden ist. Natürlich könnte ich die Liste nacheinander durchgehen, aber weil sowohl die Gesamtgröße der Liste, als auch ihre Wachstumsrate erst zur Laufzeit (vom Nutzer) bestimmt werden, kann die Liste sehr groß werden, was dann in einem sehr zeitraubenden Suchvorgang resultiert.Um etwas konkreter zu werden: Es handelt sich dabei um ein Backup-Programm, das die Namen aller geänderten Dateien speichern soll. Wird eine Datei zweimal geändert, soll sie aber nicht erneut in die Liste eingetragen.
Ich habe mich schon ein wenig schlau gemacht, was das Suchen angeht und brauche nun so etwas in Richtung "Informed Search". Ich will also die Dateinamen irgendwie klassifizieren, sodass der Suchvorgang beschleunigt wird. Leider habe ich keine sinnvolle Idee, welche Informationen ich den Dateinamen zuordnen könnte.
Es wäre toll, wenn mir jemand einen Tipp geben könnte!
-
Stichwort Hashtabelle.
-
+ binärer baum
-
Wie suchst du bisher?
-
Wenn die einfüge Reihenfolge egal ist, dann nimm std::set statt std::list.
-
Danke für eure Antworten!
Die Hashtabelle klingt schon sehr interessant. Damit werde ich mich mal genauer befassen. Bisher habe ich einfach linear die Liste durchsucht, was ich aber auf jeden Fall ändern will.
Die STL möchte ich nicht verwenden, sondern die Suchmethode lieber selbst implementieren. Wie funktioniert std::set?
-
Seeker schrieb:
Die STL möchte ich nicht verwenden, sondern die Suchmethode lieber selbst implementieren.
Öh … und warum?
Wie funktioniert std::set?
Sie benutzt einen binären Suchbaum, der meist als Rot-Schwarz-Baum (=> Wikipedia!) implementiert ist.
-
Die STL möchte ich nicht verwenden, sondern die Suchmethode lieber selbst implementieren. Wie funktioniert std::set
Schau dir doch ergänzend mal die Implementierung deines Compilers an.