[Optmierung]Auslesen von Strings aus großer Datei

Fabian E. · Verfasst: Mi 30.07.08 14:15

Hallo zusammen,

ich bin wieder da mit meiner 13 Millionen Zeilen Textdatei. Ich habe grade erfahren, dass ich noch ein weiteres Feature hinzufügen soll.

Naja, ich habe eine Datei mit 96 Einträgen. Zu jedem dieser Einträge muss ich nun alle passenden in den 13 Millionen der anderen Datei finden...
Hier ein Beispiel. Beide Dateien sind Kommata getrennt.

Die große Datei ist so aufgebaut:

markieren

Quelltext

1:
2:
3:
4:

ID     ;Wert   
1564654;1375654
7754635;7751345
...

Die IDs in dieser Datei können sich wiederholen, dann ist allerdings der Wert anders.

Die kleinere Datei so:

markieren

Quelltext

1:
2:
3:
4:
5:

ID     ;GruppenNR
1564654;1
7754635;2
4545634;3
...

Es geht mir nun darum, für jede ID in der kleinen Datei die jeweiligen Werte in der Großen auszulesen.
Dies könnte man mit zwei ineinander verschachtelten Schleifen machen, was recht unperformant wäre. (13.000.000 * 96 Durchläufe.)

Geht das vielleicht auch besser? Mir fällt grade überhaupt nichts dazu ein.

ZeitGeist87 · Verfasst: Mi 30.07.08 14:16

Da kannst du dich mit user profile icon

Gausi in Verbindung setzen.
War glaub ich Thema seiner Diplomarbeit.
Ich denke, er wird sich bald melden ;-)

_________________
Wer Provokationen, Ironie, Sarkasmus oder Zynismus herauslesen kann soll sie ignorieren um den Inhalt meiner Beiträge ungetrübt erfassen zu können.

Fabian E. · Verfasst: Mi 30.07.08 14:31

Ich habe mir grade überlegt es folgerndermaßen zu machen:

Ich habe eine Hashmap der kleinen Datei mit der ID als Schlüssel und der GruppenNR als Data.
Dann laufe ich alle 13 Millionen Einträge durch und extrahiere aus jedem Eintrag die ID. Mit der als Schlüssel bekomme ich über die Hashmap die GruppenNR raus. Dann kann ich das speichern

Laufzeit liegt in O(n).

Das sollte so doch eigentlich klappen oder?

Gausi · Verfasst: Mi 30.07.08 14:33

Joah, das lese ich grade, aber meine Diplomarbeit würde ich hier nicht unbedingt ansetzen wollen. Sind die IDs wirklich Zahlen? Zahlen, die im Bereich Integer liegen?

Dann würde ich "einfach" die große Datei in ein Integer-Array einlesen, bzw. in ein Array of MyRecord mit myRecord = ID, Wert, ggf. noch Zeilennummer. Dieses Array mit den Records drin dann nach ID sortieren, und die 96 IDs aus der kleinen Datei mit Binärsuche darin suchen. An den Fundstellen (sofern es sie gibt) nach oben und unten in dem sortierten Record-Array laufen, bis man auf eine andere ID trifft.

Oranger Kasten: Ja, das mit der Hashmap könnte auch gehen.

_________________
We are, we were and will not be.

ZeitGeist87 · Verfasst: Mi 30.07.08 14:35

Oder gleich in ne Datenbank :mrgreen:

_________________
Wer Provokationen, Ironie, Sarkasmus oder Zynismus herauslesen kann soll sie ignorieren um den Inhalt meiner Beiträge ungetrübt erfassen zu können.

Fabian E. · Verfasst: Mi 30.07.08 15:06

Also jetzt sieht es so aus:

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

procedure TMainForm.ReadPZNsForGroups;
var
  i                           : Integer;
  tmpID                       : string;
  Data                        : Pointer;
begin
  GroupHashMap.Clear;
  for i := 0 to GroupedIDList.Count - 1 do
    GroupHashMap.Add(ExtractID(GroupedIDList.Strings[i]), Pointer(ExtractPZN(GroupedIDList.Strings[i])));

  for i := 0 to FileList.Count - 1 do
    begin
      Data := nil;
      tmpID := ExtractID(FileList.Strings[i]);
      if GroupHashMap.Find(tmpID, Data) then
        PZNGroupNumberList.Add(tmpID + ';' + String(Data^));
    end;

  PZNGroupNumberList.SaveToFile(ExtractFilePath(paramstr(0)) + 'PZNGroupNumber.csv');
end;

Leider bekomme ich manchmal beim umwandeln des Pointers in einen String eine AV.
Was genau bedeutet das? Bzw. was ist dann im Pointer?

Fabian E. · Verfasst: Mi 30.07.08 15:54

Hmmm... Ich habe jetzt den Typen von String auf Integer geändert und jetzt gehts... Naja

Reinhard Kern · Beiträge: 591 Erhaltene Danke: 14

Fabian E. hat folgendes geschrieben:

Hallo zusammen,

ich bin wieder da mit meiner 13 Millionen Zeilen Textdatei. Ich habe grade erfahren, dass ich noch ein weiteres Feature hinzufügen soll.

Naja, ich habe eine Datei mit 96 Einträgen. Zu jedem dieser Einträge muss ich nun alle passenden in den 13 Millionen der anderen Datei finden...
Hier ein Beispiel. Beide Dateien sind Kommata getrennt.
....
Geht das vielleicht auch besser? Mir fällt grade überhaupt nichts dazu ein.

Hallo,

mir fehlen da ein paar Randbedingungen, aber wenn sich die grosse Datei nur selten ändert, bin ich auch der Meinung (wie Gausi), dass Sortieren am meisten bringt - ich würde sie sogar sortiert abspeichern, beim nächsten Lauf geht dann alles viel schneller, es sei denn, man müsste neu sortieren. Wie gesagt, Randbedingungen...

Gruss Reinhard

Fabian E. · Verfasst: Mi 30.07.08 16:08

Die Datei ändert sich alle zwei Wochen und es sollte möglichst schnell gehen. Daher ist vorher sortieren nicht so gut geeignet...

delphi10 · Verfasst: Mi 30.07.08 17:48

Schon mal Boyer-Moore probiert?
www-wi.uni-muenster....ristoferFichtner.pdf
Ist ziemlich effizient, allerdings hatte ich bei meiner Umsetzung keine 13Mio. Einige zehntausend aber schon.

_________________
Salus populi suprema lex esto

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme