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. :stupid:

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. :zwinker:

[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

Delphi-Quellcode:

Liste.Create;

die Liste erzeugt werden. Und sie muss am Ende wieder weg :

Delphi-Quellcode:

Liste.Free;

Steht OwnObjects der Liste auf true, dann sind mitsamt der Liste selbst auch die erzeugten Objekte weg. :shock:

[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 !! :shock:

[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" ? :shock: Da ist man 3 Tage in Darmstadt und kriegt das nicht mal mit. :mrgreen:

[Mithrandir]

Zitat:

Zitat von 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.

Danke, hab ich also richtig vermutet. ;)

@Hansa: Die Taste "F1" ist mir durchaus geläufig, darauf muss man mich imho nicht mehr verweisen.

@Daniel: Ein Wörterbuch? Öhö... :gruebel: Ich denke mal, dass ich mich da noch ein bisschen schlauer mache.

Zitat:

Ist denn auch der schnelle und elegante Zugriff auf deine Datenobjekte von Bedeutung?

Naja... Ich hoffe mal, dass nie einer auf die Idee kommt, die Weltdatei von OpenStreetMap zu importieren. Aber, um mal die WorstCase Eckdaten zu nennen*:

(Stand 11. Mai)
Knoten ~348 Mio.
Wege ~28 Mio.
Beziehungen 112357

:mrgreen:

Also ja, Geschwindigkeit ist ein Punkt. ;)

*Für Deutschland rechne so überschlagsmäßig mit höchstens 1 - 2 Mio. Knoten...

[Daniel]

Ein Dictionary ist eine sehr geile Datenstruktur, die eine Zuordnung zwischen einem eindeutigen Wert ("Schlüssel", beispielsweise eine User-ID) zu einem anderen Wert ("Wert" ^^ ... beispielsweise das User-Objekt) herstellt und dabei intern über Mechanismen verfügt, die einen sehr schnellen Zugriff ermöglichen.


Ein User-Dictionary der DP könnte wie folgt aussehen, wenn man den User mit der ID 7 (das bin ich) und weitere darin speichern möchte:

users_dict[ 7 ]:= TUser.Create( "Daniel" );
users_dict[ 35 ]:= TUser.Create( "Hansa" );
users_dict[ 52585 ]:= TUser.Create( "DanielG" );


Im Gegensatz zu einer Liste hast Du keine Positionen, an denen die Objekte stehen. Du gibst dem Dictionary den Schlüssel "7" oder "35" oder - wenn es unbedingt sein muss :mrgreen: - auch "52585" und es liefert Dir das zugehörige Datenobjekt zurück.

// edit: Auch möglich ist es, die Datenobjekte in einer herkömmlichen Liste zu verwalten und - da es bei Dir im Wesentlichen wohl auch nur read-only-Daten sind - ein Dictionary parallel laufen zu lassen als "lookup-table". Das Dictionary wäre dann die Zuordnung zwischen ID des Users/Knotens und absoluter Position in Deiner Liste. Das wäre dann ein kleines Dictionary, welches nur zwei Integer (ID -> Position) miteinander verdingsen würde.

[Mithrandir]

Interessant. :gruebel:

Ohne mich jetzt groß damit beschäftigt zu haben: Was liegt denn dann da für eine Datenstruktur hinter? Oder muss man da noch Abstrakter denken, und nicht an Array und Co. denken? :gruebel:

Jeder Knoten hat eine einmalige ID. In dem Falle würden also die Knoten des betrachteten Ausschnitts meinetwegen mit der ID 2208151986 beginnen und irgendwann mit 3244234233 aufhören. Und dann könnte ich z.B. über node_dict[2234556543] genau den Knoten mit der Id holen, richtig?

Jetzt bräuchte man ja nur noch ne schöne Implementation.. :P

Zitat:

Zitat von Daniel

oder - wenn es unbedingt sein muss :mrgreen: - auch "52585".

:cry: :P

//Edit erst jetzt gelesen:

Warum schießt mir jetzt spontan der Begriff "Hashtable" in den Kopf? Hat das damit auch was zu tun/kann man sowas dafür nutzen/bringt das Vorteile? :stupid:

[mkinzler]

@Daniel: Bist du dir mit den Anführungszeichen (") sicher?

[Mithrandir]

Zitat:

Zitat von mkinzler

@Daniel: Bist du dir mit den Anführungszeichen (") sicher?

Er hat auch mein Leerzeichen unterschlagen, dass muss an der Uhrzeit liegen. :mrgreen:

[Daniel]

Zitat:

Zitat von Daniel G

Ohne mich jetzt groß damit beschäftigt zu haben: Was liegt denn dann da für eine Datenstruktur hinter? Oder muss man da noch Abstrakter denken, und nicht an Array und Co. denken? :gruebel:

Doch, ich meine, dass das TDictionary von Delphi 2009 aus ganz grundlegenden Dingen zusammengesetzt ist - gerade, wenn man die Generics weglässt. Aus dem Schlüssel, den Du übergibst, errechnet das Dictionary einen Hash-Wert. Zu gut Deutsch: Es versucht, den von Dir gegebenen Schlüssel in einen eindeutigen, internen Zahlenwert zu überführen. Auf Basis dieser internen Zahlenwerte (Hashes) sorgt das Dictionary für einen schnellen Zugriff. Und da intern eh alles bei diesen Hashes landet, war auch schon vor Delphi 2009 - also ohne Generics - ein Dictionary denkbar, welches beispielsweise mit Strings arbeitet:

users_dict[ 'Daniel' ]:= TUser.Create( 'Daniel' );

Hier wäre dann nur eine andere Funktion nötig, die eben keinen Integer, sondern einen String in das interne Format wandelt. Alles keine Hexerei.

Zitat:

Zitat von Daniel G

Jeder Knoten hat eine einmalige ID. In dem Falle würden also die Knoten des betrachteten Ausschnitts meinetwegen mit der ID 2208151986 beginnen und irgendwann mit 3244234233 aufhören. Und dann könnte ich z.B. über node_dict[2234556543] genau den Knoten mit der Id holen, richtig?

Genau. Wenn sich Dein Programm wiederholt an einer Stelle befindet, an der es die numerische ID eines Knotens hat und dann das dazu passende Datenobjekt haben will, würde ich immer versuchen, dies mit Dictionaries zu lösen. Wenngleich bis zu 2 Mio. Elemente in einem Datencontainer (Liste, Dictionary etc.) schon happig sind, wenn es um wirklich schnelle Zugriffe geht.

Kannst Du Deine Knoten irgendwie kategorisieren und somit die Gesamtmenge in beispielsweise 4 oder gar zehn Segmente einteilen? Wenn Du dann eine schnelle Entscheidungsfunktioon hättest, in welchem Container der gegebene Knoten liegen muss, sollte die Gesamtzugriffszeit insgesamt sinken.


@Markus: Stimmt natürlich, die Anführungszeichen sind falsch. :oops:

[mkinzler]

Zitat:

@Markus: Stimmt natürlich, die Anführungszeichen sind falsch. Embarassed

Passiert mir auch immer, wenn ich zwischen PHP und Delphi wechsele

[Hansa]

@Daniel :Das hört sich sehr interessant an.Aber gib mal besser Link an. Ich finde jedenfalls nichts. Oder wie heisst es immer "...erstelle hirzu bitte ein neues thema. Klicke hierzu ..." Oder so àhnlich. :lol: :mrgreen:
Edit : 3. Versuch das hier abzuschicken. Roter kasten wird jetzt ignoriert. :wall:

[alzaimar]

Zitat:

Zitat von Daniel

...Wenngleich bis zu 2 Mio. Elemente in einem Datencontainer (Liste, Dictionary etc.) schon happig sind, wenn es um wirklich schnelle Zugriffe geht.

Das Wesen einer Hashmap(Dictionary) ist die konstante Zugriffsgeschwindigkeit, egal ob das Dictionary aus 10 oder 100.000.000 Mio Elementen besteht. Es bei jedem Suchvorgang immer genau 1x der Hashwert berechnet, dann ein Modulo und dann eventuell noch 1-3 Vergleiche (je nach Implementierung).

[Mithrandir]

So, da bin ich wieder. Der Internetanschluss im Wohnheim ist echt... :wall:

Was ich gestern eigentlich noch schreiben wollte:

Zitat:

Zitat von Daniel

Kannst Du Deine Knoten irgendwie kategorisieren und somit die Gesamtmenge in beispielsweise 4 oder gar zehn Segmente einteilen? Wenn Du dann eine schnelle Entscheidungsfunktioon hättest, in welchem Container der gegebene Knoten liegen muss, sollte die Gesamtzugriffszeit insgesamt sinken.

Ja, kann ich, allerdings nur Grob:

Zu einem Knoten kann man sogenannten 'Tags' hinzufügen. Knoten, die zu einem Weg gehören, haben in der Regel außer dem "created_by" Tag keine Tags. Die zweite Gruppe wären dann sog. 'Point of Interests', also Bankautomaten, Brunnen, Cafés etc.

Die Frage ist, wie weit ich jetzt die zugrunde liegende Datenbank erweitere. Zu viele Tabellen schränken die Flexibilität ein. OSM ist sowieso ein sehr liberales Projekt.

Zitat:

Wenn sich Dein Programm wiederholt an einer Stelle befindet, an der es die numerische ID eines Knotens hat und dann das dazu passende Datenobjekt haben will, würde ich immer versuchen, dies mit Dictionaries zu lösen.

Ja, das passiert öfters:

XML-Code:

  <way id="25004068" version="3" timestamp="2008-09-20T14:32:19Z" uid="39330" user="chehrlic">
    <nd ref="271817426"/> <= Referenzen auf einen Knoten
    <nd ref="271817429"/>
    <nd ref="271817430"/>
    <nd ref="271817431"/>
    <nd ref="271817432"/>
    <nd ref="271817433"/>
    <nd ref="271817434"/>
    <nd ref="271817435"/>
    <nd ref="271817436"/>
    <nd ref="271817437"/>
    <nd ref="271817438"/>
    <nd ref="271817439"/>
    <nd ref="271817440"/>
    <nd ref="271817441"/>
    <nd ref="271817442"/>
    <nd ref="271817443"/>
    <nd ref="271817444"/>
    <nd ref="29956036"/>
    <nd ref="271817445"/>
    <nd ref="271817446"/>
    <nd ref="271817447"/>
    <nd ref="271817448"/>
    <nd ref="271817426"/>
    <tag k="created_by" v="Potlatch 0.9c"/>
    <tag k="landuse" v="industrial"/>
    <tag k="name" v="EADS/Airbus/Astrium"/>
  </way>

Wie man sieht, können der Anfangs- und der Endknoten auch identisch sein. Dann handelt es sich um einen geschlossenen Weg, was mit entsprechenden Tags nix anderes als eine Fläche ist. ;)

Wie Hansa schon erwähnte, ein Link auf irgendeine Beispielimplementation (kann auch C# sein) wäre super. :)

[mschaefer]

Dictonaries sind wirklich eine feine Sache und halten sich auch bei großen Datenräumen gut. Habe damit schon 10000 * 10000 Arrays gehabt und das ganze lief ordentlich. Es findet sich dazu auch einiges in der DP:

1. Dictonary von r2c2
2. Dictornary von alzaimer auch für NET.
3. der Zeitvergleich von alzaimer, der es auf den Punkt bringt.

[Mithrandir]

Hmm, TIntegerDictionary von alzaimar klingt doch nach dem, was ich bräuchte. Ich mein mich auch dran erinnern zu können, dass ich schonmal darüber gestolpert bin, es kam mir zumindest bekannt vor. Aber damals habe ich das noch nicht so ganz gerallt.. :mrgreen:

Mal zur praktischen Umsetzung und der Verwendung von Pointern (Gott, is das alles lange her.. :gruebel: ) folgendes Listing:

Delphi-Quellcode:

var
  Dict: TIntegerDictionary;

implementation

{... Create, Dict initialisieren, etc ...}

procedure AddNode(Node: TORPNode);
begin
  Dict.Add(Node.ID, @Node);
end;

function ReadNode(ID: Cardinal): TORPNode;
begin
  Dict.Find(ID, Result^);
end;

Ist jetzt nur ohne Test grob zusammengehackt. Wenn ich jetzt einen Eintrag lösche, was passiert dann mit den Daten, die hinter dem Pointer liegen? Muss ich mich selbst darum kümmern? Sollte ich denn weiter auf der Schiene fahren, alles in Objekte zu fassen, oder sollte ich doch lieber Records verwenden? Fragen über Fragen... :gruebel:

[jfheins]

Zitat:

Zitat von Daniel G

Wie Hansa schon erwähnte, ein Link auf irgendeine Beispielimplementation (kann auch C# sein) wäre super. :)

Ein C# Beispiel für ein Dictionary?

Hab ich da:

Code:

var MyDict = new Dictionary<TKey, TValue>();

:mrgreen:

Für TKey und TValue die entsprechenden Typen einsetzen - in deinem Fall also wohl sowas:

Code:

var MyDict = new Dictionary<uint, Node>(1000000);

:stupid:

[Mithrandir]

Moah, so war das jetzt nicht gemeint.. :lol:

Konnt ja nicht ahnen, dass C# sowas schon kann... :stupid:

[Apollonius]

Deine Umsetzung aus #22 funktioniert so nicht, da der Zeiger auf den Stack verweist. Wenn du noch mit Records arbeitest, solltest du dir mit New einen neuen Record besorgen und dann kopieren, wenn TORPNode eine Klasse sein sollte, kannst du einfach nach Pointer casten.

[Mithrandir]

Zitat:

Zitat von Apollonius

...kannst du einfach nach Pointer casten.

Hi,

Das habe ich nicht ganz verstanden. Sollte ich mir dann so einen Typ definieren:

Delphi-Quellcode:

PORPNode = ^TORPNode;

Und den dann stattdessen in Dict.Add nutzen?

[Khabarakh]

Nein, du kannst jede Referenz auf ein Objekt als Pointer interpretieren, eben mit einem Cast:

Delphi-Quellcode:

Dict.Add(Pointer(TORPNode.Create));

[Mithrandir]

Ok, danke. ;)

Allerdings habe ich das irgendwie noch nicht ganz auf der Reihe. Folgender Ablauf:

Der Node wird erstellt:

Delphi-Quellcode:

fORPNode := TORPNode.Create;
fORPNode.Subnodes := TObjectList.Create;

Anschließend wird er über eine Schleife mit Daten gefüllt:

Delphi-Quellcode:

       
       if fRegAttrExpr.Match then
          repeat
            case AnsiIndexText(fRegAttrExpr.SubExpressions[1], AllOSMElements) of

              ATTR_ID:
                begin
                  fORPNode.ID := StrToInt(fRegAttrExpr.SubExpressions[3]); //Hier steht dann z.B. 123456
                end;

              ATTR_LAT:
                begin
                  fORPNode.MercLat := StrToFloat(fRegAttrExpr.SubExpressions[3]); //Hier bspw. 53,45356645
                end;

              ATTR_LON:
                begin
                  fORPNode.MercLon := StrToFloat(fRegAttrExpr.SubExpressions[3]);  //Hier bspw. 8,8234554
                end;

            end;
          until not fRegAttrExpr.MatchAgain;

Dann wird das Object zum TIntegerDictionary zugefügt:

Delphi-Quellcode:

  procedure TORPTree.AddNodeToList(Node: TORPNode);
  begin
    fNodes.Add(Node.ID, Pointer(Node));
  end;

Jetzt muss ich das Objekt wieder auslesen. Das geschieht so:

Delphi-Quellcode:

        var
ptr: Pointer;

{...}

ATTR_REF:
                  begin
                    if fORPTree.Nodes.Find(StrToInt(fRegAttrExpr.SubExpressions[3]), ptr) then
                    begin
                      fORPSubNd := TORPNode(ptr^);
                      fORPWay.SubNodes.Add(fORPSubNd);
                    end;

In fRegAttrExpr.SubExpressions[3] steht laut Debugger "20958823". Wenn ich mir jetzt im Debugger fORPSubNd anzeigen lasse, dann sieht das z.B: so aus:

Code:

fORPSubNd.ID = 1685016144
fORPSubNd.MercLat = 2,4587345897e-307
fORPSubNd.MercLon = 0

Der Eintrag wurde aber mit der o.g. genannten ID in der TIntegerDictionary gefunden, sonst wäre er ja nicht in den IF-Block gesprungen. Und theoretisch sollte in ID genau dieser Wert (20958823) stehen.

Was mache ich falsch? :gruebel:

P.S.: Ich vermute ja, ich schieße mit den Pointern falsch um mich. Aber eigentlich sieht das für mich ganz logisch aus. :gruebel:

[jfheins]

Caste mal nicht nach Pointer sondern nach Cardinal oder Integer - ich glaube die speicherst einen Pointer, der nach verlassen der Funktion ungültig wird ...

[Mithrandir]

Ähm... Wie jetzt genau? :gruebel: Soll ich sowas schreiben:

Delphi-Quellcode:

procedure TORPTree.AddNodeToList(Node: TORPNode);
  begin
    fNodes.Add(Node.ID, Cardinal(Node));
  end;

:gruebel:

[Mithrandir]

Sry, Doppelposting, aber:

Um das Problem zu isolieren, habe ich mal eine kleine Test-App geschrieben. Sie befindet sich im Anhang, das Listing im Posting. Ich bin jedenfalls noch nicht weitergekommen.. :gruebel:

Der Aufbau entspricht in etwa dem in der "echten" Anwendung.

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, Unit2, csDictionary;

type
  TForm1 = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    Button2: TButton;
    procedure FormCreate(Sender: TObject);
    procedure FormClose(Sender: TObject; var Action: TCloseAction);
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    procedure AddItem(Node: TORPNode);
    function ReadItem(ID: Cardinal): TORPNode;
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;
  Dict: TIntegerDictionary;

implementation

{$R *.dfm}

function TForm1.ReadItem(ID: Cardinal): TORPNode;
var
  pter: Pointer;
begin
  Dict.Find(ID, pter);
  Result := TORPNode(pter^);
end;

procedure TForm1.AddItem(Node: TORPNode);
begin
  Dict.Add(Node.ID, Pointer(Node));
end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
  fNode: TORPNode;
begin
  Button2.Enabled := false;
  for i := 0 to 1000 do
    begin
      fNode := TORPNode.Create;
      fNode.ID := i;
      fNode.Trst := Random(300000);
      AddItem(fNode);
    end;
  ShowMessage('Liste erstellt.');
  Button2.Enabled := true;
end;

procedure TForm1.Button2Click(Sender: TObject);
var
  i: Integer;
  fNode: TORPNode;
begin
  i := Random(1000);
  fNode := ReadItem(i);
  if fNode <> nil then
   begin
    Memo1.Lines.Add(IntToStr(fNode.ID));
    Memo1.Lines.Add('---------');
    Memo1.Lines.Add(IntToStr(fNode.Trst));
    Memo1.Lines.Add('');
   end
   else
    Memo1.Lines.Add('Misslungen...');
end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
  FreeAndNil(dict);
end;

procedure TForm1.FormCreate(Sender: TObject);
begin
  dict := TIntegerDictionary.Create;
  Button2.Enabled := false;
end;

end.


unit Unit2;

interface

Type
  TORPNode = class(TObject)
    ID : Cardinal;
    Trst: Integer;
  end;

implementation

end.

[Khabarakh]

Zitat:

Zitat von Daniel G

Allerdings habe ich das irgendwie noch nicht ganz auf der Reihe.

Scheint so ;) . Noch einmal: Eine Objektreferenz ist ein Pointer. Die Dereferenzierung beim Auslesen hat da nichts zu suchen. Abgesehen von dem Pointer-Cast und zurück musst du dich hier mit Pointern gar nicht auseinandersetzen.

[himitsu]

Im Notfall könnte man das Pferd auch von hinten aufzäumen

Hier ist einfach mal ganz schnell 'ne Version mit Objekten, anstatt Pointern:
(PS: wenn beim .Create der Parameter True ist, dann würden als "Bonus" die "eingelagerten" Objekte beim .Delete, bzw. beim .Destroy/.Free und .Clear vom Dictionary "automatisch" freigegeben)

[alzaimar]

Hi himitsu,
schöne kleine Verbesserung. :thumb:

[Mithrandir]

Zitat:

Zitat von Khabarakh

Zitat:

Zitat von Daniel G

Allerdings habe ich das irgendwie noch nicht ganz auf der Reihe.

Scheint so ;) . Noch einmal: Eine Objektreferenz ist ein Pointer. Die Dereferenzierung beim Auslesen hat da nichts zu suchen. Abgesehen von dem Pointer-Cast und zurück musst du dich hier mit Pointern gar nicht auseinandersetzen.

Hi Khabarakh,

das habe ich schon soweit verstanden. Allerdings scheiterte es an der simplen Umsetzung. Es war nicht das Wissen, was fehlte, sondern das Handwerkszeug. Ich hab mir das eben nochmal angesehen, und dann ist es mir wie Schuppen von den Augen gefallen. Einfach pter mit Result gleichsetzen. :wall: Schwuppdiewuppdi klappt das auch.


@Himi: :thumb: Wird ab sofort eingesetzt. ;)

[Mithrandir]

Zitat:

Zitat von Daniel G

(Stand 11. Mai)
Knoten ~348 Mio.
Wege ~28 Mio.
Beziehungen 112357
*Für Deutschland rechne so überschlagsmäßig mit höchstens 1 - 2 Mio. Knoten...

Iiick muss da mal ne böse Fehlkalkulation gestehen. Ich habe eben mal den Import von Niedersachsen durchlaufen lassen. Am Ende des Programms lasse ich mir die Zahl der Knoten ausgeben:

Code:

---------------------------
saxxmltest
---------------------------
2294861
---------------------------
OK   
---------------------------

2,3 Mio. Knoten. Alleine in Niedersachsen. Somit kann man für ganz Deutschland vermutlich mit 15 - 20 Millionen Knoten rechnen... Heidewitzka... Die Verarbeitung einer 450 MB - Datei verbrauchte übrigens 350 MB Arbeitsspeicher... Ich denke, ich lasse morgen mal die Deutschlanddatei mit 4 GB importieren, um einen vernünftigen Überblick über die Dimensionen zu bekommen.

//Edit: Der Import dauerte übrigens 22 Minuten.

[Bbommel]

Hallo zusammen,

mir ist gerade beim Querlesen dieses Themas etwas aufgefallen, was zwar schon ein paar Tage her ist, aber worauf man vielleicht doch noch mal eingehen sollte - auch wenn es etwas von der ursprünglichen Frage von Daniel G weggeht. Es geht um eine Antwort von Hansa:

Zitat:

Zitat von Hansa

Delphi-Quellcode:

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

TListe = class (TObjectList)
  Daten : TDaten;          // <--- Edit Bbommel: Das ist doch so nicht richtig, oder?
end;

var Liste : TListe;
    ListeElement : TDaten;

Die Liste weiß nun welche Daten sie erhalten soll.

Mir geht es um die von mir oben markierte Zeile und die damit wohl verbundene Aussage, dass die Liste nun weiß, welche Daten sie enthalten soll. Das halte ich so nicht für richtig. Man muss (und kann) doch einer Liste nicht anzeigen, welche Daten sie enthalten soll. Das muss sie ja auch gar nicht wissen, sondern nur, dass sie irgendwelche Nachfolger von TObject enthält, um deren Freigabe sie sich ggf. kümmern muss - alles weitere sollte die Liste selbst nicht interessieren.

In dem konkreten Beispiel von Hansa bräuchte man also eigentlich TObjectList gar nicht ableiten, sondern könnte es direkt benutzen, um die "TDaten" zu speichern. TObjectList braucht man nur dann abzuleiten, wenn man noch irgendwelche Eigenschaften für die Liste insgesamt speichern will, also sozusagen "Kopfdaten" für die gesamte Liste oder einen Status, solche Dinge. Gerne auch Methoden, mit denen die Objekte in der Liste irgendwie gespeichert und wieder geladen werden können.

@Hansa: Ich hoffe, das kommt jetzt nicht zu negativ rüber, aber es geht mir darum zu klären, ob ich selbst in den letzten Jahren etwas falsch verstanden habe, oder ob ich Glück habe und der Fehler lag wirklich bei dir. :) Oder ob ich deinen Beitrag irgendwie völlig falsch verstanden habe...

Bis denn
Bommel

[Hansa]

Tja, wer hat was falsch verstanden ? Du oder ich ? :shock: Befürchte Du. :mrgreen: Warum ? Weil es erstmal fehlerfrei und wie gewünscht läuft, sonst hätte ich das auch nicht gepostet. Aber wer weiß, es könnte ja vielleicht doch so nicht ganz richtig sein ?

Nur geht es doch darum : irgendeine Liste muss da sein und sie muss konkrete Daten enthalten können. Die Liste ist mir dabei ziemlich egal, aber die Daten sollen schon so aussehen, wie ich sie brauche. Vielleicht ist das hier noch interessanter :

Delphi-Quellcode:

while not gefunden do begin
...
  ListeElement := (Liste.Items[i] as TDaten);
  gefunden := (ID = ListeElement.ID);

Ich suche etwas. Mit etwas Phantasie kann man erahnen, dass es bei der Liste darum geht, nicht unnötigerweise immer einunddieselben Datensätze neu lesen zu müssen. Beim Programmstart wird die aus DB gefüllt und dann wird nur noch diese Liste durchsucht, statt dauernd in der DB zu suchen (die Tabelle, um die es geht, ändert sich eigentlich nie). Wie soll ich aber nun die Liste nach gewisser ID durchsuchen, wenn die die ID nicht mal kennt ? :gruebel: Besser gesagt : die Liste selbst kennt die ID ja auch nicht, aber die Elemente müssen sie kennen.

[Daniel]

Ich fürchte, Ihr redet aneinander vorbei.

Delphi-Quellcode:

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

Natürlich lässt sich dieser Codeblock kompilieren. Aber er ist so für sich genommen sinnlos. Man hat eine neue Klasse (TListe), die von TObjectlist abgeleitet ist und zusätzlich ein Feld "Daten" vom Typ "TDaten" enthält. Dieses Feld hat aber mit dem Listen-Inhalt nichts zutun. In diese Liste kann ich mittels Add() weiterhin Buttons, Balkonmöbel und Brausepulver reintun.

Wenn ich den Datentyp vorgeben will, kann ich das tun, brauche dann aber entweder Generics (Delphi 2009 oder später) oder eine angepasste Add-Methode.

[himitsu]

Zitat:

Zitat von Daniel

oder eine angepasste Add-Methode.

siehe "mich" > #33 :angel:
Und wenn wirklich nur dieser Objekttyp da rein soll, dann müßte man in die Add-Methode noch eine Typenprüfung reinmachen.

Aber mit Generics wär's schon was Schönes und leichter anpaßbar :stupid: