Entwickler-Ecke :: Thema anzeigen - [Optmierung]Auslesen von Strings aus großer Datei

Fabian E. - Mi 30.07.08 14:15
Titel: [Optmierung]Auslesen von Strings aus großer Datei

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:

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:

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.

Fabian E. - 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 - 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.

Fabian E. - Mi 30.07.08 15:06

Also jetzt sieht es so aus:

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?

Reinhard Kern - Mi 30.07.08 15:54
Titel: Re: [Optmierung]Auslesen von Strings aus großer Datei

Fabian E. hat folgendes geschrieben:

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

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!