VB.NET-Tipp 0115: Unendliche Sequenzen und Generatorfunktionen
von Dario
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: | Framework-Version(en): .NET Framework 3.5 | .NET-Version(en): Visual Basic 2008 | Download: |
' 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.