Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Hi,
ich muss sagen, ich verwende sehr gerne Listen (und auch Maps). Die Handhabung ist einfach sehr praktisch und übersichtlich.
Aus Interesse habe ich bei einigen Fällen, Listen durch Arrays übersetzt, da sehr sehr viele Zugriffe und Berechnungen durchgeführt wurden.
Ich war einfach gespannt, welchen Geschwindigkeitsvorteil es wohl bringen würde (in der Purebasic-Hilfe werden Arrays ja als "schneller" beschrieben).
Das Ende vom Lied war, dass es absolut nichts brachte...egal wieviel Schreibvorgänge in Listen, Lesevorgänge aus Listen...Listen waren genauso schnell wie Arrays.
Auch Funktionen wie NextElement(), SelectElement(), ResetList(), usw...alles wurde durch Schleifen bzw. direktes Ansprechen per Index des Arrays realisiert.
Ich frage mich jetzt, was ist an der Info dran? Zumindest bezogen auf PureBasic.
In welchen Fällen habt ihr Geschwindigkeitsvorteile bemerkt?
Aktuell bin ich zur Erkenntnis gekommen, dass ich Arrays wohl an den Nagel hänge, wo es geht
Ich habe dynamische Arrays verwendet...keine statischen.
Viele Grüße,
Andi
ich muss sagen, ich verwende sehr gerne Listen (und auch Maps). Die Handhabung ist einfach sehr praktisch und übersichtlich.
Aus Interesse habe ich bei einigen Fällen, Listen durch Arrays übersetzt, da sehr sehr viele Zugriffe und Berechnungen durchgeführt wurden.
Ich war einfach gespannt, welchen Geschwindigkeitsvorteil es wohl bringen würde (in der Purebasic-Hilfe werden Arrays ja als "schneller" beschrieben).
Das Ende vom Lied war, dass es absolut nichts brachte...egal wieviel Schreibvorgänge in Listen, Lesevorgänge aus Listen...Listen waren genauso schnell wie Arrays.
Auch Funktionen wie NextElement(), SelectElement(), ResetList(), usw...alles wurde durch Schleifen bzw. direktes Ansprechen per Index des Arrays realisiert.
Ich frage mich jetzt, was ist an der Info dran? Zumindest bezogen auf PureBasic.
In welchen Fällen habt ihr Geschwindigkeitsvorteile bemerkt?
Aktuell bin ich zur Erkenntnis gekommen, dass ich Arrays wohl an den Nagel hänge, wo es geht
Ich habe dynamische Arrays verwendet...keine statischen.
Viele Grüße,
Andi
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Man kann nicht sagen dass Arrays schneller als Listen sind oder umgekehrt, sondern es kommt darauf an was man macht:
- Einfügen eines Elements
- Löschen eines Elements
- direkter Zugriff auf ein Element
- etc.
Wo genau steht das so allgemein?(in der Purebasic-Hilfe werden Arrays ja als "schneller" beschrieben)
Das ist (spätestens bei langen Listen) langsamer, als auf ein Array-Element per Index zuzugreifen.SelectElement()
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Hier mal ein Beispiel für den Zugriff:
Mit 100 Elementen (im Array und in der Liste), ist der Unterschied:
Generell sind die Zeiten aber so gering (bei 10mio Zugriffe), dass dieser Unterschied in üblichen Programmen nicht auffällt,
bei massiver Datenverarbeitung aber schon ins Gewicht fällt.
Code: Alles auswählen
Define TimeArray.i, TimeList.i, I.i, N.i
#Size = 100
Global Dim MyArray.i(#Size-1)
Global NewList MyList.i()
For I = 1 To #Size
AddElement(MyList())
Next
TimeArray = ElapsedMilliseconds()
For N = 1 To 10000000
I = Random(#Size-1)
MyArray(I) + 1
Next
TimeArray = ElapsedMilliseconds()-TimeArray
TimeList = ElapsedMilliseconds()
For N = 1 To 10000000
SelectElement(MyList(), Random(#Size-1))
MyList() + 1
Next
TimeList = ElapsedMilliseconds()-TimeList
MessageRequester("Result", "TimeArray: "+StrF(TimeArray)+" ms"+#LF$+"TimeList: "+StrF(TimeList)+" ms")
Schlimmer wird es, wenn die Anzahl der Elemente weiter zunimmt, z.B. 1000TimeArray: 73 ms
TimeList: 333 ms
Während die Zeit für das Array gleich ist, steigt die bei der Liste um den Faktor 10.TimeArray: 73 ms
TimeList: 2377 ms
Generell sind die Zeiten aber so gering (bei 10mio Zugriffe), dass dieser Unterschied in üblichen Programmen nicht auffällt,
bei massiver Datenverarbeitung aber schon ins Gewicht fällt.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
- NicTheQuick
- Ein Admin
- Beiträge: 8679
- Registriert: 29.08.2004 20:20
- Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti - Wohnort: Saarbrücken
- Kontaktdaten:
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Außerdem können Arrays gut von der CPU gecached werden, da sie zusammenhängend im Speicher liegen, während bei Listen im allgemeinen jedes Element an einer andere Stelle im physischen Speicher liegen könnte und dafür ist der Cache in der CPU nicht ausgelegt. Der kann am besten zusammenhängende Daten ablegen.
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Hi,
vielen Dank für die Rückmeldungen. Ich habe das Beispiel ausprobiert und war so verblüfft, dass es sich so gar nicht mit meinen Erfahrungen deckt,
dass ich gleich noch ein wenig rumexperimentiert habe.
Bei mir kam dabei heraus, dass einzig und allein die Random-Funktion für den Geschwindigkeitsunterschied verantwortlich ist. Ersetzt man ihn durch einen festen Wert,
so sind beide Varianten gleich schnell. Warum die Random-Funktion unterschiedlich schnell ausfällt, ist mir bislang ein Rätsel...vielleicht liegt es an SelectElement.
Ich habe zwei Gegenbeispiele zur Veranschaulichung. Im ersten Beispiel zähle ich die Liste mit For-Next und NextElement() durch. Und obwohl bei jedem Durchgang
eine zusätzliche Funktion (NextElement) ausgeführt wird, ist die Liste fast gleich schnell mit dem Array.
Im zweiten Beispiel nutze ich die optimierte Variante "ForEach-Next" und hier sind dann beide Varianten gleich schnell.
Fast gleich schnell mit For-Next und NextElement():
Gleich schnell mit Verwendung von ForEach-Next:
Also reines Durchzählen, Werte reinschreiben oder auslesen macht in der Praxis wohl kaum einen Unterschied.
Oder habe ich hier etwas übersehen bzw. nicht bedacht?
Hier ein Auszug aus der PureBasic-Hilfe über Arrays:
Wenn hier kein Bezug auf Listen und Maps gemeint ist, ist der letzte Satz sehr gewagt formuliert
Viele Grüße,
Andi
vielen Dank für die Rückmeldungen. Ich habe das Beispiel ausprobiert und war so verblüfft, dass es sich so gar nicht mit meinen Erfahrungen deckt,
dass ich gleich noch ein wenig rumexperimentiert habe.
Bei mir kam dabei heraus, dass einzig und allein die Random-Funktion für den Geschwindigkeitsunterschied verantwortlich ist. Ersetzt man ihn durch einen festen Wert,
so sind beide Varianten gleich schnell. Warum die Random-Funktion unterschiedlich schnell ausfällt, ist mir bislang ein Rätsel...vielleicht liegt es an SelectElement.
Ich habe zwei Gegenbeispiele zur Veranschaulichung. Im ersten Beispiel zähle ich die Liste mit For-Next und NextElement() durch. Und obwohl bei jedem Durchgang
eine zusätzliche Funktion (NextElement) ausgeführt wird, ist die Liste fast gleich schnell mit dem Array.
Im zweiten Beispiel nutze ich die optimierte Variante "ForEach-Next" und hier sind dann beide Varianten gleich schnell.
Fast gleich schnell mit For-Next und NextElement():
Code: Alles auswählen
Define TimeArray.i, TimeList.i, n.i, Value.i
#Size = 1000000
Global Dim MyArray.i(#Size-1)
Global NewList MyList.i()
For n = 1 To #Size
AddElement(MyList())
Next
TimeArray = ElapsedMilliseconds()
For n = 0 To #Size -1
MyArray(n) = 12345
Value = MyArray(n)
Next
TimeArray = ElapsedMilliseconds()-TimeArray
TimeList = ElapsedMilliseconds()
ResetList(MyList())
For n = 1 To #Size
NextElement(MyList())
MyList() = 12345
Value = MyList()
Next
TimeList = ElapsedMilliseconds()-TimeList
MessageRequester("Result", "TimeArray: "+StrF(TimeArray)+" ms"+#LF$+"TimeList: "+StrF(TimeList)+" ms")
Gleich schnell mit Verwendung von ForEach-Next:
Code: Alles auswählen
Define TimeArray.i, TimeList.i, n.i, Value.i
#Size = 1000000
Global Dim MyArray.i(#Size-1)
Global NewList MyList.i()
For n = 1 To #Size
AddElement(MyList())
Next
TimeArray = ElapsedMilliseconds()
For n = 0 To #Size -1
MyArray(n) = 12345
Value = MyArray(n)
Next
TimeArray = ElapsedMilliseconds()-TimeArray
TimeList = ElapsedMilliseconds()
ForEach MyList()
MyList() = 12345
Value = MyList()
Next
TimeList = ElapsedMilliseconds()-TimeList
MessageRequester("Result", "TimeArray: "+StrF(TimeArray)+" ms"+#LF$+"TimeList: "+StrF(TimeList)+" ms")
Also reines Durchzählen, Werte reinschreiben oder auslesen macht in der Praxis wohl kaum einen Unterschied.
Oder habe ich hier etwas übersehen bzw. nicht bedacht?
Hier ein Auszug aus der PureBasic-Hilfe über Arrays:
Es wird hier zwar nicht direkt gesagt, dass Arrays schneller als Listen sind...aber es wird gesagt, dass Arrays im Vergleich zu Listen einen schnellen Zugriff bieten.PureBasic-Hilfe hat geschrieben:Arrays sind Strukturen zum Speichern von indizierten Elementen. Anders als bei einer verknüpften Liste oder bei einer Map werden die Elemente in einer zusammenhängenden Weise im Speicher angelegt. Somit ist es nicht so einfach möglich, ein Element einzufügen oder zu entfernen. Auf der anderen Seite bietet diese sehr schnellen und direkten Zugriff auf ein beliebiges Element.
Wenn hier kein Bezug auf Listen und Maps gemeint ist, ist der letzte Satz sehr gewagt formuliert
Viele Grüße,
Andi
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Wie du richtig bemerkt hast, ist der ungeordnete Zugriff auf Listen Elemente langsam.
Die Funktion SelectElement() speichert den letzten Aufruf im "Hinterkopf", somit wird beim nächsten Aufruf nicht wieder von vorne Durchgezählt, sondern vom aktuellen Element.
Daher sind beide beiden Beispiele etwa gleich schnell.
Wenn aber hin und her gesprungen wird, müssen immer sehr viele Listenelemente "durchwandert" werden.
Arrays: "Auf der anderen Seite bietet diese sehr schnellen und direkten Zugriff auf ein beliebiges Element."
Der Satz ist vollkommen richtig. Wichtig ist hier das "beliebiges".
Arrays sind immer schneller als Listen, wenn es um den direkten Zugriff auf ein beliebiges Element geht.
Wann du Arrays, Listen und Maps einsetzt hängt immer vom Anwendungsgebiet ab.
Genau kann ich es bei dir nicht erkennen, aber wenn du dein Array einfach immer nur von Anfang zum Ende durchläufst, kannst du genauso gut eine Liste nehmen. Außer, du brauchst den Zusammenhängenden Speicher, den du bei einem Array hast, bei einer Liste hingegen nicht.
Die Funktion SelectElement() speichert den letzten Aufruf im "Hinterkopf", somit wird beim nächsten Aufruf nicht wieder von vorne Durchgezählt, sondern vom aktuellen Element.
Daher sind beide beiden Beispiele etwa gleich schnell.
Wenn aber hin und her gesprungen wird, müssen immer sehr viele Listenelemente "durchwandert" werden.
Arrays: "Auf der anderen Seite bietet diese sehr schnellen und direkten Zugriff auf ein beliebiges Element."
Der Satz ist vollkommen richtig. Wichtig ist hier das "beliebiges".
Arrays sind immer schneller als Listen, wenn es um den direkten Zugriff auf ein beliebiges Element geht.
Wann du Arrays, Listen und Maps einsetzt hängt immer vom Anwendungsgebiet ab.
Genau kann ich es bei dir nicht erkennen, aber wenn du dein Array einfach immer nur von Anfang zum Ende durchläufst, kannst du genauso gut eine Liste nehmen. Außer, du brauchst den Zusammenhängenden Speicher, den du bei einem Array hast, bei einer Liste hingegen nicht.
PB 6.01 ― Win 10, 21H2 ― Ryzen 9 3900X, 32 GB ― NVIDIA GeForce RTX 3080 ― Vivaldi 6.0 ― www.unionbytes.de
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Aktuelles Projekt: Lizard - Skriptsprache für symbolische Berechnungen und mehr
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Hi Stargate,
vielen Dank! Ich muss sagen, du hast es genau auf den Punkt gebracht, dass es bei mir Klick gemacht hat!
Eigentlich stehts ja sogar schon in der Hilfe drin...das Wort "beliebiges" sollte in der Hilfe Fett markiert werden
Listen gehe ich tatsächlich meist der Reihe nach durch...bei beliebigen Zugriffen bin ich bisher meist auf Maps ausgewichen.
Arrays habe ich in PureBasic bislang kaum verwendet (nur für externe Funktionen), da ich entweder Elemente mitten in den Listen enfernen oder hinzufügen musste (bei Arrays recht kompliziert),
oder eben ein Schlüsselwort als Zugriff gebraucht habe.
Viele Grüße
vielen Dank! Ich muss sagen, du hast es genau auf den Punkt gebracht, dass es bei mir Klick gemacht hat!
Eigentlich stehts ja sogar schon in der Hilfe drin...das Wort "beliebiges" sollte in der Hilfe Fett markiert werden
Listen gehe ich tatsächlich meist der Reihe nach durch...bei beliebigen Zugriffen bin ich bisher meist auf Maps ausgewichen.
Arrays habe ich in PureBasic bislang kaum verwendet (nur für externe Funktionen), da ich entweder Elemente mitten in den Listen enfernen oder hinzufügen musste (bei Arrays recht kompliziert),
oder eben ein Schlüsselwort als Zugriff gebraucht habe.
Viele Grüße
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Das sind keine Gegenbeispiele, denn in beiden Beispielen wird SelectElement() - wovon vorher ausdrücklich die Rede war - gar nicht verwendet. Dass das sequentielle Durchlaufen von Listen und Arrays etwa gleich schnell ist, sollte eh klar sein.Beefi hat geschrieben:Ich habe zwei Gegenbeispiele zur Veranschaulichung.
- NicTheQuick
- Ein Admin
- Beiträge: 8679
- Registriert: 29.08.2004 20:20
- Computerausstattung: Ryzen 7 5800X, 32 GB DDR4-3200
Ubuntu 22.04.3 LTS
GeForce RTX 3080 Ti - Wohnort: Saarbrücken
- Kontaktdaten:
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Was genau musst du denn machen und wie relevant ist die Geschwindigkeit bei dir? Arbeitest du mit großen Mengen an Daten oder eher kleine Listen? Vielleicht sind ja auch sortierte Heaps für dich interessant.
Re: Geschwindigkeitsvorteil bei Arrays anstatt Listen ???
Ewentuell solltest Du auch mal Hashtables (in PB auch Map genannt) anschauen.
Ich versuche, wann immer es möglich ist Hashtables zu verwenden und nicht via for / next oder While/went etc., durch Listen oder Arrays zu stolpern um werte zu bekommen.
Da ziehe ich super schnelle Hashtables vor.
Was mich jedoch gerade ein wenig wundert ist die Geschwindigkeit beim füllen von Arra, LinkedList und Map in PB.
Ich habe dazu mal den obigen Code angepasst (mit Debugger ausführen).
M.E. nach stimmt da was mit der Zeitmessung beim füllen der Map nicht. Es benötigt wesendlich länger als die diff. zwischen Start und Endzeit beim befüllen der Map
Ich versuche, wann immer es möglich ist Hashtables zu verwenden und nicht via for / next oder While/went etc., durch Listen oder Arrays zu stolpern um werte zu bekommen.
Da ziehe ich super schnelle Hashtables vor.
Was mich jedoch gerade ein wenig wundert ist die Geschwindigkeit beim füllen von Arra, LinkedList und Map in PB.
Ich habe dazu mal den obigen Code angepasst (mit Debugger ausführen).
M.E. nach stimmt da was mit der Zeitmessung beim füllen der Map nicht. Es benötigt wesendlich länger als die diff. zwischen Start und Endzeit beim befüllen der Map
Code: Alles auswählen
Define TimeArray.i, TimeList.i, n.i, Value.i, TimeMap.i
#Size = 1000000
Global Dim MyArray.i(#Size-1)
Global NewList MyList.i()
Global NewMap MyMap.i()
;- fill Array, LinkedList and Map with values
TimeArray = ElapsedMilliseconds()
For n = 0 To #Size -1
MyArray(n) = (n)
Next
TimeArray = ElapsedMilliseconds()-TimeArray
Debug "Time to fill Array: "+StrF(TimeArray)+" ms"
TimeList = ElapsedMilliseconds()
For n = 0 To #Size -1
AddElement(MyList())
MyList() = (n )
Next
TimeList = ElapsedMilliseconds()-TimeList
Debug "Time to fill LinkedList: "+StrF(TimeList)+" ms"
TimeMap = ElapsedMilliseconds()
For n = 0 To #Size -1
MyMap(Str(n)) = (n)
Next
TimeMap = ElapsedMilliseconds() - TimeMap
Debug "Time to fill Map: "+StrF(TimeArray)+" ms"
TimeList = 0
TimeArray = 0
TimeMap = 0
;- lets read values and find value 999999
TimeArray = ElapsedMilliseconds()
For n = 0 To #Size -1
Value = MyArray(n)
If value = 999999
Debug "Array value = "+Str(value)
Break
EndIf
Next
TimeArray = ElapsedMilliseconds()-TimeArray
Debug "Time to find Array value: "+StrF(TimeArray)+" ms"
TimeList = ElapsedMilliseconds()
ResetList(MyList())
For n = 1 To #Size
NextElement(MyList())
Value = MyList()
If value = 999999
Debug "LinkedList value = "+Str(value)
Break
EndIf
Next
TimeList = ElapsedMilliseconds()-TimeList
Debug "Time to find LinkedList value via for/next loop: "+StrF(TimeList)+" ms"
TimeList = ElapsedMilliseconds()
ResetList(MyList())
While NextElement(MyList())
Value = MyList()
If value = 999999
Debug "LinkedList value = "+Str(value)
Break
EndIf
Wend
TimeList = ElapsedMilliseconds()-TimeList
Debug "Time to find LinkedList value via While/went loop: "+StrF(TimeList)+" ms"
TimeMap = ElapsedMilliseconds()
FindMapElement(MyMap(),"999999")
Debug MyMap()
TimeMap = ElapsedMilliseconds() - TimeMap
Debug "Time to find Map value: "+StrF(TimeMap)+" ms"
;MessageRequester("Result", "TimeArray: "+StrF(TimeArray)+" ms"+#LF$+"TimeList: "+StrF(TimeList)+" ms"+#LF$+"TimeMap: "+StrF(TimeMap)+" ms")