Tipp-Upload: VB.NET 0255: Berechnungen durch Memoisation optimieren

Hinweis zum Tippvorschlag  

Dieser Vorschlag wurde noch nicht auf Sinn und Inhalt überprüft und die Zip-Datei wurde noch nicht auf schädlichen Inhalt hin untersucht.
Bitte haben Sie ein wenig Geduld, bis die Freigabe erfolgt.

Über den Tipp  

Dieser Tippvorschlag ist noch unbewertet.

Der Vorschlag ist in den folgenden Kategorien zu finden:

• Algorithmen
• Mathematik
• Sprachmerkmale

Dem Tippvorschlag wurden folgende Schlüsselwörter zugeordnet:
Memoization, Memoisation, Dictionary, Fibonacci

Der Vorschlag wurde erstellt am: 15.04.2008 16:58.
Die letzte Aktualisierung erfolgte am 15.04.2008 16:58.

Zurück zur Übersicht

Beschreibung  

Durch eine Technik namens Memoization (Memoisation) kann man Algorithmen sehr einfach und mit stattlichen Ergebnissen optimieren. Hierbei werden Werte, anstatt sie von einer Funktion mehrfach berechnen zu lassen, zwischengespeichert und ggf. direkt und ohne erneute Berechnung zurückgegeben. Der Algorithmus selbst muss dabei kaum angepasst werden. Vorraussetzung für eine zu optimierende Funktion ist, dass sie bei gleichen Eingabewerten auch gleiche Ergebnisse liefert.
Als Datenstruktur für die Zwischenspeicherungen kann man ein Array oder meist ein Dictionary verwenden.

Das Beispiel hier zeigt eine Optimierung bzgl. der Berechnung der Fibonacci-Zahlen, die gewöhnlich rekursiv implementiert wird, wobei gigantische Rekursionsfolgen entstehen und gleiche Werte vielfach neu berechnet werden.

Durch ein paar Zeilen kann man so exponentielle auf lineare Laufzeit drücken.

Schwierigkeitsgrad

Verwendete API-Aufrufe:

Download: Download des Beispielprojektes [9,04 KB]

' Dieser Source stammt von http://www.activevb.de
' und kann frei verwendet werden. Für eventuelle Schäden
' wird nicht gehaftet.

' Um Fehler oder Fragen zu klären, nutzen Sie bitte unser Forum.
' Ansonsten viel Spaß und Erfolg mit diesem Source!
'
' Beachten Sie, das vom Designer generierter Code hier ausgeblendet wird.
' In den Zip-Dateien ist er jedoch zu finden.

' ----------- Anfang Projektgruppe Memoization.sln -----------
' ---------- Anfang Projektdatei Memoization.vbproj ----------
' ------------------- Anfang Datei Base.vb -------------------
MustInherit Class FibTester

    Protected Counter As Long

    Private Time As Long

    Protected MustOverride Function GetFib(ByVal n As Long) As Long

    Default Public ReadOnly Property Fib(ByVal n As Long) As Long
        Get
            Counter = 0

            With New Diagnostics.Stopwatch

                .Start()

                Dim Res As Long = GetFib(n)

                .Stop()

                Time = .ElapsedMilliseconds
                Return Res

            End With

        End Get

    End Property

    Public ReadOnly Property Count() As Long
        Get
            Return Counter

        End Get

    End Property

    Public ReadOnly Property Runtime() As Long
        Get
            Return Time

        End Get

    End Property

End Class

' -------------------- Ende Datei Base.vb --------------------
' ---------------- Anfang Datei Fibonacci.vb  ----------------
Class RecursiveFib

    Inherits FibTester

    Protected Overrides Function GetFib(ByVal n As Long) As Long

        Counter += 1

        If n = 1 Or n = 2 Then Return 1
        Return GetFib(n - 1) + GetFib(n - 2)

    End Function

    Public Overrides Function ToString() As String

        Return "Rekursive Fibonacci-Zahlen"

    End Function

End Class

' SO - Hier passiert die Optimierung
Class MemoizedFib

    Inherits FibTester

    Private Memo As New Dictionary(Of Long, Long) ' Zwischenwerte speichern

    ' 1 => 1 und 2 => 1 vorspeichern
    Sub New()

        Memo.Add(1, 1) : Memo.Add(2, 1)

    End Sub

    Protected Overrides Function GetFib(ByVal n As Long) As Long

        Counter += 1

        ' Nur Rekurrieren, wenn der Wert noch nicht berechnet wurde
        If Not Memo.ContainsKey(n) Then Memo.Add(n, GetFib(n - 1) + GetFib(n - 2))
        Return Memo(n)

    End Function

    Public Overrides Function ToString() As String

        Return "Fibonacci-Zahlen mit Memoization"

    End Function

End Class

Class IterativeFib

    Inherits FibTester

    Protected Overrides Function GetFib(ByVal n As Long) As Long

        Dim Cur As Long = 1, Prev As Long = 0, Tmp

        For i As Long = 2 To n
            Tmp = Prev
            Prev = Cur
            Cur += Tmp
            Counter += 1
        Next

        Return Cur

    End Function

    Public Overrides Function ToString() As String

        Return "Fibonacci-Zahlen durch Iteration"

    End Function

End Class

' ----------------- Ende Datei Fibonacci.vb  -----------------
' ----------------- Anfang Datei Module1.vb  -----------------
Module Module1

    Sub Main()

        Console.Write("Geben sie den Index der gesuchen Fibonacci-Zahl ein: ")

        Dim Num As Long = Long.Parse(Console.ReadLine())

        Dim FibonacciCalculator As FibTester = Nothing

        Do
            Console.WriteLine("Wählen sie ein Verfahren zur Berechnung:")
            Console.Write("Iterativ, Rekursiv oder per Memoization (i/r/m):")

            Dim [Char] As Char = Console.ReadKey.KeyChar

            Select Case Char.ToLower([Char])

                Case "i"c
                    FibonacciCalculator = New IterativeFib

                Case "r"c
                    FibonacciCalculator = New RecursiveFib

                Case "m"c
                    FibonacciCalculator = New MemoizedFib

            End Select

            Console.WriteLine()
        Loop While FibonacciCalculator Is Nothing

        Console.WriteLine()
        Console.WriteLine("Berechne " & FibonacciCalculator.ToString & " ....... ")
        Console.WriteLine()

        For i = 1 To 2

            Dim Res As Long = FibonacciCalculator(Num)

            Console.WriteLine("{0}. Durchlauf: ", i)

            Console.WriteLine("Die {0}. Fibonacci-Zahl lautet: {1}{4}Der Vorgang hat {2} " & _
                "Rekursionen/Iterationen gebraucht{4}Der Vorgang hat {3}ms gedauert{4}", Num, _
                Res, FibonacciCalculator.Count, FibonacciCalculator.Runtime, _
                Environment.NewLine)

        Next i

        Console.ReadKey()

    End Sub

End Module

' ------------------ Ende Datei Module1.vb  ------------------
' ----------- Ende Projektdatei Memoization.vbproj -----------
' ------------ Ende Projektgruppe Memoization.sln ------------

	

Diskussion  

Diese Funktion ermöglicht es, Fragen, die die Veröffentlichung des Tipps betreffen, zu klären, oder Anregungen und Verbesserungsvorschläge einzubringen. Nach der Veröffentlichung des Tipps werden diese Beiträge nicht weiter verlinkt. Allgemeine Fragen zum Inhalt sollten daher hier nicht geklärt werden.
Folgende Diskussionen existieren bereits

Um eine Diskussion eröffnen zu können, müssen sie angemeldet sein.