Eine Frage der Performance - T(Object)List oder Dyn. Array?

[Mithrandir]

Hi ihr,

Ich stehe gerade vor einer elementaren Frage: (*trommelwirbel* *tätäää*)


In einer Anwendung lese ich aus einer Datei eine unbekannte, aber große Zahl an Daten aus (irgendwo im 5 bis 6-stelligen Bereich). Nun werden die Daten zuerst in den RAM geladen, anschließend wird noch eine zweite Zahl Daten geladen, die dann wieder auf die ersten Daten zugreifen müssen. Dabei werden die ersten Daten dann entweder genutzt (=kopiert), separat gespeichert oder verworfen(=gelöscht).

Wem die Erklärung genügt, der kann den nächsten Teil getrost überspringen.

Konkreter Anwendungsfall

Es geht natürlich um meinen Routenplaner. Die XML-Datei ist so organisiert:

• Knoten
• Wege
• Beziehungen

Die Wege bestehen aus einer Liste von Knoten. Allerdings beinhalten diese Knoten nur Referenzen auf die jeweiligen Knoten vorher. Realbeispiel:

XML-Code:

<node id="123".../>
<node id="678".../>
<way id="453"...>
  <nd ref="123"/>
  <nd ref="678"/>
</way>

Jetzt möchte ich natürlich nicht die Referenzen der Knoten im Weg speichern, sondern die Knoten selbst. Ich muss also alle Knoten im Speicher vorhalten.



Die Frage ist jetzt, was eignet sich für mein Vorhaben am Besten? Im Moment habe ich das noch mit einem dynamischen Array gelöst. Allerdings habe ich das Gefühl, dass das zu einem Leck führt, und zwar aus dem von shmia angeführten Gründen, denn mit SetLength arbeite ich auch.

Jetzt kommt der Punkt, wo ich Elemente auch löschen müsste. Dazu sehe ich zwei effiziente Möglichkeiten:

• Boolscher Wert im Record
• Komplett auf Liste umsteigen

Momentan arbeite ich mit Records:

Delphi-Quellcode:

type
  TORPTag = packed record
     Key:   String[255];
     Value: String[255];
  end;

  TORPTags = Array of TORPTag;

  TORPNode = packed record
     ID: String;
     Lat: String;
     Lon: String;
     Tags: TORPTags;
  end;

  TORPNodes = Array of TORPNode;

  TORPSubNode = packed record
      Ref: String;
  end;

  TORPSubNodes = Array of TORPSubNode;

  TORPWay = packed record
     ID: String;
     SubNodes: TORPNodes;
     Tags: TORPTags;
  end;

  TORPWays = Array of TORPWay;

  TORPMember = packed record
     MemberType: String[255];
     Ref: String[255];
     Role: String[255];
  end;

  TORPMembers = Array of TORPMember;

  TORPRelation = packed record
     ID: String;
     Tags: TORPTags;
     Members: TORPMembers;
  end;

  TORPPOI = packed record
     POIType: String[255];
     Custom: Integer;
     POIName: String[255];
     NodeID: String[255];
  end;

  TORPPOIS = Array of TORPPOI;

Wie man sieht, verstecken sich dort doch recht viele Dynamische Arrays. Ich bin im Moment noch in der glücklichen Situation, ganz am Anfang des Projekts zu stehen. Ich habe also noch Spielraum und kann noch umdisponieren.

Was meint ihr dazu?

[Dax]

Wenn du statt dynamischer Arrays Listen verwenden kannst: mach es. Die meisten Anwendungsfälle brauchen die Eigenheiten der Arrays wie Adressierbarkeit mit Pointer nicht, und Listen sind viel einfacher zu handhaben. Noch dazu nimmt sie dir die Speicherverwaltung ab, weil sie sich eben selbst vergrößert und diese Arbeit nicht dir überlässt (was ja nicht selten zu OOB-Exceptions führt).

[Hansa]

Vielleicht liege ich auch ganz daneben, aber da bieten sich doch die Objects an. Die gibts ab TStrings aufwärts und auch bei vielen Trees usw. Da kann man ja reinpacken, was man will. Und bei der TObjectList ist ja der Witz, dass man sowieso alles reinpacken kann und zusätzlich auch noch diese Objects für jeden Eintrag hat.

[Mithrandir]

Danke ihr beiden.

Jetzt bin ich aber noch etwas am Grübeln. Im Moment fliegt das ja noch alles etwas unkontrolliert umher. Meine Idee ist jetzt eine Klasse, die einen großen Baum abbildet, der in sich die Zweige Way, Relation, Node und POI trägt und dann mit diesem während des ganzen Import-Vorgangs zu arbeiten.

In etwa so:

Delphi-Quellcode:

  TORPTree = class(TObject)
    private

      //Meta
      fVersion: String;
      fGenerator: String;

      //Elements
      fWays: TObjectList;
      fNodes: TObjectList;
      fRelations: TObjectList;
      fPOI: TObjectList;

      //Misc. Functions
      function GetWayNode(ID: String): TORPNode;

    published
      //Meta
      property Version: String read fVersion;
      property Generator: String read fGenerator;

      //Elements
      property Ways: TObjectList read fWays;
      property Nodes: TObjectList read fNodes;
      property Relations: TObjectList read fRelations;
      property POI: TObjectList read fPOI;

      //Add Special Items
      procedure AddWayToList(Way: TORPWay);
      procedure AddNodeToList(Node: TORPNode);
      procedure AddRelationToList(Relation: TORPRelation);
      procedure AddPOIToList(POI: TORPPOI);

      //Delete Special Items
      function DeleteWayFromList(ID: String): Boolean;
      function DeleteNodeFromList(ID: String): Boolean;
      function DeleteRelationFromList(ID: String): Boolean;
      function DeletePOIFromList(ID: String): Boolean;

      Constructor Create;
      Destructor Destroy;
  end;

In der Extractor-Klasse erzeuge ich diese Klasse einmal und kann dann mit ihr arbeiten. Die TObjectList möchte vermutlich gerne eine Klasse haben, weswegen ich bspw. aus dem TORPNode-Record eine Klasse mit Constructor und Destructor, abgeleitet von TObject, machen müsste, oder?

[Hansa]

So ungefähr. Das Ganze muss so aussehen :

Delphi-Quellcode:

TDaten = class (TObject)
  ID,
  nr  : integer;   
// weitere Nutzdaten
end;

TListe = class (TObjectList)
  Daten : TDaten;
end;

var Liste : TListe;
    ListeElement : TDaten;

Die Liste weiß nun welche Daten sie erhalten soll. Zuerst werden immer die Elemente erzeugt und bestückt. Die Elemente kommen nun in die TObjectList :

Delphi-Quellcode:

ListeElement := TDaten.Create;
      ListeElement.ID := DS.FieldByName ('ID').AsInteger;
      ListeElement.Nr  := DS.FieldByName ('NR').AsInteger;
//...
      Liste.Add (ListeElement);

Ganz am Anfang muss mit Liste.Create; die Liste erzeugt werden. Und sie muss am Ende wieder weg :Liste.Free; Steht OwnObjects der Liste auf true, dann sind mitsamt der Liste selbst auch die erzeugten Objekte weg.

[Mithrandir]

Ok, danke
Wenn ich mich recht entsinne, speichert die Liste doch nur Zeiger, oder? Das heißt, eine Prozedur zum Hinzufügen des Objekts zur Liste darf das Objekt nicht wieder freigeben, oder?

Delphi-Quellcode:

procedure XYZ(huhu, du: Integer);
var
  Daten: TDaten;
begin
  Daten := TDaten.Create;
  Daten.ID := huhu;
  Daten.NR := du;
  Liste.Add(Daten);
  //FreeAndNil(Daten) <= Fällt einem dann hier der Himmel auf den Kopf?
end;

[Hansa]

Die letzte frage hier zu beantworten, das ist solange der falsche platz bis du endlich mal die hilfe durchliest. 8) da steht alles genau drin.vor allem ownsobjects nicht vergessen !!

[mkinzler]

An dieser Stelle darfst du natürlich nicht freigeben und wie Hansa geschrieben hat, kannst du die Liste zum Eigentümer machen und die Aufgabe der Entsorung so an diese Deligieren.

@hans: Ich glaube du hast die Frage nicht ganz verstanden

[Daniel]

Ist denn auch der schnelle und elegante Zugriff auf deine Datenobjekte von Bedeutung? Wenn ja, dann könntest Du überlegen, ein Dictionary einzusetzen. Delphi selbst bringt die zwar erst ab Version 2009 mit, aber ein Dictionary ist ja keine Hexerei und da sollte es auch für frühere Delphi-Versionen gute Implementationen geben.

Damit könntest Du eine Relation von (int)ID auf (data-object-dingens)DATA schaffen.


Ich habe mal in einem anderen Projekt drei Dictionaries ineinander geschachtelt und habe so einen bombig schnellen Zugriff, weil jede verbleibende Teilmenge vergleichsweise klein geblieben ist.

[Hansa]

Was zum Teufel ist ein "Dictionary" ? Da ist man 3 Tage in Darmstadt und kriegt das nicht mal mit.