User Tools

Site Tools


k7:k7.3:k7.3.1:start

7.3.1 Class List (gb. data)

The List class implements a circular, double-linked list of elements. The classification as “double-linked” means that each item in the list is linked to a previous and next item in the list. In a “circular” list, the successor of the last element is again the first element and the predecessor of the first element is the last element.

So one can run through these kind of lists ring-shaped both forward and backward. The elements in a chained list are of type Variant. This allows you to save everything in a chained list - from integer to float and string to objects.

7.3.1.1.1 Properties

The properties of a concatenated list are manageable in number and are shown in the following table:

Property Data typeDescription
.Backwards.List.backwards (ReadOnly)Virtual object for enumeration backward
.CountInteger (ReadOnly)Number of elements of the List
.CurrentVariantValue of the current list element

Table 7.3.1.1.1.1: Properties of the List class

  • For example, a list can be used to iterate with' For Each'. All values are processed from the first to the last value. The value of. current does not change.
  • For Each vElement In hList', for example, the variant variable' vElement' runs through all elements of the list' hList' one after the other from the first to the last.
  • The List. Backwards property can be used to reverse the operation of' For Each':' For Each vElement In hList. Backwards' results in the reverse order of values that' vElement' assumes.

7.3.1.2 Methods of a List Object

A concatenated list always has a virtual root element that has no value. When a list object is instantiated, only the root element exists. It is its own predecessor and successor. In this case, the list is also called “empty”.

The root element is logically always between the first and the last element. However, you do not have access to this root element. It is ignored in all operations because it has no value, but the root element helps explain some methods.

MethodDescription
Clear ()Remove all elements
Append (aElement)add aElement to the beginning; after the root-element
Prepend (pElement)add pElement to the end; before the root-element
Take (Optional iIndex)Return and remove the current item. Optionally, an index can be transferred. If this is the case, the element with the specified index relative to the root element is returned and removed. Negative indices are allowed. They run backwards from the root element.
MoveFirst ()Let the current element point to the first of the list
MoveLast ()Let the current element point to the last of the list
MoveNext ()Let the current element point to its successor
MovePrev ()Synonym for MovePrevious ()
MovePrevious () Let the current element point to its predecessor
FindFirst (vValue)Show the current element on the first find of a certain value in the list
FindLast (vValue)Let the current element point to the last find of a value
FindNext (vValue)Beginning with the successor of the current element, search for a value forward. This method can use the end of the list to switch back to the beginning and continue searching there. After each element has been examined once, the method terminates.
FindPrev ()Synonym for FindPrevious (vValue)
FindPrevious (vValue)Search backwards starting from the predecessor of the current element. This method can switch back to the end via the top of the list.

Table 7.3.1.2.1: Methods of the List class

  • Like many classes in Gambas, List also has a current element - Current. The List. Current property returns or sets its value. Using the Move* () methods, you can determine another element for the current element.
  • When a list object is instantiated, the current element is in an undefined state because there is no (real) element in the list. It is called “invalid”. If the value of an invalid element is queried, zero is returned. An error is triggered when an invalid element is to be removed.
  • The current element becomes invalid if one of the Find* () methods does not find the value to be searched for.

7.3.1.3 The difference between list and array (variant[])

Note that the Find* () methods do not work well with the CPU data caches. The list elements are allocated separately, individually, in the memory of the computer and are then loosely connected to each other. Modern computers profit greatly from their fast cache caches, which store values according to heuristics, the spatiality of accesses, for example, in order to be able to access them very quickly at a later date. Thus, when a program accesses a memory block, the computer assumes that it will access another memory block nearby shortly afterwards. However, this is not the case for lists, since their elements can be distributed anywhere in the main memory. The iteration over many list elements (as when searching for values in the list) renders all data in the CPU data caches unusable, which in turn slows down the execution of the entire program.

In this context, it is also possible to access the ith element in a list with' hList[i]'. However, this is a very time-consuming operation, since all elements from the first to the third element have to be run through. Similar to List. Take (), the index' i' can be negative to count elements backwards from the end of the list.

A list is not meant for arbitrary access to the elements as you are used to from an array, but for sequential access patterns (MoveNext () and MovePrev ()). A list can be much more efficient than an array if you don't use it too often to find values or move through all the elements. The advantage of saving the elements of the list separately is that a very low and above all constant effort must be used if a list element is to be added or removed. However, if an element is added or removed from an array, the entire array may have to be copied to a different location, which is very time-consuming for large arrays.

Whether a list or an array is used depends on the intended access pattern and must be carefully considered beforehand. In case of doubt, you should always use an array. For all stress tests carried out, the Variant[] class was superior to the List class.

Download

Articles

Download


7.3.1 Klasse List (gb.data)

Die Klasse List implementiert eine zirkuläre, doppelt-verkettete Liste von Elementen. Die Klassifikation als “doppelt-verkettet” bedeutet, dass jedes Element der Liste mit einem vorhergehenden und einem nächsten Element der Liste verbunden ist. Bei einer “zirkulären” Liste ist der Nachfolger des letzten wieder das erste Element und der Vorgänger des ersten Elements ist das letzte Element.

Man kann diese Art von Listen also ringförmig sowohl vorwärts als auch rückwärts durchlaufen. Die Elemente in einer verketteten Liste sind vom Typ Variant. Das ermöglicht es Ihnen in einer verketteten Liste alles zu speichern – von Integer über Float und String bis hin zu Objekten.

7.3.1.1 Eigenschaften

Die Eigenschaften einer verketteten Liste sind von der Anzahl her überschaubar und werden in der folgenden Tabelle angegeben:

Eigenschaft DatentypBeschreibung
.Backwards.List.Backwards (ReadOnly)Virtuelles Objekt zur Enumeration rückwärts
.CountInteger (ReadOnly)Anzahl der Elemente der Liste
.CurrentVariantWert des aktuellen Listenelements

Tabelle 7.3.1.1.1: Eigenschaften der Klasse List

  • Über eine Liste kann zum Beispiel mit 'For Each' iteriert werden. Dabei werden alle Werte vom ersten bis zum letzten durchlaufen. Der Wert von .Current verändert sich dabei nicht.
  • Mit 'For Each vElement In hList' zum Beispiel durchläuft die Variant-Variable 'vElement' alle Elemente der Liste 'hList' nacheinander vom ersten bis zum letzten.
  • Die Eigenschaft List.Backwards kann benutzt werden, um die Operation von 'For Each' umzukehren: 'For Each vElement In hList.Backwards' resultiert in der umgekehrten Reihenfolge von Werten, die 'vElement' annimmt.

7.3.1.2 Methoden eines List-Objektes

Eine verkettete Liste besitzt immer ein virtuelles root-Element, das keinen Wert hat. Bei der Instantiierung eines List-Objektes ist nur das root-Element vorhanden. Es selbst ist sein eigener Vorgänger und Nachfolger. In diesem Fall wird die Liste auch als “leer” bezeichnet.

Das root-Element liegt logisch immer zwischen dem ersten und dem letzten Element. Sie haben jedoch keinen Zugriff auf dieses root-Element. Es wird bei allen Operationen übergangen, da es keinen Wert trägt, aber das root-Element hilft bei der Erklärung einiger Methoden.

MethodeBeschreibung
Clear()Entfernen aller Elemente
Append(aElement)aElement an den Anfang anfügen; hinter das root-Element
Prepend(pElement)pElement an das Ende anfügen; vor das root-Element
Take(Optional iIndex)Zurückgeben und Entfernen des aktuellen Elements. Es kann optional ein Index übergeben werden. Ist dies der Fall, wird das Element mit dem angegebenen Index relativ zum root-Element zurückgegeben und entfernt. Negative Indizes sind erlaubt. Sie laufen rückwärts vom root-Element.
MoveFirst()Das aktuelle Element auf das erste der Liste zeigen lassen
MoveLast()Das aktuelle Element auf das letzte der Liste zeigen lassen
MoveNext()Das aktuelle Element auf seinen Nachfolger zeigen lassen
MovePrev()Synonym für MovePrevious()
MovePrevious() Das aktuelle Element auf seinen Vorgänger zeigen lassen
FindFirst(vValue)Das aktuelle Element auf den ersten Fund eines bestimmten Wertes in der Liste zeigen lassen
FindLast(vValue)Das aktuelle Element auf den letzten Fund eines Wertes zeigen lassen
FindNext(vValue)Beginnend beim Nachfolger des aktuellen Elements einen Wert vorwärts suchen. Diese Methode kann über das Ende der Liste wieder zum Anfang umschlagen und dort weitersuchen. Nachdem jedes Element einmal untersucht wurde, bricht die Methode ab.
FindPrev()Synonym für FindPrevious(vValue)
FindPrevious(vValue)Beginnend beim Vorgänger des aktuellen Elements einen Wert rückwärts suchen. Diese Methode kann über den Anfang der Liste wieder zum Ende umschlagen.

Tabelle 7.3.1.2.1: Methoden der Klasse List

  • Wie viele Klassen in Gambas besitzt auch List ein aktuelles Element – Current. Die Eigenschaft List.Current gibt seinen Wert zurück oder setzt ihn. Mithilfe der Move*()-Methoden kann man ein anderes Element zum aktuellen Element bestimmen.
  • Bei der Instanziierung eines List-Objektes ist das aktuelle Element in einem undefinierten Zustand, denn es existiert noch kein (echtes) Element in der Liste. Es wird als “invalid” bezeichnet. Sollte der Wert eines invaliden Elements abgefragt werden, wird Null zurückgegeben. Ein Fehler wird ausgelöst, wenn ein invalides Element entfernt werden soll.
  • Das aktuelle Element wird invalid, wenn eine der Find*()-Methoden den zu suchenden Wert nicht findet.

7.3.1.3 Der Unterschied zwischen List und Array (Variant[])

Man beachte, dass die Find*()-Methoden nicht gut mit den CPU-Datencaches zusammenarbeiten. Die Listenelemente werden separat, jedes für sich, im Speicher des Rechners alloziert und dann lose miteinander verbunden. Moderne Rechner profitieren sehr stark von ihren schnellen Cache-Zwischenspeichern, in denen u.a. nach der Heuristik, der Spatialität von Zugriffen, Werte gespeichert werden, um auf diese später besonders schnell zugreifen zu können. Der Rechner nimmt also an, wenn ein Programm auf einen Speicherblock zugreift, dass es kurze Zeit später auf einen weiteren Speicherblock ganz in der Nähe zugreifen wird. Bei Listen ist das aber nicht der Fall, da ihre Elemente beliebig im gesamten Hauptspeicher verteilt sein können. Die Iteration über viele Listenelemente (wie beim Suchen von Werten in der Liste) macht damit sämtliche Daten in den CPU-Datencaches unbrauchbar und das wiederum verlangsamt die Ausführung des gesamten Programms.

Es besteht in diesem Zusammenhang auch die Möglichkeit, auf das i-te Element in einer Liste mit 'hList[i]' zuzugreifen. Das ist aber eine sehr zeitintensive Operation, da hierfür alle Elemente vom ersten bis zum i-ten Element durchlaufen werden müssen. Ähnlich wie bei List.Take() kann der Index 'i' negativ sein, um Elemente vom Ende der Liste rückwärts abzuzählen.

Eine Liste ist nicht für beliebigen Zugriff auf die Elemente gedacht, wie man es von einem Array gewohnt ist, sondern für sequenzielle Zugriffsmuster (MoveNext() und MovePrev()). Eine Liste kann sehr viel effizienter als ein Array sein, wenn man sie nicht zu oft zum Finden von Werten oder zum Durchwandern aller Elemente gebraucht. Die separate Speicherung der Elemente der Liste hat nämlich den Vorteil, dass ein sehr geringer und vor allem konstanter Aufwand betrieben werden muss, wenn ein Listenelement hinzugefügt oder entfernt werden soll. Wird bei einem Array hingegen ein Element hinzugefügt oder entfernt, kann es sein, dass das gesamte Array an einen anderen Ort kopiert werden muss, was bei großen Arrays sehr aufwändig ist.

Ob eine Liste oder ein Array benutzt wird, hängt vom beabsichtigten Zugriffsmuster ab und muss im Vorfeld sorgfältig überlegt werden. Im Zweifelsfall sollte man immer zu einem Array greifen. Bei allen durchgeführten Stress-Tests war die Variant[]-Klasse der List-Klasse überlegen.

Download

Artikel

Download

The website uses a temporary session cookie. This technically necessary cookie is deleted when the browser is closed. You can find information on cookies in our privacy policy.
k7/k7.3/k7.3.1/start.txt · Last modified: 02.07.2018 (external edit)

Page Tools