Die Community zu .NET und Classic VB.
Menü

VB.NET-Tipp 0115: Unendliche Sequenzen und Generatorfunktionen

 von 

Beschreibung

Die IEnumerable-Schnittstelle ist auch deshalb eine sehr interessante Technik, da der Enumerator bei jedem Iterationsschritt sukzessive weiterberechnet wird. Dadurch ist man nicht auf abgeschlossene Objekte wie zum Beispiel Arrays oder Listen beschränkt, sondern kann auch unendliche Sequenzen oder Mengen repräsentieren, die nur bei Bedarf berechnet werden (Lazy evaluation). Beispiele wären alle natürlichen Zahlen, Quadratzahlen oder die Fibonacci-Folge. Die meisten IEnumerable-Funktionen, auch LINQ, unterscheiden dabei nicht zwischen endlichen und unendlichen Sequenzen, weshalb man sehr intuitiv mit ihnen arbeiten kann.

Das Hauptproblem ist allerdings solche Folgen zu erstellen. Denn Visual Basic verfügt, anders als C# oder funktionale Sprachen, nicht über eine Generatorensyntax per yield return. Dieser Tipp zeigt eine Möglichkeit dennoch solche Sequenzen gut formulieren zu können.

Mithilfe einer Generate-Funktion kann von einem Anfangswert ausgehend die Sequenz ähnlich einer Folge in der Mathematik formuliert und berechnet werden. Dabei wird eine Funktion verwendet, die aus einem Element das nächste berechnet. Die Funktion ist generisch aufgebaut, weshalb das ganze Konzept sehr flexibel ist. Durch Implementierung einer Tupel-Klasse oder mit anonymen Typen lässt sich der Algorithmus auf fast jede Problemstellung zurechtschneiden. Durch die IEnumerable-Schnittstelle ist die entstehende Folge voll Linq-kompatibel.

Der Tipp beinhaltet zudem noch weitere Verkürzungen und nützliche Funktionen zum Umgang mit Sequenzen.

Schwierigkeitsgrad:

Schwierigkeitsgrad 2

Framework-Version(en):

.NET Framework 3.5

.NET-Version(en):

Visual Basic 2008

Download:

Download des Beispielprojektes [9,38 KB]

' Dieser Quellcode 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!

' Projektversion:   Visual Studio 2008
' Option Strict:    An
' Option Explicit:  An
' Option Infer:     An
'
' Referenzen: 
'  - System
'  - System.Data
'  - System.Deployment
'  - System.Xml
'  - System.Core
'  - System.Xml.Linq
'  - System.Data.DataSetExtensions
'
' Imports: 
'  - Microsoft.VisualBasic
'  - System
'  - System.Collections
'  - System.Collections.Generic
'  - System.Data
'  - System.Diagnostics
'  - System.Linq
'  - System.Xml.Linq
'

' ##############################################################################
' ################################ Module1.vb ##################################
' ##############################################################################
Module Module1
    Sub Main()
        ' Natürliche Zahlen - Die nächste Zahl ist die aktuelle plus eins
        Dim Naturals = 1.Generate(Function(n) n + 1)

        ' Quadratzahlen - Hier wird Linq verwendet
        Dim Squares = From n In Naturals Select n ^ 2

        ' Fibonacci-Zahlen - Jede Zahl ist die Summe ihrer beiden Vorgänger.
        '  Hierzu müssen die Vorgänger (a und b) zwischengespeichert werden, in 
        '  diesem Falle geschieht dies in einem anonymen Typen. Das 
        '  letztendliche Ergebnis ist wiederum nur eine Zahl, die aus den 
        '  Paaren extrahiert wird
        Dim Fibonacci = (New With {.a = 1, .b = 1}).Generate( _
            Successor:=Function(p) New With {.a = p.b, .b = p.a + p.b}, _
            Selector:=Function(p) p.a)

        ' Dreieckszahlen - Jede Zahl ist die Summe aller Zahlen bis zu dieser
        '  Das Vorgehen ist hier ähnlich zu dem bei den Fibonacci-Zahlen, hier 
        '  jedoch in verkürzter Syntax
        Dim TriangleNumbers = (New With {.Sum = 1, .i = 1}).Generate( _
            Function(p) New With {.Sum = p.Sum + p.i, .i = p.i + 1}, _
                Function(p) p.Sum)

        ' Ausgeben
        Console.WriteLine("Natürliche Zahlen:   {0}", Naturals.Show(8))
        Console.WriteLine("Quadratzahlen:       {0}", Squares.Show(8))
        Console.WriteLine("Fibonaccizahlen:     {0}", Fibonacci.Show(8))
        Console.WriteLine("Dreieckszahlen:      {0}", TriangleNumbers.Show(8))

        Console.ReadKey()
    End Sub

End Module

' ##############################################################################
' ############################### Sequences.vb #################################
' ##############################################################################
Option Strict On

Imports System.Runtime.CompilerServices

<DebuggerStepThrough()> _
Public Module Sequences

    ''' <summary>
    ''' Unendliche Folge generieren
    ''' </summary>
    ''' <typeparam name="T">Typ der Sequenz</typeparam>
    ''' <param name="Init">Startwert der Sequenz</param>
    ''' <param name="Successor">Berechnungsvorschrift für den Nachfolger</param>
    ''' <returns>Generierte Sequenz</returns>
    ''' <remarks>Elemente werden nur auf Bedarf berechnet</remarks>
    <Extension()> _
    Public Function Generate(Of T)(ByVal Init As T, _
        ByVal Successor As Func(Of T, T)) As IEnumerable(Of T)

        Return New GeneratorEnumerable(Of T)(Init, Function(x) Successor(x))
    End Function

    ''' <summary>
    ''' Unendliche Folge generieren
    ''' </summary>
    ''' <typeparam name="TIn">Eingabetyp</typeparam>
    ''' <typeparam name="TOut">Ausgabetyp</typeparam>
    ''' <param name="Init">Startwert der Sequenz</param>
    ''' <param name="Successor">
    '''  Berechnungsvorschrift für den Nachfolger
    ''' </param>
    ''' <param name="Selector">
    '''  Ausgabetransformation für jedes Folgenelement
    ''' </param>
    ''' <returns>Generierte Sequenz</returns>
    ''' <remarks>Elemente werden nur auf Bedarf berechnet</remarks>
    <Extension()> _
    Public Function Generate(Of TIn, TOut)(ByVal Init As TIn, _
        ByVal Successor As Func(Of TIn, TIn), _
        ByVal Selector As Func(Of TIn, TOut)) As IEnumerable(Of TOut)

        Return (New GeneratorEnumerable(Of TIn)(Init, _
            Function(x) Successor(x))).Select(Selector)
    End Function

    ''' <summary>
    ''' Vorschau einer Folge berechnen
    ''' </summary>
    ''' <typeparam name="T">Typ der Sequenz</typeparam>
    ''' <param name="Sequence">Die zu verarbeitende Folge</param>
    ''' <param name="Length">Optionale Länge der Vorschau</param>
    ''' <param name="Delimiter">Optionales Trennelement</param>
    ''' <returns>Stringrepräsentation der Sequenz</returns>
    <Extension()> _
    Public Function Show(Of T)(ByVal Sequence As IEnumerable(Of T), _
        Optional ByVal Length As Integer = 4, _
        Optional ByVal Delimiter As String = ", ") As String

        Return "[" & String.Join(Delimiter, Sequence.Take(Length).Select( _
            Function(x) x.ToString()).ToArray) & Delimiter & "...]"
    End Function

    ''' <summary>
    ''' Funktion für jedes Element einer Folge ausführen
    ''' </summary>
    ''' <typeparam name="T">Typ der Sequenz</typeparam>
    ''' <param name="Sequence">Die zu verarbeitende Folge</param>
    ''' <param name="Function">Die auszuführende Funktion</param>
    <Extension()> _
    Public Sub ForEach(Of T)(ByVal Sequence As IEnumerable(Of T), _
        ByVal [Function] As Action(Of T))

        For Each It In Sequence
            Call [Function](It)
        Next
    End Sub

    ' Generatorklasse - Diese ist im Programm nicht sichtbar, sondern wird
    '  einzig und allein durch IEnumerable(Of T) dargestellt. Dadurch ist sie 
    '  voll Linq-kompatibel
    <DebuggerStepThrough()> _
    Private Class GeneratorEnumerable(Of T) : Implements IEnumerable(Of T)

        ' Funktion zum Berechnen des nächsten Elementes
        Public Delegate Function Generator(ByVal Arg As T) As T

        ' Interner Iterator, der die Folge Schritt für Schritt berechnet
        <DebuggerStepThrough()> _
        Private Class Enumerator : Implements IEnumerator(Of T)

            Private m_Out As T
            Private m_Current As T

            Private ReadOnly m_Init As T
            Private ReadOnly m_Generator As Generator

            Public Sub New(ByVal Init As T, ByVal Generator As Generator)
                m_Init = Init
                m_Current = Init
                m_Generator = Generator
            End Sub

            Public ReadOnly Property Current() As T _
                Implements System.Collections.Generic.IEnumerator(Of T).Current

                Get
                    Return m_Out
                End Get
            End Property

            Public ReadOnly Property Current1() As Object _
                Implements System.Collections.IEnumerator.Current

                Get
                    Return Current
                End Get
            End Property

            Public Function MoveNext() As Boolean _
                Implements System.Collections.IEnumerator.MoveNext

                m_Out = m_Current
                m_Current = m_Generator(m_Current)

                Return True
            End Function

            Public Sub Reset() Implements System.Collections.IEnumerator.Reset
                m_Current = m_Init
            End Sub

            Public Sub Dispose() Implements IDisposable.Dispose
                GC.SuppressFinalize(Me)
            End Sub

        End Class

        Private ReadOnly m_Init As T
        Private ReadOnly m_Generator As Generator

        Public Sub New(ByVal Init As T, ByVal Generator As Generator)
            m_Init = Init
            m_Generator = Generator
        End Sub

        Public Function GetEnumerator() _
            As System.Collections.Generic.IEnumerator(Of T) _
            Implements _
                System.Collections.Generic.IEnumerable(Of T).GetEnumerator

            Return New Enumerator(m_Init, m_Generator)
        End Function

        Public Function GetEnumerator1() _
            As System.Collections.IEnumerator _
            Implements System.Collections.IEnumerable.GetEnumerator

            Return GetEnumerator()
        End Function
    End Class

End Module

Ihre Meinung  

Falls Sie Fragen zu diesem Artikel haben oder Ihre Erfahrung mit anderen Nutzern austauschen möchten, dann teilen Sie uns diese bitte in einem der unten vorhandenen Themen oder über einen neuen Beitrag mit. Hierzu können sie einfach einen Beitrag in einem zum Thema passenden Forum anlegen, welcher automatisch mit dieser Seite verknüpft wird.