Warum man manchmal besser TMaps benutzt...

Übersicht BlitzMax, BlitzMax NG FAQs und Tutorials

Neue Antwort erstellen

Firstdeathmaker

Betreff: Warum man manchmal besser TMaps benutzt...

 BeitragMo, Feb 23, 2009 21:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Code pasten und laufen lassen. Spielt einfach mal mit den Consts rum, aber selbst bei 100 Personen ist TMap bei mir schneller. Also wenn man eine Funktion hat welche eine Id übergeben bekommt und ein Objekt danach raussuchen soll, gibt es nix besseres, und man sollte sich überlegen vielleicht doch besser mit TMap zu arbeiten.


Code: [AUSKLAPPEN]
SuperStrict

Const MAX_PERSONEN:Int = 100
Const SIMULATION_CALLS:Int = 10000
Const SIMULATION_TURNS:Int = 5
Const SHOWSINGLETURNRESULTS:Byte = False

Local time:Int
Local timeArray:Int[SIMULATION_TURNS , 2]
Local timeTotal:Int[2]

For Local i:Int = 0 Until MAX_PERSONEN
   Local p:TPerson = New TPerson
   p.id = "Person Nr " + (i+1)
   p.add()
Next

'Benchmark start
Print "#####################"
Print "# Benchmark Options"
Print "# Objects: " + MAX_PERSONEN
Print "# Calls per turn: " + SIMULATION_CALLS
Print "# Turns: " + SIMULATION_TURNS
Print "#####################"

For Local turn:Int = 0 Until SIMULATION_TURNS
   Print "Turn "+(turn+1)+" ..."
   time = MilliSecs()
   For Local i:Int = 0 Until SIMULATION_CALLS
      Local id:String = "Person Nr " + Rand(1 , TPerson.count)
      Local p:TPerson = TPerson.getIdFromList(id)
   Next
   time = MilliSecs() - time
   timeArray[turn , 0] = time
   timeTotal[0]:+time
   
   
   time = MilliSecs()
   For Local i:Int = 0 Until SIMULATION_CALLS
      Local id:String = "Person Nr " + Rand(1 , TPerson.count)
      Local p:TPerson = TPerson.getIdFromMap(id)
   Next
   time = MilliSecs() - time
   timeArray[turn , 1] = time
   timeTotal[1]:+time
Next

If SHOWSINGLETURNRESULTS
   For Local i:Int = 0 Until SIMULATION_TURNS
      Print "ListCall: " + timeArray[i , 0]
      Print "MapCall:  " + timeArray[i , 1]
      Print "---------------"
   Next
EndIf

Print "Total:"
Print "ListCall: " + timeTotal[0]
Print "MapCall:  " + timeTotal[1]
Print "-----------------"
Print "Average Total per Turn: "
Print "ListCall: " + timeTotal[0]/SIMULATION_TURNS
Print "MapCall:  " + timeTotal[1] / SIMULATION_TURNS
Print "-----------------"
Print "Average Total per Call: "
Print "ListCall: " + Double(timeTotal[0])/(SIMULATION_TURNS*SIMULATION_CALLS)
Print "MapCall:  " + Double(timeTotal[1]) / (SIMULATION_TURNS * SIMULATION_CALLS)
Print ""
Print "RESULT: TMap is " + (Double(timeTotal[0]) / timeTotal[1]) + " times faster than TList."

WaitKey()
End




Type TPerson
   Global map:TMap = CreateMap()
   Global list:TList = New TList
   Global count:Int = 0
   Field _link:TLink
   
   Field id:String
   
   Method add()
      If _link Return
      MapInsert(TPerson.map , Self.id, Self)
      _link = TPerson.list.addlast(self)
      count:+1
   End Method
   
   Method remove()
      If _link RemoveLink(_link)
      MapRemove(TPerson.map , Self.id)
      count:-1
   End Method
   
   Function getIdFromMap:TPerson(id:String)
      Return TPerson(MapValueForKey(TPerson.map,id))
   End Function
   
   Function getIdFromList:TPerson(id:String)
      For Local p:TPerson = EachIn TPerson.list
         If p.id = id Return p
      Next
   End Function
End Type
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

kog

 BeitragMo, Feb 23, 2009 21:41
Antworten mit Zitat
Benutzer-Profile anzeigen
Hehe du hast recht, hab aus spass mal 10'000 genommen:
Code: [AUSKLAPPEN]
#####################
# Benchmark Options
# Objects: 10000
# Calls per turn: 10000
# Turns: 5
#####################
Turn 1 ...
Turn 2 ...
Turn 3 ...
Turn 4 ...
Turn 5 ...
Total:
ListCall: 10844
MapCall:  44
-----------------
Average Total per Turn:
ListCall: 2168
MapCall:  8
-----------------
Average Total per Call:
ListCall: 0.21687999999999999
MapCall:  0.00088000000000000003

RESULT: TMap is 246.45454545454547 times faster than TList.

juse4pro

 BeitragDi, Feb 24, 2009 12:46
Antworten mit Zitat
Benutzer-Profile anzeigen
was genau ist TMap?
Portfolio |LinkedIn |XING

Mr.Hyde

Newsposter

BeitragDi, Feb 24, 2009 13:06
Antworten mit Zitat
Benutzer-Profile anzeigen
TMap ist eine Hashmap. Das heißt du hast nicht nur eine Liste der du Objekte hinzufügen (oder auch entfernen) kannst, sondern du legst die Objekte mit einem Schlüssel ab und kannst somit über den Schlüssel direkt auf das Objekt zugreifen. Nach dem Programm von FDM ist es wohl grundsätzlich wesentlich schneller ein Objekt mit Key abzuspeichern und aufzurufen als in einer TList zu vergleichen.
BBP News RSS | Chaos Interactive | Watanien 2 Screens, Infos und Download | Watanien 2 Worklog | PuzzleMasters
http://abgeordnetenwatch.de - http://www.regierungs-beratung.de - Der Regierung auf die Finger schauen

Firstdeathmaker

 BeitragDi, Feb 24, 2009 15:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Tut mir leid, aber jeder der sich den code brl.map anschaut, sieht, dass es leider keine wirkliche Hashmap ist, sondern ein Binärer Suchbaum. D.h. Werte werden als Baumstruktur gespeichert, und es gibt eine compare funktion welche die Werte <, = oder als > einordnet (also eine totale Ordnung über Strings aufbaut). Ist trotzdem viel schneller als eine LinkedList wenn man Werte nach Keys sortiert, und hat den Vorteil dass die Größe dynamisch ist. Auch kann besser und schneller über alle Werte iteriert werden. Aufwand: O(log(n))

Der Vorteil gegenüber einer richtigen Hashmap ist der, dass bei einer Hashmap der ungefähre Füllstand vorher bekannt sein muss, da sie als Array angelegt ist. Sprich man hat ein Array und eine Funktion, welche Keys arrayeinträge zuordnet, z.B.

Code: [AUSKLAPPEN]
val:int = 0
for local i:int = 0 until len(key)
val = asc(key)
key = key(left(key,len(key)-1))
next
val = val mod arraylength


Eine besonders gute Hash-Funktion zeichnet sich dabei dadurch aus, dass sie die Keys möglichst gleichmässig ohne viele überschneidungen auf das Array verteilt. Falls ein Arrayeintrag schon belegt ist, muss man eine Auflösungsfunktion aufrufen, oder aber den Eintrag hinten an den schon vorhandenen anhängen (also eine Liste erstellen). Das Problem ist aber, eine für alle gültige gute Hashfunktion zu finden, denn die Güte dieser ist stark von der Art der Eingangswerten abhängig. Dafür erreicht man aber fast konstanten Aufwand, je nachdem ob man die Arraygröße richtig gewählt hat (Worst Case: O(n), average case: O(1))

Eigentlich ist TMap also besser als TBinaryTree zu bezeichnen.
www.illusion-games.de
Space War 3 | Space Race | Galaxy on Fire | Razoon
Gewinner des BCC #57 User posted image

BladeRunner

Moderator

BeitragDi, Feb 24, 2009 16:51
Antworten mit Zitat
Benutzer-Profile anzeigen
Jop, TMap ist ein Rot-Schwarz-Baum.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

fire

 BeitragSa, März 07, 2009 12:01
Antworten mit Zitat
Benutzer-Profile anzeigen
wow, ich wusste gar nicht dass das so ein grosser unterschied ist!
hab wie einer meiner vorredner mal 10.000 objekte angeben und das result war wirklich eindeutig Smile
RESULT: TMap is 340.78181818181821 times faster than TList.
1 Lichtjahr = 9.454.254.955.488.000 m

BladeRunner

Moderator

BeitragSa, März 07, 2009 12:54
Antworten mit Zitat
Benutzer-Profile anzeigen
Nun sollte man dabei aber berücksichtigen dass dieser Test nicht unbedingt realitätsnah ist.
Immer wenn viele Objekte neu entstehen und rasch wieder gelöscht werden (zB bei Partikeln) ist die Liste deutlich im Vorteil, da das einfügen von Infos bei einer Liste wesentlich rascher geht als bei einer gewichteten Baumstruktur.
Von daher sind TMaps immer dann zu bevorzugen wenn man eine im wesentlichen statische Liste hat die häufig auf einzelne Elemente abgefragt wird, die Tlist immer dann wenn es viele Änderungen gibt, aber meist die komplette Liste iteriert wird.
Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92
 

Dreamora

 BeitragSa, März 07, 2009 18:33
Antworten mit Zitat
Benutzer-Profile anzeigen
TMaps sind eigentlich in genau einem Szenario sinnvoll, und das ist der Fall der dieser Art von Datenstruktur ihren normalen (nicht BM) Namen gibt: Dictionary

Sprich bei allem wo man einen Key (meist string, kann aber auch was komplexeres sein) benötigt um ein spezifisches Objekt zu identifizieren (ich schreib das fett weil das der springende Kernpunkt ist)

Es macht jedoch keinen Sinn wenn man zb eine TMap auffährt, um damit etwas zu handhaben was nur temporär was speichern muss und das ohne ein spezifisches Objekt zu direkt finden zu können. Das ist der Job von Listen, die einiges schneller sind für "stupid über eine Menge von Objekten eine Operation ablaufen zu lassen".

Dann gibt es noch den dritten Fall: Das ist wenn man zwar einen Key hat, der aber eine natürliche Zahl ist welche aufsteigend ist. zb bei Datenbanken, Spielerverwaltung / Verbindungsverwaltung bei einem Gameserver usw
In dem Falle sind klar Arrays am besten geeignet, denn arrays sind die einzige struktur die wenn man ihr nen Index hinwirft direkt das result haben. Alle anderen müssen in so fällen suchen.

Leider sind das alle Datenstrukturen die BM integriert hat, was eigentlich sehr mikrig ist.
Eigentlich gibt es noch zwei weitere (natürlich viel mehr aber die zwei sind kernstrukturen aus meiner Sicht), nämlich Hashmaps / Hashtables und PriorityQueue (auf Heap Basis, nicht irgend ein ineffizientes TList-Compare Massaker )
Speziell die PriorityQueue's sind eigentlich für die Spieleentwicklung von elementarer Bedeutung und es ist schwer nachzuvollziehen warum BM, welches gerne als ausrede für fehlende Features anführt das es nur/primär & sekundär auf Spieleentwicklung ausgelegt ist, die immer noch nicht beherrscht.
Denn in einem Spiel sind ein Grossteil der Dinge Fälle für genau diese Struktur, da man primär mit Fällen der Art "tue x für y sekunden", "tue x in y sekunden" zu tun hat, wobei das y dann genau das ist was man benötigt um es als Event in die PQ einzutragen.
Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen.

FireballFlame

 BeitragDi, Sep 29, 2009 2:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Dreamora hat Folgendes geschrieben:
Leider sind das alle Datenstrukturen die BM integriert hat, was eigentlich sehr mikrig ist.
Eigentlich gibt es noch zwei weitere [...]
Speziell die PriorityQueue's sind eigentlich für die Spieleentwicklung von elementarer Bedeutung und es ist schwer nachzuvollziehen warum BM, welches gerne als ausrede für fehlende Features anführt das es nur/primär & sekundär auf Spieleentwicklung ausgelegt ist, die immer noch nicht beherrscht.

Was heißt denn hier "nicht beherrscht"?
Man kann sich sowas doch jederzeit selber schreiben, wenn man es braucht?
PC: Intel Core i7 @ 4x2.93GHz | 6 GB RAM | Nvidia GeForce GT 440 | Desktop 2x1280x1024px | Windows 7 Professional 64bit
Laptop: Intel Core i7 @ 4x2.00GHz | 8 GB RAM | Nvidia GeForce GT 540M | Desktop 1366x768px | Windows 7 Home Premium 64bit

hamZta

Administrator

BeitragDi, Sep 29, 2009 9:58
Antworten mit Zitat
Benutzer-Profile anzeigen
Wenn ich mal ganz dreist Werbung machen dürfte: https://www.blitzforum.de/foru...906#313906

Ist ganz leicht und schnell implementiert.
BRLs Roadmap würde ich ja zu gerne mal sehen ... aber vermutlich basiert die nur auf Marks aktuellem Lieblingsthema.
Blog.

Jan_

Ehemaliger Admin

BeitragDi, Jun 29, 2010 14:22
Antworten mit Zitat
Benutzer-Profile anzeigen
*Ausgrab*

Es Lohnt sich nciht, mit einer Tmap zu arbeiten, wenn man alle objekte bearbeiten will. Z.B. eine Gegner Liste oder Partikel. es lohnt sich nur, wenn es eine 1 zu 1 zuordnung zum Suchen gibt. (wie oben zu sehen).
--> Tmap ist auch sehr gut geeignet wenn man sein Level in Bereiche einordnet und diese Bereiche dann sucht. Jedoch ist tmap bei Code: [AUSKLAPPEN]
echin
langsamer als Tlist.

Siehe hierzu:
Code: [AUSKLAPPEN]

SuperStrict

Const MAX_PERSONEN:Int = 100
Const SIMULATION_CALLS:Int = 10000
Const SIMULATION_TURNS:Int = 5
Const SHOWSINGLETURNRESULTS:Byte = False

Local time:Int
Local timeArray:Int[SIMULATION_TURNS , 2]
Local timeTotal:Int[2]

For Local i:Int = 0 Until MAX_PERSONEN
   Local p:TPerson = New TPerson
   p.id = "Person Nr " + (i+1)
   p.add()
Next

'Benchmark start
Print "#####################"
Print "# Benchmark Options"
Print "# Objects: " + MAX_PERSONEN
Print "# Calls per turn: " + SIMULATION_CALLS
Print "# Turns: " + SIMULATION_TURNS
Print "#####################"

For Local turn:Int = 0 Until SIMULATION_TURNS
   Print "Turn "+(turn+1)+" ..."
   time = MilliSecs()
   For Local i:Int = 0 Until SIMULATION_CALLS
      Local id:String = "Person Nr " + Rand(1 , TPerson.count)
      Local p:TPerson = TPerson.getIdFromList(id)
   Next
   time = MilliSecs() - time
   timeArray[turn , 0] = time
   timeTotal[0]:+time
   
   
   time = MilliSecs()
   For Local i:Int = 0 Until SIMULATION_CALLS
      Local id:String = "Person Nr " + Rand(1 , TPerson.count)
      Local p:TPerson = TPerson.getIdFromMap(id)
   Next
   time = MilliSecs() - time
   timeArray[turn , 1] = time
   timeTotal[1]:+time
Next

If SHOWSINGLETURNRESULTS
   For Local i:Int = 0 Until SIMULATION_TURNS
      Print "ListCall: " + timeArray[i , 0]
      Print "MapCall:  " + timeArray[i , 1]
      Print "---------------"
   Next
EndIf

Print "Total:"
Print "ListCall: " + timeTotal[0]
Print "MapCall:  " + timeTotal[1]
Print "-----------------"
Print "Average Total per Turn: "
Print "ListCall: " + timeTotal[0]/SIMULATION_TURNS
Print "MapCall:  " + timeTotal[1] / SIMULATION_TURNS
Print "-----------------"
Print "Average Total per Call: "
Print "ListCall: " + Double(timeTotal[0])/(SIMULATION_TURNS*SIMULATION_CALLS)
Print "MapCall:  " + Double(timeTotal[1]) / (SIMULATION_TURNS * SIMULATION_CALLS)
Print ""
Print "RESULT: TMap is " + (Double(timeTotal[0]) / timeTotal[1]) + " times faster than TList."

WaitKey()
End




Type TPerson
   Global map:TMap = CreateMap()
   Global list:TList = New TList
   Global count:Int = 0
   Field _link:TLink
   
   Field id:String
   
   Method add()
      If _link Return
      MapInsert(TPerson.map , Self.id, Self)
      _link = TPerson.list.addlast(Self)
      count:+1
   End Method
   
   Method remove()
      If _link RemoveLink(_link)
      MapRemove(TPerson.map , Self.id)
      count:-1
   End Method
   
   Function getIdFromMap:TPerson(id:String)
   For Local p:TPerson = EachIn TPerson.map
         If p.id = id Return p
      Next
      'Return TPerson(MapValueForKey(TPerson.map,id))
   End Function
   
   Function getIdFromList:TPerson(id:String)
      For Local p:TPerson = EachIn TPerson.list
         If p.id = id Return p
      Next
   End Function
End Type
between angels and insects

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG FAQs und Tutorials

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group