Bei einer generischen Liste (Namespace: System.Collections.Generic) stehen die Methoden "Contains" und "IndexOf" zur Verfügung, um zu prüfen, ob ein bestimmtes Element bereits in der Liste vorhanden ist. Ist für die Listen-Elemente die Schnittstelle "IComparable<T>" (und dementsprechend die Schnittstelle "IEquatable<T>") implementiert, kann die Liste nach dem Hinzufügen aller Elemente durch die "Sort"-Methode (ansteigend) sortiert werden. Danach steht die "BinarySearch"-Methode zur Verfügung, die bei der Suche in langen Listen wesentlich effizienter arbeitet (ab etwa 200 Einträgen), als "IndexOf" (O[log(n)] statt O[n]-Operation). Umfasst die Liste eine Länge von 1000 Elementen, ist die binäre Suche nach einem Element etwa 4x schneller als die lineare Suche, bei 500.000 Elementen ist die binäre Suche bereits mehr als 600x schneller. Die Binärsuch-Methode der generischen Liste erkennt NICHT, ob die Listen-Elemente tatsächlich sortiert worden sind und liefert gegebenenfalls unbrauchbare Resultate! Bei sortierten Listen, denen dynamisch Elemente hinzugefügt werden, ist es zweckmäßiger, die Elemente bereits bei der Zuweisung an der korrekten Sortier-Position einzufügen. Die "BinarySearch"-Methode unterstützt diese Operation: Die Klasse "sList" ist von der generischen Liste abgeleitet. Sie verwaltet die Elemente in ansteigend sortierter Reihenfolge unter Nutzung der "BinarySearch"-Methode. Die oben angegebenen Besonderheiten der "BinarySearch"-Methode sind bei der Implementierung berücksichtigt worden. Eine Überladung des Konstruktors übernimmt eine Auflistung von Items, die direkt in die neu erstellte "sList"-Instanz eingetragen und anschließend sortiert wird. Das ist der effizienteste Weg, um eine Instanz der "sList"-Klasse zu erstellen, die eine große Anzahl von Items enthält. Die "Add"- und die "Addrange"-Methode fügen Elemente in eine Instanz der "sList" ein. Dabei wird der Listenindex der Elemente durch die Implementierung der "IComparable"-Schnittstelle per "BinarySearch" ermittelt. Die"Contains"-Methode und die Überladungen der "IndexOf"-Methode verwenden "BinarySearch" für die schnelle Suche nach einem Element - ab einer Listen-Länge von 200 Elementen. Bei kurzen Listen ist die Verwendung der linearen Suche effizienter. "IndexOf" gibt den Index des ersten Vorkommens, "LastIndexOf" den Index des letzten Vorkommens eines Elements in der Liste zurück. Die Rückgabewerte dieser Methoden entsprechen auch bei binärer Suche denen der Basisklasse. Die "Frequency"-Methode gibt die Häufigkeit eines Elements in der Liste an. Fehlt das abgefragte Element in der Liste, wird 0 zurückgegeben. Zum Entfernen von Elementen werden die Überladungen der "Remove"-Methode der Basisklasse herangezogen. Methoden der generischen Liste, welche die Reihenfolge der Elemente ändern würden ("Insert", "Sort", "Reverse"), sind bei der "sList"-Klasse nicht implementiert ("Shadows"). Aufrufe dieser Methoden lösen jeweils die "Not Implemented"-Ausnahme aus. Bei der Erstellung von Klassen, deren Instanzen als Elemente einer "sList"-Klasse fungieren, sollte darauf geachtet werden, daß die in der "CompareTo"-Methode verwendeten Eigenschaften nur im Klassen-Konstruktor zugewiesen werden können, weil bei einer nachträglichen Änderung die Reihenfolge in der "sList" eventuell nicht mehr korrekt ist. Option Strict On Option Explicit On Option Infer Off Imports System.Collections.Generic ''' <summary>Verwaltung einer sortierten Liste unter Verwendung von BinarySearch</summary> ''' <typeparam name="T">Datentyp der Elemente (IEquatable, IComparable muß implementiert sein)</typeparam> Public Class SList(Of T As {IEquatable(Of T), IComparable(Of T)}) Inherits List(Of T) ''' <summary>minimale Listenlänge, ab der die binäre Suche eingesetzt wird</summary> Private Const critlength As Integer = 200 #Region "Konstruktoren" ''' <summary>Erstellt eine neue Instanz, die über die Standardkapazität verfügt</summary> Public Sub New() MyBase.new() End Sub ''' <summary>Erstellt eine neue Instanz mit vorgegebener Anfangs-Kapazität</summary> ''' <param name="capacity">anfängliche Anzahl von Elementen</param> Public Sub New(ByVal capacity As Integer) MyBase.new(capacity) End Sub ''' <summary>Erstellt eine neue Instanz, die die Elemente der Auflistung sortiert enthält</summary> ''' <param name="collection">einzutragende Elemente der Auflistung</param> Public Sub New(collection As IEnumerable(Of T)) MyBase.New(collection) MyBase.Sort() End Sub #End Region #Region "Add-/Addrange" ''' <summary>Fügt ein Objekt in die sortierte Liste ein</summary> ''' <param name="item">einzufügendes Objekt</param> Public Shadows Sub Add(ByVal item As T) ' Einfügung (oder Anhängen) des Items durch Nutzung von "Binarysearch" MyBase.Insert(FindListIndex(item), item) End Sub ''' <summary>Fügt eine Auflistung von Objekten in die sortierte Liste ein</summary> ''' <param name="items">Auflistung der einzufügenden Objekte</param> Public Shadows Sub AddRange(ByVal items As IEnumerable(Of T)) If items Is Nothing Then Exit Sub For Each item As T In items ' Einfügung durch Add-Methode (BinarySearch) Me.Add(item) Next item End Sub ''' <summary>Ruft das Element am angegebenen Index ab</summary> ''' <param name="Index">Der nullbasierte Index des Elements, das abgerufen werden soll</param> Default Public Shadows ReadOnly Property Item(ByVal Index As Integer) As T Get Return MyBase.Item(Index) End Get End Property #End Region #Region "Contains, Indexof, LastIndexOf" ''' <summary>Bestimmt, ob sich ein Element in der sortierten Liste befindet?</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <returns>Objekt in der sortierten Liste vorhanden?</returns> Public Shadows Function Contains(ByVal item As T) As Boolean If MyBase.Count < critlength Then Return MyBase.Contains(item) Else Return MyBase.BinarySearch(item) >= 0 End If End Function ''' <summary>Gibt den niedrigsten Index eines Elements in der ''' sortierten Liste zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <returns>niedrigster Index des gesuchten Objekts in der Liste (oder -1)</returns> Public Shadows Function IndexOf(ByVal item As T) As Integer If MyBase.Count < critlength Then Return MyBase.IndexOf(item) Else Dim bs_indx As Integer = MyBase.BinarySearch(item) If bs_indx < 0 Then Return -1 Return FirstItemIndex(bs_indx) End If End Function ''' <summary>Gibt den niedrigsten Index eines Elements in einem Bereich ''' der sortierten Liste zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <param name="index">nullbasierter Startindex des zu durchsuchenden Bereichs</param> ''' <returns>niedrigster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns> Public Shadows Function IndexOf(ByVal item As T, ByVal index As Integer) As Integer If MyBase.Count < critlength Then Return MyBase.IndexOf(item, index) Else Dim count As Integer = MyBase.Count - index Dim bs_indx As Integer = MyBase.BinarySearch(index, count, item, Nothing) If bs_indx < 0 Then Return -1 Return FirstItemIndex(bs_indx, index) End If End Function ''' <summary>Gibt den niedrigsten Index eines Elements in einem Bereich der sortierten ''' Liste zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <param name="index">nullbasierter Startindex des zu durchsuchenden Bereichs</param> ''' <param name="count">Länge des zu durchsuchenden Bereichs der Liste</param> ''' <returns>niedrigster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns> Public Shadows Function IndexOf(ByVal item As T, ByVal index As Integer, _ count As Integer) As Integer If MyBase.Count < critlength Then Return MyBase.IndexOf(item, index, count) Else Dim bs_indx As Integer = MyBase.BinarySearch(index, count, item, Nothing) If bs_indx < 0 Then Return -1 Return FirstItemIndex(bs_indx, index) End If End Function ''' <summary>Gibt den höchsten Index eines Elements in der sortierten Liste ''' zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <returns>höchster Index des gesuchten Objekts in der Liste (oder -1)</returns> Public Shadows Function LastIndexOf(ByVal Item As T) As Integer If MyBase.Count < critlength Then Return MyBase.LastIndexOf(Item) Else Dim bs_indx As Integer = MyBase.BinarySearch(Item) If bs_indx < 0 Then Return -1 Return LastItemIndex(bs_indx) End If End Function ''' <summary>Gibt den höchsten Index eines Elements in einem Bereich der ''' sortierten Liste zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <param name="index">nullbasierter Startindex des zu durchsuchenden ''' Bereichs (Rückwärtssuche)</param> ''' <returns>höchster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns> Public Shadows Function LastIndexOf(ByVal item As T, ByVal index As Integer) As Integer If MyBase.Count < critlength Then Return MyBase.LastIndexOf(item, index) Else Dim count As Integer = MyBase.Count - index Dim bs_indx As Integer = MyBase.BinarySearch(0, index + 1, item, Nothing) If bs_indx < 0 Then Return -1 Return LastItemIndex(bs_indx, index) End If End Function ''' <summary>Gibt den höchsten Index eines Elements in einem Bereich der ''' sortierten Liste zurück (oder -1)</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <param name="index">nullbasierter Startindex des zu durchsuchenden ''' Bereichs (Rückwärtssuche)</param> ''' <param name="count">Länge des zu durchsuchenden Bereichs der Liste</param> ''' <returns>höchster Index des gesuchten Objekts im Bereich der Liste (oder -1)</returns> Public Shadows Function LastIndexOf(ByVal item As T, ByVal index As Integer, _ count As Integer) As Integer If MyBase.Count < critlength Then Return MyBase.LastIndexOf(item, index, count) Else Dim bs_indx As Integer = MyBase.BinarySearch(index - count + 1, count, item, Nothing) If bs_indx < 0 Then Return -1 Return LastItemIndex(bs_indx, index) End If End Function ''' <summary>Bestimmung der Häufigkeit eines Items in der sortierten Liste</summary> ''' <param name="item">das zu suchende Objekt</param> ''' <returns>Häufigkeit des Objekts (ggf. 0)</returns> Public Function Frequency(ByVal item As T) As Integer Dim firstindex As Integer = IndexOf(item) If firstindex = -1 Then Return 0 Dim lastindex As Integer = LastItemIndex(firstindex) Return lastindex - firstindex + 1 End Function #End Region #Region "Helpers" Private Function FindListIndex(ByVal item As T) As Integer ' binäre Suche nach einem Listen-Index zu einem Item Dim index As Integer = MyBase.BinarySearch(item) If index < 0 Then ' ersetzt die bitweise Komplement-Operation index = Math.Abs(index) - 1 End If Return index End Function Private Function FirstItemIndex(ByVal index As Integer, Optional ByVal limitindex As Integer = 0) As Integer ' Bestimmung des niedrigsten Listenindex zu einem Item (ab Index bis Limitindex) ' Lineare Suche / Abschnitt gleicher Items (CompareTo=0) Dim item As T = MyBase.Item(index) Do index -= 1 Loop While index >= limitindex AndAlso MyBase.Item(index).CompareTo(item) = 0 Return index + 1 End Function Private Function LastItemIndex(ByVal index As Integer, _ Optional ByVal limitindex As Integer = -1) As Integer ' Bestimmung des höchsten Listenindex zu einem Item (ab Index bis Limitindex) ' Lineare Suche / Abschnitt gleicher Items (CompareTo=0) Dim item As T = MyBase.Item(index) If limitindex = -1 Then limitindex = Me.Count - 1 Do index += 1 Loop While index <= limitindex AndAlso MyBase.Item(index).CompareTo(item) = 0 Return index - 1 End Function #End Region #Region "Nicht implementiert" ''' <summary>nicht implementiert</summary> Public Shadows Sub Insert(ByVal index As Integer, ByVal element As T) Throw New NotImplementedException("Insert not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub InsertRange(ByVal index As Integer, ByVal items As IEnumerable(Of T)) Throw New NotImplementedException("InsertRange not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub Sort() Throw New NotImplementedException("Sort not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub Sort(comparer As IComparer(Of T)) Throw New NotImplementedException("SortByComparer not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub Sort(comparison As System.Comparison(Of T)) Throw New NotImplementedException("SortByComparison not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub Sort(ByVal index As Integer, ByVal count As Integer, _ ByVal comparer As IComparer(Of T)) Throw New NotImplementedException("SortByComparer not implemented") End Sub ''' <summary>nicht implementiert</summary> Public Shadows Sub Reverse() Throw New NotImplementedException("Reverse not implemented") End Sub #End Region End Class Dieser Tipp wurde bereits 8.044 mal aufgerufen. Voriger Tipp | Zufälliger Tipp | Nächster Tipp
Anzeige
Diesen und auch alle anderen Tipps & Tricks finden Sie auch auf unserer aktuellen vb@rchiv Vol.6 Ein absolutes Muss - Geballtes Wissen aus mehr als 8 Jahren vb@rchiv! - nahezu alle Tipps & Tricks und Workshops mit Beispielprojekten - Symbol-Galerie mit mehr als 3.200 Icons im modernen Look Weitere Infos - 4 Entwickler-Vollversionen (u.a. sevFTP für .NET), Online-Update-Funktion u.v.m. |
Neu! sevDTA 3.0 Pro SEPA mit Kontonummernprüfung Erstellen von SEPA-Dateien mit integriertem BIC-Verzeichnis und Konto- nummern-Prüfverfahren, so dass ungültige Bankdaten bereits im Vorfeld ermittelt werden können. Tipp des Monats April 2024 Skyfloy Chart von Microsoft und dazu noch gratis Tutorial für Microsoft Chart Controls für Microsoft .NET Framework 3.5 Access-Tools Vol.1 Über 400 MByte Inhalt Mehr als 250 Access-Beispiele, 25 Add-Ins und ActiveX-Komponenten, 16 VB-Projekt inkl. Source, mehr als 320 Tipps & Tricks für Access und VB |
||||||||||||||||
Microsoft, Windows und Visual Basic sind entweder eingetragene Marken oder Marken der Microsoft Corporation in den USA und/oder anderen Ländern. Weitere auf dieser Homepage aufgeführten Produkt- und Firmennamen können geschützte Marken ihrer jeweiligen Inhaber sein. |