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

[Mithrandir]

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ö... 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



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

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?

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

Zitat von Daniel:

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

//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?

[mkinzler]

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

[Mithrandir]

Zitat von mkinzler:

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

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

[Daniel]

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?

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

[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 as 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.
Edit : 3. Versuch das hier abzuschicken. Roter kasten wird jetzt ignoriert.

[alzaimar]

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

Was ich gestern eigentlich noch schreiben wollte:

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.