Geschwindigkeitsvorteil bei Arrays anstatt Listen ???

[Beefi]

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

[Nino]

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.

Manche Operationen sind bei Arrays schneller, andere bei Listen. Es kommt immer darauf an, wofür man die betr. Datenstruktur braucht.

(in der Purebasic-Hilfe werden Arrays ja als "schneller" beschrieben)

Wo genau steht das so allgemein?

SelectElement()

Das ist (spätestens bei langen Listen) langsamer, als auf ein Array-Element per Index zuzugreifen.

[STARGÅTE]

Hier mal ein Beispiel für den Zugriff:

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")

Mit 100 Elementen (im Array und in der Liste), ist der Unterschied:

TimeArray: 73 ms
TimeList: 333 ms

Schlimmer wird es, wenn die Anzahl der Elemente weiter zunimmt, z.B. 1000

TimeArray: 73 ms
TimeList: 2377 ms

Während die Zeit für das Array gleich ist, steigt die bei der Liste um den Faktor 10.

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.

[NicTheQuick]

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.

[Beefi]

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():

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:

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.

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.
Wenn hier kein Bezug auf Listen und Maps gemeint ist, ist der letzte Satz sehr gewagt formuliert

Viele Grüße,
Andi

[STARGÅTE]

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.

[Beefi]

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

[Nino]

Ich habe zwei Gegenbeispiele zur Veranschaulichung.

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.

[NicTheQuick]

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.

[nicolaus]

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

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")