Linked List speedtest BMax vs Python

Übersicht Sonstiges Smalltalk

Neue Antwort erstellen

Trust

Betreff: Linked List speedtest BMax vs Python

BeitragMi, Jan 24, 2018 3:53
Antworten mit Zitat
Benutzer-Profile anzeigen
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


Local myStr:String = "String"

Local myList:TList = New TList


Print "Appending 10 million items to list..."

Local time:Int = MilliSecs()

For Local i:Int = 0 To 9999999
myList.AddLast(myStr)
Next

time = MilliSecs() - time
Print "ms: " + time

Print ""

Print "popping 1000 items from position 100"

time:Int = MilliSecs()
Local k:Int = 0
Local poppedItem:String
For Local j:Int = 0 To 999
For Local str:String = EachIn myList
If k = 100
poppedItem = str
k = 0
Continue
EndIf
k :+ 1
Next
Next
time = MilliSecs() - time
Print "ms: " + time


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 Wink. )

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! Smile



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

Holzchopf

Meisterpacker

BeitragMi, Jan 24, 2018 7:39
Antworten mit Zitat
Benutzer-Profile anzeigen
Guten Morgen Laughing

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
2. Schleifen werden mit Exit abgebrochen, nicht mit Continue Mr. Green

BlitzMax: [AUSKLAPPEN]
SuperStrict


Local myStr:String = "String"

Local myList:TList = New TList


Print "Appending 10 million items to list..."

Local time:Int = MilliSecs()

For Local i:Int = 0 To 9999999
'myList.AddLast(myStr)
myList.AddLast(myStr+i)
Next

time = MilliSecs() - time
Print "ms: " + time

Print ""

Print "popping 1000 items from position 100"

time:Int = MilliSecs()
'Local k:Int = 0
Local poppedItem:String
For Local j:Int = 0 To 999
Rem
__COMMENT3__
k = 1
For Local str:String = EachIn myList
If k = 100
poppedItem = str
k = 0
__COMMENT4__
Exit
EndIf
k :+ 1
Next
End Rem

poppedItem = String(PopFromList(myList, 99))
'Print poppedItem
Next
time = MilliSecs() - time
Print "ms: " + time

' "poppt" ein Element aus pList an pIndex
' Indexierung beginnt bei 0 (das erste Element ist Element Nr. 0)
' Gibt das indizierte Element zurück - oder Null, wenn das Element nicht
' gefunden wurde (z.B. weil die Liste zu kurz ist)
Function PopFromList:Object(pList:TList, pIndex:Int)
Local iobj:Object, i:Int
For iobj = EachIn pList
If i = pIndex Then
Return iobj
EndIf
i :+ 1
Next
Return Null
End Function

Rem

------------------------------
Original:

Appending 10 million items to list...
ms: 398

popping 1000 items from position 100
ms: 103883

------------------------------
Continue durch Exit ersetzt:

Appending 10 million items to list...
ms: 380

popping 1000 items from position 100
ms: 1

------------------------------
myList.AddLast(myStr+i) und Print poppedItem, um prüfen zu können, ob auch
wirklich immer das 100. Element herausgezogen wird:

Appending 10 million items to list...
ms: 1232

popping 1000 items from position 100
String99
[...]
String99
ms: 191

------------------------------
"poppen" des 100. Elements via PopFromList:

Appending 10 million items to list...
ms: 1294

popping 1000 items from position 100
String99
[...]
String99
ms: 155

End Rem


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

BeitragMi, Jan 24, 2018 9:35
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Rolling Eyes , na ja war schon spät Laughing

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
For Local str:String = EachIn myList
If k = 100 ' sollte 99 sein
poppedItem = str
k = 0 '<--- k wird immer zurückgesetzt
Continue ' sollte Exit sein
EndIf
k :+ 1
Next
Next
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Midimaster

BeitragMi, Jan 24, 2018 10:11
Antworten mit Zitat
Benutzer-Profile anzeigen
Dann sind aber auch deine Performance-Ergebnisee falsch! Bei mir kommt BMax da auf 1msec und damit ist es 7112x schneller als Python, oder? Laughing
Gewinner des BCC #53 mit "Gitarrist vs Fussballer" http://www.midimaster.de/downl...ssball.exe

Holzchopf

Meisterpacker

BeitragMi, Jan 24, 2018 10:29
Antworten mit Zitat
Benutzer-Profile anzeigen
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 BYBinaryBorn - Yogurt ♫ (31.10.2018)
Im Kopf da knackt's und knistert's sturm - 's ist kein Gedanke, nur ein Wurm

Trust

BeitragMi, Jan 24, 2018 11:00
Antworten mit Zitat
Benutzer-Profile anzeigen
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


Local myStr:String = "String"

Local myList:TList = New TList


Print "Appending 10 million items to list..."

Local time:Int = MilliSecs()

For Local i:Int = 0 To 9999999
myList.AddLast(myStr)
Next

time = MilliSecs() - time
Print "ms: " + time

Print ""

Print "popping 1000 items from position 100"

Print "Items before popping: " + myList.Count()

time:Int = MilliSecs()



Local poppedItem:String
For Local j:Int = 0 To 999
poppedItem = String(PopFromList(myList, 100))
Next
time = MilliSecs() - time

Print "ms: " + time
Print ""

Print "Items after popping: " + myList.Count()




Function PopFromList:Object(pList:TList, pIndex:Int)
Local iobj:Object, i:Int = 1

For iobj = EachIn pList
If i = pIndex Then
' Get actual link
Local objLink:TLink = pList.FindLink(iobj)
' Delete Object
objLink._value = Null
' Connect previous And Next node of deleted iObj
objLink._succ._pred = objLink._pred
objLink._pred._succ = objLink._succ

Return iobj
EndIf
i :+ 1
Next
Return Null
End Function



@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 )
If link._succ._value <> link._succ
link = link._succ
Return True
EndIf
Return False
End Function


Hier die abgeänderte PopFromList Funktion:
BlitzMax: [AUSKLAPPEN]
Function PopFromList:Object(pList:TList, pIndex:Int)
Local obj:Object, i:Int = 1

' Get head of pList
Local objLink:TLink = pList._head

While NextLink( objLink )
If i = pIndex Then
' Save object for returning
obj = objLink._value
' Delete object
objLink._value = Null
' Connect previous and next node of deleted obj
objLink._succ._pred = objLink._pred
objLink._pred._succ = objLink._succ

Return obj
EndIf
i :+ 1
Wend
Return Null
End Function




Im Codearchiv wurden die Funktionen ebenfalls angepasst.


G,
Trust
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.
 

ohaz

Betreff: Re: Linked List speedtest BMax vs Python

BeitragMi, Jan 24, 2018 18:09
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Wink.
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

BeitragDo, Jan 25, 2018 11:42
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDo, Jan 25, 2018 16:09
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragDo, Jan 25, 2018 17:44
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragFr, Jan 26, 2018 16:31
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragFr, Jan 26, 2018 16:37
Antworten mit Zitat
Benutzer-Profile anzeigen
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

BeitragMi, Jan 31, 2018 13:43
Antworten mit Zitat
Benutzer-Profile anzeigen
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 Wink
Meine Sachen: https://bitbucket.org/chtisgit https://github.com/chtisgit

Trust

BeitragSa, Feb 03, 2018 13:09
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo Leute,

danke für die zahlreichen Antworten! Smile

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
Field _count:Int = 0

' ######### Overriding BMax's TList Methods #########


' This Count Method is incredibly faster than the original Count-Method
Method Count:Int()
Return Self._count
End Method


' The Methods AddFirst/AddLast are internally calling InsertBeforeLink/InsertAfterLink so they don't need to be overridden

' Add Objects
Method InsertBeforeLink:TLink( value:Object, succ:TLink )
Local link:TLink = Super.InsertBeforeLink( value, succ )
If link Then _count:+1
Return link
End Method

Method InsertAfterLink:TLink( value:Object, pred:TLink )
Local link:TLink = Super.InsertAfterLink( value, pred )
If link Then _count:+1
Return link
End Method


' Remove Objects
Method RemoveFirst:Object()
Local obj:Object = Super.RemoveFirst()
If obj Then _count:-1
Return obj
End Method

Method RemoveLast:Object()
Local obj:Object = Super.RemoveLast()
If obj Then _count:-1
Return obj
End Method

Method Remove( value:Object )
Local success:Int = Super.Remove( value )
If success Then _count:-1
End Method


' ######### New Methods/Functions #########

' This function is used internally
Function _NextLink:Int( link:TLink Var )
If link._succ._value <> link._succ
link = link._succ
Return True
EndIf
Return False
End Function

' Add an object at the given index
Method Push:TLink( value:Object, pIndex:Int )
Local newLink:TLink = New TLink, i:Int = 1
Assert value Else "Can't insert Null object into list"
Local listCount:Int = Self.Count()

' Get head of list
Local objLink:TLink = Self._head

If pIndex > listCount
Return Self.AddLast(value)
ElseIf pIndex <= 1
Return Self.AddFirst(value)
Else

While _NextLink( objLink )
If i = pIndex Then

' Assign object to Link
newLink._value = value

' The new object will be inserted before obj, so the new object gets the index of obj
' and obj gets the index of pIndex+1 and so on...

' Connect new link with its previous and next nodes
newLink._succ = objLink
newLink._pred = objLink._pred

' Connect newLink's next node with newLink
objLink._pred._succ = newLink
' Connect newLink's previous node with newLink
objLink._pred = newLink

_count:+1
Return newLink
EndIf
i :+ 1
Wend
EndIf
End Method

' Get and remove an object from the list at the given index
Method Pop:Object( pIndex:Int )
Local obj:Object, i:Int = 1
Local listCount:Int = Self.Count()

' Get head of List
Local objLink:TLink = Self._head

If pIndex >= listCount
Return Self.RemoveLast()
ElseIf pIndex <= 1
Return Self.RemoveFirst()
Else
While _NextLink( objLink )
If i = pIndex Then
' Save object for returning
obj = objLink._value
' Delete object
objLink._value = Null
' Connect previous and next node of deleted obj
objLink._succ._pred = objLink._pred
objLink._pred._succ = objLink._succ

_count:-1
Return obj
EndIf
i :+ 1
Wend
EndIf
Return Null
End Method

' Get object from list at given index
Method FromList:Object( pIndex:Int )
Local i:Int = 1
Local listCount:Int = Self.Count()

' Get head of list
Local objLink:TLink = Self._head

If pIndex >= listCount
Return Self.Last()
ElseIf pIndex <= 1
Return Self.First()
Else
While _NextLink( objLink )
If i = pIndex Then
Return objLink._value
EndIf
i :+ 1
Wend
EndIf
Return Null
End Method

' Replace the object at the given index with the given object
Method ToList:TLink( value:Object, pIndex:Int )
Local newLink:TLink = New TLink, i:Int = 1
Assert value Else "Can't insert Null object into list"

' Get head of list
Local objLink:TLink = Self._head

While _NextLink( objLink )
If i = pIndex Then
objLink._value = value
Return objLink
EndIf
i :+ 1
Wend
End Method

End Type


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.

Neue Antwort erstellen


Übersicht Sonstiges Smalltalk

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group