Geschwindigkeit: Arrays <---> LinkedLists

[#NULL]

ich wollts mal wissen und hab ein paar zeit-vergleiche von zugriffen auf arrays und linkedlists, ausgetested. ist aber wohlmöglich fraglich in wie weit man daraus schlüsse ziehen sollte. wen's interessiert:

Code: Alles auswählen

OpenConsole()
Declare foo(n.l)

;    n should be at least
;    2000000 (on my machine) To get valid result
foo( 2000000)
foo( 4000000)
foo( 8000000)
foo(16000000)
;foo(32000000)   ;) got full fridge ?

PrintN ("...FINISHED.")
Input()
CloseConsole()


Procedure foo(n.l)
	PrintN( "n=" + Str(n) )
  x.l
	Dim a.l(n)
	NewList b.l()
	
	t0=ElapsedMilliseconds()
	For i=0 To n
	Next
	t0=ElapsedMilliseconds()-t0
	PrintN( "empty loop : " + Str( t0 ) + "ms    " + Str( t0*100.0/t0 ) + "%" )
	
	
	;###########################################################################
	t1=ElapsedMilliseconds()
	For i=0 To n
		a(i)=1
	Next
	t1 = ElapsedMilliseconds() - t1
	PrintN( "array - write :" + Str( t1 ) + "ms    " + Str( t1*100.0/t0 ) + "%" )
	
	
	;###########################################################################
	t2=ElapsedMilliseconds()
	For i=0 To n
		x=a(i)
	Next
	t2 = ElapsedMilliseconds() - t2
	PrintN( "array - read :" + Str( t2 ) + "ms    " + Str( t2*100.0/t0 ) + "%" )
	
	
	;###########################################################################
	t3=ElapsedMilliseconds()
	For i=0 To n
		AddElement(b())
	Next
	t3 = ElapsedMilliseconds() - t3
	PrintN( "AddElement() :" + Str( t3 ) + "ms    " + Str( t3*100.0/t0 ) + "%" )

	
	;###########################################################################
	ResetList(b())
	t4=ElapsedMilliseconds()
	For i=0 To n
		NextElement(b())
	Next
	t4 = ElapsedMilliseconds() - t4
	PrintN( "NextElement() :" + Str( t4 ) + "ms    " + Str( t4*100.0/t0 ) + "%" )

	
	;###########################################################################
	ResetList(b())
	t5=ElapsedMilliseconds()
	For i=0 To n
		NextElement(b())
		b()=1
	Next
	t5 = ElapsedMilliseconds() - t5
	PrintN( "NextElement()/write :" + Str( t5 ) + "ms    " + Str( t5*100.0/t0 ) + "%" )
	
	
	;###########################################################################
  FirstElement(b())
	t6=ElapsedMilliseconds()
	For i=0 To n
		DeleteElement(b(),1)
	Next
	t6 = ElapsedMilliseconds() - t6
	PrintN( "DeleteElement() :" + Str( t6 ) + "ms    " + Str( t6*100.0/t0 ) + "%" )
	
	
	;###########################################################################
	PrintN("")
	PrintN("")
EndProcedure

[Toshy]

Vielleicht solltest du zuerst uns deine Schlüsse erstmal mitteilen, besser noch was überhaupt dein Anliegen ist.
Gruß
Toshy

[Kaeru Gaman]

also, ich entscheide zwischen LL und Array eigentlich anhand der anwendung,
also was ich damit machen will, und welches feature ich wirklich brauche usw.
die performance ist dabei für mich eher zweitrangig.

[#NULL]

performance is a feature.

[Kaeru Gaman]

performance is a feature.

wenn du das ergebnis deines test mal mitteilen würdest, könnte ich ja mal gelegentlich in begeisterungsstürme ausbrechen...

solange bleibe ich bei meiner aussage:
Arrays und LinkedLists haben so viele unterschiedliche vor- und nachteile, so spezifische anwendungsgebiete, dass sich mir nur in den allerseltensten Fällen die Frage stellt, zwischen ihnen anhand der performance zu entscheiden.

[#NULL]

wen's interessiert (!!!):

->wen's nicht interessiert<-

n=2000000
empty loop : 63ms 100%
array - write :203ms 322%
array - read :172ms 273%
AddElement() :640ms 1016%
NextElement() :172ms 273%
NextElement()/write :297ms 471%
DeleteElement() :813ms 1290%


n=4000000
empty loop : 172ms 100%
array - write :390ms 227%
array - read :360ms 209%
AddElement() :1593ms 926%
NextElement() :375ms 218%
NextElement()/write :594ms 345%
DeleteElement() :1672ms 972%


n=8000000
empty loop : 281ms 100%
array - write :735ms 262%
array - read :718ms 256%
AddElement() :3594ms 1279%
NextElement() :719ms 256%
NextElement()/write :1109ms 395%
DeleteElement() :3016ms 1073%


...FINISHED.

[STARGÅTE]

Ich sehe das genauso wie Kaeru Gaman :

Wenn ich Eigenschafften von Spielern in einem Spiel in einem z.B. 20 Dimensionalen Array speicher ist es "dumm", und wenn ich eine Karte mit x1000*y1000 in einer Liste speicher wäre es auch unsinnig.

[#NULL]

ich sehe das ganz genauso wie ihr.

[Kaeru Gaman]

klar, is bestimmt mal interessant, sich vor augen zu führen, wie schnell ne LL wirklich ist.

und ich finde das nicht so überraschend, die tempo-verhältnisse bei so einfachen elementen bei beiden.

leider hast du keine komplexeren elementzugriffe in dem test, und das ist ja eh, was man bei LL verwendet. (also, ich jedenfalls meistens)

[Toshy]

Wie ich schon sagte, wäre nett wenn du mal auch was schreibst. Was willst du überhaupt Aussagen?

Beim Zugriff auf Daten dürfte es in der Geschwindigkeit keinen Unterschied geben. Beim Positionieren auf ein Element schon, Arrays dürften hier um einiges schneller sein. Geht es um das löschen oder direkte anspringen (per selectelement) oder ändern des genutzen Elements sind Linkedlist natürlich langsamer als Arrays. Es dient ja unterschiedlichen Zwecken und daher sind Beide (LL und Arrays) ganz unterschiedliche aufgebaut. Da ein Array einen Zusammenhängenden und geordneten SPeicherbereich nutzt (Elemement X steht an Positon X*ElementBreite) kann man ein anderes Element (intern) direkt auslesen, bei einer LL muß dazu erst der Speicherbereich gewechselt werden bzw. die Positon dazu auch erst ausgelesen werden.

Lieber #NULL bitte schreib doch mal ein paar ausführliche Sätze was du überhaupt willst. So rätselt man nur was du willst und eine Antwort ist nicht möglich. LL und Arrays dienen unterschiedlichen Dingen, je nach Anwendungsart kann entweder eine LL oder ein Array schneller sein.

Grundlegend sind Arrays schneller, aber sobald du mit einer variablen Anzahl an Elementen arbeiten willst (und in einigen anderen Fällen) sind normal LL viel schneller bzw. das einzig (sinvoll) Mögliche.

Gruß
Toshy