Komplexität von TMap?
Übersicht
BlitzMax, BlitzMax NG Allgemein
|
SkabusBetreff: Komplexität von TMap? |
 Di, Mai 31, 2011 14:00Antworten mit Zitat 
|
|---|---|---|
|
Weiß jemand die (Groß-O)-Komplexität von TMap?
Eigtl. kann man das ja mit nem Hash realisieren, allerdings wirkt der Aufruf der TMap-Funktionen etwas komisch... Daher die Frage: Hat jemand mitbekommen wie das implementiert wurde? Für mich ist das gerade relevant, da ich theoretisch mehr davon habe, wenn ich Elemente anhand von Suchschlüsseln aufrufen kann.Wenns aber nicht im Durchschnitt O(1) hat, bringt mir das net viel... Danke für eure Hilfe^^ MfG Ulukai |
||
|
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat
aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu |
||
|
BtbN |
Di, Mai 31, 2011 15:24 Antworten mit Zitat
|
|---|---|---|
| TMap ist ein simpler binärbaum, und hat auch die selben Laufzeit-Eigenschaften. Eine allgemeine Hashmap ist nicht möglich, da es keine Hash Methode in Object gibt, sehr wohl aber eine compare-methode. | ||
|
Noobody |
Di, Mai 31, 2011 15:52 Antworten mit Zitat
|
|---|---|---|
|
Wenn ich mich richtig erinnere, ist die TMap von BRL mittels eines Red-Black-Trees implementiert, hat also eine Laufzeitkomplexität von O(log n) für Suchen/Einfügen/Löschen.
Wenn du konstante Zugriffe willst, kannst du natürlich eine Hashmap implementieren, allerdings musst du dann mit schlechter Performance beim Einfügen rechnen. |
||
| Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun | ||
|
|
Skabus |
Mi, Jun 01, 2011 17:21 Antworten mit Zitat
|
|---|---|---|
|
Ah Danke!
O(log n) ist auch okay. Mir gings halt nur darum abzuschätzen wie schnell das Ganze ist. Aber gut zu wissen, vielen Dank 
MfG Ska |
||
|
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat
aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu |
||
Übersicht
BlitzMax, BlitzMax NG Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group