Tutorial

Optimierungen

von

Seite 5 von 9

Arrays, LinkedLists, ...
Angenommen, wir möchten eine Grafische Balken- oder Linienanzeige programmieren, dann benötigen wir hierfür ein Array, oder eine LinkedList, welche die Informationen speichert.

Eine sehr einfache und zu einem gewissen Teil auch schnelle Variante ist ein Array.

Dim MyArray() as UInteger

Mithilfe solch einer Liste kann man mehrere Werte abspeichern, und per 'Indexnummer' auf diese zugreifen.
Das ist ausgesprochen Hilfreich, wenn es um den Zugriff auf den Datenbereich geht. Allerdings hinderlich, wenn ein Wert hinzugefügt wird.

Hier mal ein kleines Programm, das ein Liniendiagram erzeugt. Die Werte mit denen es gefüttert wird, sind die Berechnungszeiten * 10.000.000. Da das 'Umschaufeln' von 800 Einträgen nicht sonderlich lang dauert, müssen wir eine 'Verstärkung' hinzurechnen, um etwas sehen zu können.

'Frames Per Second

Dim TFPS as UInteger

Dim TFPSC as UInteger

Dim TFPST as Double



'Eigentliches Programm

ScreenRes 800, 410, 32



'Daten-Array

Const TDataArrayItems as UInteger = 800 '800 entspricht der Breite des Fensters

Dim TDataArray(TDataArrayItems) as UInteger





Dim TMoveTime as Double

Dim TMoveTimeLast as Double = Timer()

Dim X as UInteger

Do Until InKey() = Chr(27)

    TMoveTime = Timer()

    'ArrayDaten bearbeiten

    '* Zuerst alle Werte um 1 nach vorn verschieben

    For X = 2 to TDataArrayItems

        TDataArray(X - 1) = TDataArray(X)

    Next

    '* neuen Wert erzeugen und am Ende des Arrays Speichern

    TDataArray(TDataArrayItems) = Fix(TMoveTimeLast * 10000000)

    TMoveTimeLast = Timer() - TMoveTime



    'FPS ermitteln

    TFPSC += 1

    If TFPST < Timer() Then

        TFPS = TFPSC

        TFPSC = 0

        TFPST = Timer() + 1

    End If



    'zeichnen

    ScreenLock()

    CLS()

    For X = 1 to TDataArrayItems - 1

        Line (X - 1, 400 - TDataArray(X))-(X, 400 - TDataArray(X + 1)), &HFF

    Next

    Draw String (10, 10), "FPS:" & Str(TFPS), &HFFFFFF

    Draw String (10, 30), "MT: " & Str(Fix(TMoveTimeLast * 10000000)), &HFFFFFF

    ScreenUnLock()



    'CPU schonen

    Sleep 1, 1

Loop

screen 0

End

Auf meiner Rechenkiste erhalte ich damit rund 230 bis 240 FPS. Je nachdem, ob Linux (auch Windows) gerade mit etwas anderes beschäftigt ist, z.B. durch einen Threadwechsel, und dadurch die Zeit leicht ansteigt.
Die Spitzenwerte, welche gelegentlich beim Ablauf auftauchen sind die Threadwechsel zwischen dem eigenem Programm und einem anderen. Wurde ein Threadwechsel genau dann eingeleitet, nachdem wir die TMoveTime Variable mit dem Timer() gefüllt haben, dann kommt die Wartezeit zum Rückwechsel des eigenem Threads, zur Zeit hinzu.
Alle anderen Werte bewegen sich jedoch in einem sehr kleinem Bereich, der nur leicht schwankt.

Dieses Messverfahren werden wir jetzt einmal auf eine einfache LinkedList mit vorvergrößertem Speicher an.
Vorvergrößert heißt hier, das die Liste mit 800 Einträgen befüllt wird, und folglich beim hinzufügen nur der erste Pointer gelöscht, sowie ein neuen hinzugefügt werden muss.
Das ist im Übrigen schon ein Teil einer Optimierung.

Regulär würde man vor dem Hinzufügen prüfen, ob die Linked List bereits 'Inizialisiert' wurde, und schon ein Pointer auf einen Datenwert existiert.
Da wir die Liste jedoch bereits erzeugt haben (mit 800 Einträgen), kann man dies Vernachlässigen.

Der Quellcode sieht fast genauso aus. Es ändert sich nur das Array zu einer Linked List.

'Frames Per Second

Dim TFPS as UInteger

Dim TFPSC as UInteger

Dim TFPST as Double



'Eigentliches Programm

ScreenRes 800, 410, 32



'Daten-Liste (LinkedList)

Type Item_Type

    V_Next      as Item_Type Ptr

    V_Prev      as Item_Type Ptr

    V_Data      as UInteger

End Type

'LinkedList (leer) aufbauen

Dim TDataArray_F as Item_Type Ptr = CAllocate(SizeOf(Item_Type))

Dim TDataArray_L as Item_Type Ptr = TDataArray_F

For Y as UInteger = 2 to 800

    TDataArray_L->V_Next = CAllocate(SizeOf(Item_Type))

    TDataArray_L->V_Next->V_Prev = TDataArray_L

    TDataArray_L = TDataArray_L->V_Next

Next



Dim TMoveTime as Double

Dim TMoveTimeLast as Double = Timer()

Dim TPtr as Item_Type Ptr

Dim X as UInteger

Do Until InKey() = Chr(27)

    TMoveTime = Timer()

    'Ersten Eintrag löschen

    TPtr = TDataArray_F->V_Next

    TPtr->V_Prev = 0

    DeAllocate(TDataArray_F)

    TDataArray_F = TPtr

    '* neuen Wert erzeugen und am Ende des Arrays Speichern

    TDataArray_L->V_Next = CAllocate(SizeOf(Item_Type))

    TDataArray_L->V_Next->V_Prev = TDataArray_L

    TDataArray_L = TDataArray_L->V_Next

    TDataArray_L->V_Data = Fix(TMoveTimeLast * 10000000)

    TMoveTimeLast = Timer() - TMoveTime



    'FPS ermitteln

    TFPSC += 1

    If TFPST < Timer() Then

        TFPS = TFPSC

        TFPSC = 0

        TFPST = Timer() + 1

    End If



    'zeichnen

    ScreenLock()

    CLS()

    X = 0

    TPtr = TDataArray_F->V_Next

    Do Until TPtr = 0

        X += 1

        Line (X - 1, 400 - TPtr->V_Prev->V_Data)-(X, 400 - TPtr->V_Data), &HFF

        TPtr = TPtr->V_Next

    Loop

    Draw String (10, 10), "FPS:" & Str(TFPS), &HFFFFFF

    Draw String (10, 30), "MT: " & Str(Fix(TMoveTimeLast * 10000000)), &HFFFFFF

    ScreenUnLock()



    'CPU schonen

    Sleep 1, 1

Loop

screen 0

End

Der Umbau auf eine LinkedList hat auf meinem Rechner eine Optimierung von zwar nur geringen 10 FPS erzeugt (240 bis 250), jedoch kann man an der Grafik selbst deutlich erkennen, wie die Beschleunigung durch den Umbau des Datenspeichers die durchschnittliche Änderungszeit deutlich gesenkt werden konnte.
Der Aufwand an Code ist hier zwar gestiegen, doch dafür ist auch der Nutzen an Geschwindigkeit gewachsen!

Je nach Anwendungsfall ist entsprechend zu entscheiden, ob ein Array oder eine Linkdlist vorteilhafter sind.
Im Falle einer Zeitgrafik in der ständig ein neuer Datensatz hinzugefügt und der letzte entfernt werden muss, ist die Verwendung einer LinkdList von Vorteil, da diese kein umkopieren der eigentlich Daten nötig macht, und damit viel Zeit einsparen kann.

Im einem vorherigem Beispiel haben wir eine Liste der Verzeichnisstruktur erzeugt. Hierbei eine Linkedlist zu verwenden ist prinzipiell zwar auch möglich, jedoch nicht ratsam, da die Liste nur einmalig aufgebaut werden muss.
Außerdem ist es vorteilhafter gleich mehrere Datensätze auf einmal zu erzeugen um dort später Werte eintragen zu können. Mit einem Array funktioniert dies schneller als mit einer LinkedList, welche zusätzlich noch einen "Overhead" erzeugt.
Der Overhead einer LinkedList ist einfach ein (mindestens) 4Byte großer Speicherverbrauch pro Eintrag (Jump-Pointer)

Das Array dimensioniert mithilfe des Betriebssystems den neuen Speicher. Die Größe und die Initialisierung übernimmt Ebenfalls das Betriebssystem. Eine LinkedList muss jedoch überwiegend durch das eigene Programm erzeugt werden.
Zwar können auch hier viele kritische Teile vom Betriebssystem übernommen werden, jedoch bleibt die Verwaltung in den eigenen Händen und kann nicht abgegeben werden (was im übrigem auch keinen Sinn ergeben würde).

Gehe zu Seite 1 2 3 4 5 6 7 8 9

Zusätzliche Informationen und Funktionen

Das Tutorial wurde am 03.12.2011 von ThePuppetMaster angelegt.
Die aktuellste Version wurde am 17.05.2012 von theta gespeichert.

Bearbeiten

Versionen