Riesige Strings parsen

[Macros]

Hiho,

Ich hab im Zuge eines Freizeitprojekts nun riesige Strings zu verarbeiten. Genaugenommen handelt es sich um Datein mit IMDB Daten. Beispielsweise die trivia.list von ftp://ftp.fu-berlin.de/pub/misc/movies/database/
oder für die aktuelle Anfrage besser geeignet: Die ratings.list

Es ist eine ewige Liste mit allen in der IMDB eingetragegen Filmen im Format:
0000000125 753 9.2 "The Simpsons" (1989) {Who Shot Mr. Burns?: Part 1 (#6.25)}
bzw. nur
0000002113 75 7.0 Avatar: Creating the World of Pandora (2010) (TV)

Durchsuche ich diese mit RegEx, dauert es schon merklich auf dem langsamen PC an dem ich gerade bin.
"RegEx von hand" also Findstring gehts schon schneller, aber ich frage mich was man noch alles tun kann.
Das Programm läuft dabei jeweils nur ein bis 2 mal mit der selben Liste, umfangreiche Umstrukturierung der Liste um nachher Vorteile zu haben lohnen sich also nicht.

Folgende Optimierungsfälle:

• Ich habe eine Serie und möchte die Bewertungen der Episoden.
  Hier geht Filtern nach Serienname und im Ergebnis nach der Episoden suchen hinreichend schnell.
• Ich suche die Bewertungen von verschiedenen Filmen, das dauert im Moment deutlich zu lang

Welche Tricks fallen euch ein?

[NicTheQuick]

Hast du die gesamte Datei dann in einem String?
Ich würde vermutlich die komplette Datei in den RAM laden und dann durchpointern. Ich weiß jetzt nur nicht, in wie weit du damit Erfahrung hast.
Also bei folgender Zeile

Code: Alles auswählen

      0000000125  778920   9.2  The Shawshank Redemption (1994)

hättest du dann gerne daraus eine LinkedList mit der entsprechenden Struktur?

Code: Alles auswählen

Structure IMDB
  Distribution.i
  Votes.i
  Rank.f
  Title.s

Ab dann kann man ja einfach darin suchen oder sortieren und dann suchen.

[Macros]

Es muss keine Linked List sein, wichtig sind eigentlich nur die Bewertungen zu konkreten Folgen oder Filmen.
Und hier um Geschwindigkeit, eine Lösung die funktioniert habe ich schon.
Mein Projekt ist ein Programm, das automatisch einen Episodenguide zu einer Serie erstellt von der man nur den Namen angibt.
Teil ist eine Tabelle mit Infos zu den Folgen (welche DVD usw.), mir kam die Idee, die IMDB Bewertungen hinzuzunehmen.

Die Folgen tragen alle den Titel der Serie gefolgt von der geschweiften Klammer, die Filme können ganz verschieden heißen.

Du darfst verwenden, was immer dir sinnvoll erscheint. Mit Pointern bin ich vertraut und sollte etwas vorkommen, das ich nicht kenne, lerne ichs mir an.

[RSBasic]

Ist es bei dir möglich, wenn du die ganzen Datensätze in einer Tabelle einer Datenbank speicherst? Damit könntest du schnell deine Einträge sortiert und gefiltert ausgeben.

[Macros]

Möglich ist es, sinnvoll nicht,

Denn dann habe ich den Aufwand:
-Alle parsen, obwohl mich nur einzelne Einträge interessieren
-Alle in Datenbank eintragen (Viel IO)
-Abfragen

Da sich die Liste mit den Ratings ändert, lohnt der Aufwand nicht.

[Nino]

[...] hättest du dann gerne daraus eine LinkedList mit der entsprechenden Struktur?

Code: Alles auswählen

Structure IMDB
  Distribution.i
  Votes.i
  Rank.f
  Title.s

Oder vielleicht eine Map benutzen, z.B.

Code: Alles auswählen

Structure IMDB
  Distribution.i
  Votes.i
  Rank.f
EndStructure

NewMap Film.IMDB()

Und dann die Titel als Schlüssel verwenden.

Oder vielleicht einen ternären Suchbaum benutzen.

Grüße, Nino

[Thorium]

Ich würde die Stingfunktionen von PB weglassen und eigenen Code schreiben, der den String durchläuft. Wenn du nach mehreren Namen sucht, muss PB mehrfach den kompletten String durchlaufen, was Zeit kostet.
Mit einer eigenen Prozedur spezialisiert auf das Textformat kannst die viele Zeichen überspringen, da du z.B. weisst das nach jedem Namen X Eigenschaften kommen, bevor wieder ein Name kommt. Also kannst du X Zeichen überspringen. Oder du kannst mehrere Sachen gleichzeitig prüfen um die zusätzliche Durchläufe zu sparen, etc.

Zu guter letzt könnte man auch eine Stringsuche mit ASM und SSE machen, ich glaube Helle hatte mal nen Code dazu gepostet.

[Macros]

@Nino

An eine Map hatte ch auch gedacht, doch dürfte der Zeitaufwand durch das Hashen der Ursprungswerte deutlich spürbar sein.
Ich werde morgen ein paar Tests durchführen.

Der Ternäre Suchbaum war kein guter Tipp. Ich hab mich erst mal 20 Minuten damit beschäftigt, bis ich die übliche Funktion ganz begriffen hatte, nur um dann festzustellen, dass er mir nichts nützt.
Er ist doch nur dazu da, um zu überprüfen ob ein Suchstring in einer Menge von Strings vorkommt, bzw. um die Nähe von zwei Strings zu prüfen. Ich könnte natürlich statt Buchstaben gleich ganze Strings als Knotenwerte verwenden, beispielsweise die Folgennamen, aber dann verliere ich wesentliche Geschwindigkeitsvorteile, weil ich wiederrum mit Strings arbeite. Hänge ich die Wertungen noch an, kommt der Aufwand die für jede Zeile zu extrahieren zusätzlich hinzu.
Wenn ich einfach gleich die Zeilen in einen Ternären Suchbaum einfüge, habe ich wiederrum einen riesen Aufwand.
Ein log n das sicher noch einen guten Faktor davor hat dürfte viel Zeit bedeuten. Außerdem dürfte der Speicherbedarf bei 27 oder mehr MB Strings extrem sein.
Habe ich was falsch verstanden?

@Thorium
Eine Eigene Funktion die den String durchläuft ist eine gute Idee. Daran werde ich mich auch mal versuchen und die Ergebnisse testen. Zusätzliche Durchläufe zu sparen wäre natürlich optimal, doch dann würde ich das aufrufende Programm dazu zwingen, dass es alle Filme die es Anfragen wird schon vorher kennt. Das will ich, wenn möglich vermeiden.

ASM+SSE ist mir zu aufwendig. Ich will ja noch zu den anderen Teilen meines Programms kommen

[Nino]

Der Ternäre Suchbaum war kein guter Tipp. Ich hab mich erst mal 20 Minuten damit beschäftigt, bis ich die übliche Funktion ganz begriffen hatte, nur um dann festzustellen, dass er mir nichts nützt.

Du musstest Dich tatsächlich selbst mit der Sache befassen? Geradezu skandalös!

Habe ich was falsch verstanden?

Kann schon sein, woher soll ich das wissen?

[Kiffi]

Da sich die Liste mit den Ratings ändert, lohnt der Aufwand nicht.

wie oft ändert sich diese Liste denn? Ich habe mir mal nen
kleinen unoptimierten Demo-Code zusammengestöpselt, der
innerhalb von knapp 7 Sekunden die 'ratings.list' in eine
SQLite-Datenbank überführt. Die Queries laufen dann gewohnt
schnell.

Grüße ... Kiffi