Linked List speedtest BMax vs Python
Übersicht

![]() |
TrustBetreff: Linked List speedtest BMax vs Python |
![]() Antworten mit Zitat ![]() |
---|---|---|
Hallo Leute,
da ich ein bissl dabei bin meinen AStar-algo in BMax zu optimieren, hatte ich nach Alternativen für Linked Lists in BMax gesucht, allerdings ohne großen Erfolg. Hatte sogar ne kleine DLL in C++ geschrieben welche mir direkt die Memoryfunktionen zur Verfügung stellt (memcpy) (ja, ist ein bissl schneller als die MemCopy-Funktion von BMax) um damit dynamisch vergrößerbare arrays zu realisieren - allerdings war das ganze memcopy auch nicht viel schneller. Dann habe ich den AStar-algo mal in Python programmiert, und siehe da, DEUTLICH schneller. Habe daraufhin mal jeweils für Python und BMax einen Test geschrieben um das mal gegenüber zu stellen: BMax: BlitzMax: [AUSKLAPPEN] SuperStrict Python: Code: [AUSKLAPPEN] import time as _time_
def millisecs(): return int(round(_time_.time() * 1000)) def main(): my_str = "String" my_list = [] print("Appending 10 million items to list...") time = millisecs() for i in range(0, 9999999): my_list.append(my_str) time = millisecs() - time print("ms: ", time) print("") print("popping 1000 items from position 100") time = millisecs() for i in range(0, 999): popped_item = my_list.pop(100) time = millisecs() - time print("ms: ", time) if __name__ == '__main__': main() Und die Resultate: BMax: Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 839 popping 1000 items from position 100 ms: 162712 Process complete Python: Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 1297 popping 1000 items from position 100 ms: 7112 Process finished with exit code 0 Mir ist klar, dass der Flaschenhals in BMax die häufigen Iterationen sind, allerdings ist das mit den TLists anders nicht möglich (wüsste zumindest nicht wie). Zudem kann man in BMax nicht einfach Elemente aus der Mitte einer TList herausnehmen (á pop), was sehr schlecht ist. (Mir ist bewusst, dass bei diesem Test im BMax code immer das selbe Element zurückgegeben wird, da es nicht entfernt wird. Allerdings macht es auch keinen Unterschied, da eh immer auf das hundertste Element zugegriffen wird, ob es nun das Selbe ist oder nicht ![]() Ja und Slices kann man erst recht vergessen - grausam Langsam! Python ist zwar beim "appenden" der Elemente etwas langsamer (da Python interpretiert ist) allerdings um ein vielfaches schneller beim "poppen" als BMax mit seinen zig tausenden Iterationen. Warum dann keine Arrays benutzen? Weil die Größe ständig wächst und schrumpft, daher muss es dynamisch sein und BMax bietet solche arrays nicht an von Haus aus. Hatte es in BMax über verschiedene Wege versucht: TList, Slices, MemCopy(Bmax), memcpy(CppDLL) aber nichts war schnell genug. Leider kann man auf die Elemente einer Linked List nicht über Baseaddress * Offset zugreifen da die Elemente ja verstreut im Speicher liegen. Wie seht ihr das? Gibts da was schnelleres, oder eine andere Möglichkeit, Daten dynamisch und indexiert abzulegen? Bin auf eure Meinungen gespannt! G, Trust ---- EDIT ---- Der oben gepostete BMax code ist als "Trash" anzusehen, da ich da wohl Müdigkeitsfehler eingebaut habe (3 Uhr Nachts) und dadurch das Ergebnis zu ungunsten BMax's ausfiel. Die Aufklärung ist in den folgenden Posts! ![]() ---- EDIT 2 ---- Es sind nun vier Funktionen und diese ein bissl aufbereitet. Habe sie ins Codearchiv gestellt, da ich denke dass sie ziemlich nützlich sind: [TListEx] Indexbasierte Zugriffe (ähnlich wie bei arrays) G Trust |
||
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen. |
- Zuletzt bearbeitet von Trust am Sa, Feb 03, 2018 12:51, insgesamt 4-mal bearbeitet
![]() |
HolzchopfMeisterpacker |
![]() Antworten mit Zitat ![]() |
---|---|---|
Guten Morgen ![]() 1. k muss auch immer wieder brav zurückgesetzt werden, sonst findest du nur beim ersten Durchgang von For Local str:String = EachIn myList ein 100. Element ![]() 2. Schleifen werden mit Exit abgebrochen, nicht mit Continue ![]() BlitzMax: [AUSKLAPPEN] SuperStrict LG Holzchopf Edit ey was macht die Forensoftware denn da? __COMMENT3__ = nicht vergessen, den Zähler auch wieder zurückzusetzen __COMMENT4__ = Schleifenabbruch mit Exit |
||
![]() |
Trust |
![]() Antworten mit Zitat ![]() |
---|---|---|
Guten Morgen,
haha, was hab ich denn da gestern Nacht fabriziert, Schleifen mit continue abrechen und k mit 0 initialisieren aber auf 100 überprüfen ![]() ![]() Zitat: 1. k muss auch immer wieder brav zurückgesetzt werden, sonst findest du nur beim ersten Durchgang von For Local str:String = EachIn myList ein 100. Element Wink
k wurde doch immer zurück gesetzt oder was meinst du jetzt? Originalcode BlitzMax: [AUSKLAPPEN] For Local j:Int = 0 To 999 |
||
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen. |
![]() |
Midimaster |
![]() Antworten mit Zitat ![]() |
---|---|---|
Dann sind aber auch deine Performance-Ergebnisee falsch! Bei mir kommt BMax da auf 1msec und damit ist es 7112x schneller als Python, oder? ![]() |
||
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe |
![]() |
HolzchopfMeisterpacker |
![]() Antworten mit Zitat ![]() |
---|---|---|
Trust hat Folgendes geschrieben: k wurde doch immer zurück gesetzt oder was meinst du jetzt?
Da wird k zurückgesetzt, aber das ist mMn nicht der richtige Ort. Wenn nämlich deine Liste nur 75 Elemente lang wäre, würde beim erste j-Durchlauf kein 100. Element gefunden und demnach k nicht zurückgesetzt, beim zweiten j-Durchlauf würde dann fälschlicherweise das 25. Element gefunden, weil zu Beginn der EachIn-Schleife k schon 75 war... Der Fehler zieht sich dann fort. Deshalb müsste k vor jeder EachIn-Schleife zurückgesetzt werden. Aber zugegeben: Das wird nur in diesem Fall mit verschachtelten Schleifen auftauchen. Was interessant wäre: Wie schneiden Phyton und BMax ab, wenn nicht das 100. Element, sondern das 100000. "gepoppt" werden soll? Schliesslich sind 100 Elemente relativ wenig, um mal eben durchzuzählen. |
||
Erledige alles Schritt um Schritt - erledige alles. - Holzchopf
CC BY ♫ BinaryBorn - Yogurt ♫ (31.10.2018) Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm |
![]() |
Trust |
![]() Antworten mit Zitat ![]() |
---|---|---|
Hallo Midimaster,
ja da hast du recht, habe den ersten Post mit einem "EDIT" versehen. Allerdings muss die Pop-Funktion noch abgeändert werden, sodass die Elemente auch wirklich entfernt werden. Habe die Pop-Funktion von Holzchopf so umgeschrieben, dass sie auch wirklich das Element aus der Liste entfernt und zurückgibt. Hier der neue bearbeitete Code: BlitzBasic: [AUSKLAPPEN] SuperStrict @Holzchopf Ah ok, nun verstehe ich was du meinst. Ja für den speziellen Fall macht es keinen Unterschied. Zitat: Was interessant wäre: Wie schneiden Phyton und BMax ab, wenn nicht das 100. Element, sondern das 100000. "gepoppt" werden soll? Schliesslich sind 100 Elemente relativ wenig, um mal eben durchzuzählen.
Gleich mal getestet: BMax Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 493 popping 1000 items from position 100000 Items before popping: 10000000 ms: 820 Items after popping: 9999000 Process complete Python Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 1486 popping 1000 items from position 100000 ms: 7096 Process finished with exit code 0 Interessant: in Python ist die Position egal. Nochmal ein Test an Position 999000: BMax Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 524 popping 1000 items from position 999000 Items before popping: 10000000 ms: 8295 Items after popping: 9999000 Process complete Python Code: [AUSKLAPPEN] Appending 10 million items to list...
ms: 1314 popping 1000 items from position 999000 ms: 6789 Process finished with exit code 0 Daran kann man schön sehen, dass in Python nicht iteriert wird sondern über Adressen gearbeitet wird, da die Zeit relativ konstant bleibt. ---- EDIT ---- Es sind nun vier Funktionen und diese ein bissl aufbereitet. Habe sie ins Codearchiv gestellt, da ich denke dass sie ziemlich nützlich sind: Indexbasierte Zugriffe für TLists (ähnlich wie bei arrays) ---- EDIT 2 ---- Mir ist nach einigen weiteren Tests aufgefallen, dass die Methode "FindLink" BlitzMax: [AUSKLAPPEN] Local objLink:TLink = pList.FindLink(iobj) bei 10 Millionen Elementen ca. 150 bis 200 msec braucht. Da wäre es doch besser, nicht durch die Objekte der Liste zu iterieren und dann den Link des Objekts zu suchen, sondern gleich durch die Links iterieren und dann vom Link aufs Objekt schließen. Das ist um ein vielfaches schneller, da jeder Link eh das Objekt beinhaltet über Link._value. Um das zu realisieren, kann man nicht mehr über "foreach" durch die Elemente iterieren sondern es muss eine eigene Funktion her: BlitzMax: [AUSKLAPPEN] Function NextLink:Int( link:TLink Var ) Hier die abgeänderte PopFromList Funktion: BlitzMax: [AUSKLAPPEN] Function PopFromList:Object(pList:TList, pIndex:Int) Im Codearchiv wurden die Funktionen ebenfalls angepasst. G, Trust |
||
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen. |
ohazBetreff: Re: Linked List speedtest BMax vs Python |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
Trust hat Folgendes geschrieben: Mir ist bewusst, dass bei diesem Test im BMax code immer das selbe Element zurückgegeben wird, da es nicht entfernt wird. Allerdings macht es auch keinen Unterschied, da eh immer auf das hundertste Element zugegriffen wird, ob es nun das Selbe ist oder nicht Technisch gesehen ist das falsch, vor allem bei langen Listen. Wenn man mehrmals auf das selbe Element zugreift ist es ab dem ersten Zugriff im Cache und kann von da an im Normallfall schneller gelesen werden. Wenn jedes mal ein anderes Element gelesen wird mag das zwar bei den ersten paaren auch noch im Cache sein, aber irgendwann wird es das nicht mehr sein - und dann wird das lesen drastisch langsamer.
![]() |
||
![]() |
DAK |
![]() Antworten mit Zitat ![]() |
---|---|---|
Python ist die Position deswegen egal, weil dort ArrayLists verwebdet werden statt LinkedLists. Das macht den Zugriff auf ein Element über den Index wesentlich schneller (O(1) statt O(n)), dafür das Einfügen oder Löschen am Anfang oder in der Mitte der Liste wesentlich langsamer (O(n) statt O(1)).
Da beides Vor- und Nachteile hat, liefert z.B. Java beides mit und man kann je nach Situation entscheiden, was man braucht. Bei Python ersetzt die Arraylist auch gleich das Array (da die Arraylist gegenüber dem Array kaum Nachteile hat), weswegen es nur die Arraylist gibt. Dass es in BMax nur eine LinkedList gibt hat mich schon länger gewurmt. |
||
Gewinner der 6. und der 68. BlitzCodeCompo |
![]() |
Trust |
![]() Antworten mit Zitat ![]() |
---|---|---|
Hi DAK,
ah ok alles klar. Das ist gut zu wissen (mache nicht viel mit Python). Das heißt, das Python jedes mal wieder Speicher für das gesamte Array + sizeOf(newElement) reservieren muss und dann das Array + newElement kopieren muss wenn O(n). Das kann ja recht langsam werden bei großen Arrays. |
||
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen. |
ohaz |
![]() Antworten mit Zitat ![]() |
|
---|---|---|
Ich habe mir die genaue Implementierung der Arrayliste in python nicht angesehen, aber ich gehe davon aus, dass sie exponentiell mehr Speicher reserviert als sie tatsächlich braucht, um seltener kopieren zu müssen. | ||
![]() |
Lobby |
![]() Antworten mit Zitat ![]() |
---|---|---|
Zudem kann beim Verschieben von sehr vielen Elementen durch Verwendung des DMA-Controllers CPU-Zeit eingespart werden. Ich weiß allerdings nicht, ob eine der Implementierungen das hier leistet. Meines Wissens nach sind ArrayLists State of the Art da sie keinen Overhead durch Link-Objekte erzeugen und durch die Verwendung eines exponentiell wachsenden Arrays der Aufwand zum Einfügen am Ende amortisiert nicht schlechter ist als bei verlinkten Listen. | ||
TheoTown - Eine Stadtaufbausimulation für Android, iOS, Windows, Mac OS und Linux |
![]() |
DAK |
![]() Antworten mit Zitat ![]() |
---|---|---|
Es wächst langsamer als exponentiell, aber schneller als linear. Laut dieser Seite ist das Wachstumsmuster das Folgende: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …
Das heißt, es muss zwar schon immer wieder kopiert werden, aber bei weitem nicht jedes Mal. Außerdem wird nicht allzu arg viel Speicher verschwendet. Und im Hinblick auf die Operationen ist es dann auch nicht so übel. Will man z.B. bei einer ArrayList in der Mitte etwas hinzufügen, dann müssen alle Elemente nach dem eingefügten Element kopiert und nach hinten geschoben werden. Das kostet also O(n) Schritte für das Kopieren + einen Schritt zum hinzufügen. Bei einer LinkedList braucht es O(n) Schritte um die Einfügeposition überhaupt erst zu finden und dann einen Schritt um das neue Element einzufügen. Selbiges gilt für Löschen in der Mitte. Hinzufügen am Ende kostet bei der ArrayList meistens einen Schritt, aber beim Resizen braucht es O(n) Schritte. Da das aber nur recht selten vorkommt redet man hier von amortisierten Kosten von O(1). Das Löschen am Ende kostet immer nur einen Schritt. Bei einer LinkedList kostet es beides nur einen Schritt. Der Direktzugriff auf irgendein Element kostet bei einer ArrayList immer nur einen Schritt. Bei einer LinkedList muss das Element (so es nicht das Erste oder Letzte ist) erst gesucht werden und kostet dafür O(n) Schritten. Also zum Zusammenfassen: Am Ende hinzufügen/löschen: LinkedList: O(1) ArrayList: O(1) (amortisiert) Am Anfang hinzufügen/löschen: LinkedList: O(1) ArrayList: O(n) In der Mitte hinzufügen/löschen: LinkedList: O(n) ArrayList: O(n) Am Anfang oder am Ende lesen LinkedList: O(1) ArrayList: O(1) In der Mitte lesen LinkedList: O(n) ArrayList: O(1) Liest man also Werte aus der Mitte ist die ArrayList wesentlich besser. Will man Elemente am Anfang dranhängen, dann ist die LinkedList wesentlich besser (kommt allerdings selten vor weil man ja auch einfach bei umgekehrter Reihenfolge an das Ende dranhängen kann). Hängt man viel am Ende dran und liest nur vom Ende (z.B. bei einem Stack), dann kann die LinkedList ein kleines Bisschen schneller sein, da sie nie die ganze Liste kopieren muss. Allerdings ist das nur dann relevant, wenn die Liste stark wächst. Wenn man immer am Ende was dran tut und wieder wegnimmt, so dass die Liste in ähnlich langer Länge bleibt, dann ist die ArrayList wieder gleich schnell. Für die meisten Einsatzzwecke ist also die ArrayList deutlich sinnvoller. PS: Falls wer die O-Notation nicht kennt, das funktioniert so, dass man von der Laufzeit nur das relevanteste Glied nimmt. n ist dabei die Anzahl der Elemente. Hat man z.B. eine Laufzeit von n+1, dann ist die Laufzeit in O-Notation O(n), da bei sehr hohem n die 1 irrelevant wird. Das Gleiche gilt auch bei n+n², da ist es in O-Notation O(n²), da das n auf Dauer irrelevant wird. Konstante Faktoren werden bei der Notation auch immer weggelassen. Ist die Laufzeit also z.B. n²/5, dann ist das in O-Notation O(n²). Der Sinn von dieser Notation ist, dass man auf einen Blick die Skalierbarkeit eines Algos oder einer Datenstruktur erkennen und vergleichen kann, und sich nicht in kleinen Details verliert. |
||
Gewinner der 6. und der 68. BlitzCodeCompo |
![]() |
Thunder |
![]() Antworten mit Zitat ![]() |
---|---|---|
Es gibt in BlitzMax übrigens Module, ein paar davon sind standardmäßig dabei.
Wenn du z.B. pub.stdc importierst (was standardmäßig bei BlitzMax dabei ist), kannst du auf memcpy usw. zugreifen: Link https://github.com/blitz-resea...d/stdc.bmx Man muss sich nicht immer für alles eine kleine DLL bauen ![]() |
||
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit |
![]() |
Trust |
![]() Antworten mit Zitat ![]() |
---|---|---|
Hallo Leute,
danke für die zahlreichen Antworten! ![]() Nachdem ich mich nochmal ein bisschen mit den Funktionen beschäftigt hatte, ist mir aufgefallen, dass die Methode tlist.Count() doch wirklich extrem langsam ist, da sie jedes mal durch die gesamte Liste iteriert und einen Counter mitlaufen lässt um die Elemente zu zählen. Bei einem Test wo die Count()-Methode 10x aufgerufen wird, bei einer Liste mit 10 Mio Elementen dauerte es über 3 sek. Code: [AUSKLAPPEN] Calling Count()-Method 10 times
ms: 3184 Count: 10000000 Process complete Das könnte man doch besser lösen, indem man beim Hinzufügen/Löschen von Elementen schon einen Counter mitzählen lässt, und dann beim Aufruf der Count()-Methode nur diesen Counter zurückgibt. Um das "im Hintergrund" zu lösen ohne dass sich der User drum kümmern muss, habe ich alles in eine Klasse gepackt die von TList erbt. BlitzMax: [AUSKLAPPEN] Type TListEx Extends TList Die genaue Funktionsweise wird im Codearchiv erklärt: [TListEx] Indexbasierte Zugriffe (ähnlich wie bei arrays) G, Trust |
||
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen. |
Übersicht


Powered by phpBB © 2001 - 2006, phpBB Group