Eigene Queue-Klasse

  • VB.NET

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von ErfinderDesRades.

    Eigene Queue-Klasse

    Hallo zusammen =)

    Zunächst einmal meine Ausgangsposition: Ich habe vor eine eigene Queue zu schreiben/verändern/überschreiben, da die Queue-Klasse an sich mir nicht die gewünschten Funktionen bietet.
    Meine Anforderungen:
    - OnChanged-Event
    - Priorisierte Auflistung

    Meine Frage an Euch ist nun, wie ich dies am besten umsetze. Ich habe einige Vorstellungen, möchte jedoch gerne Eure Meinung dazu wissen.

    1) Von Collection.Queue erben und das OnChanged-Event hinzufügen.
    Problemstellung: Die Auflistung wird mit Klassen gespeist, welche mit einem Rang versehen sind z.B (1,2,3). Die Add-Funktion fügt die Klasse jedoch am Ende an, also bräuchte ich eine eigene Insert-Funktion, damit diese z.B. die Klasse mit "Rang 1" zwischen den letzten von "Rang 1" und dem ersten mit "Rang 2" eingefügt wird.

    2) In jede Klasse IComparable implementieren und die Auflistung nach jedem hinzufügen sortieren.

    Ich bedanke mich schon mal im Voraus.
    Ich habe so eine Queue mal geschrieben (habe dafür einen Code gefunden und den vereinfacht). Genutzt habe ich sie am Ende nicht, weil ich es doch anders gelöst habe.

    VB.NET-Quellcode

    1. Public Class PriorityQueue(Of T)
    2. Private Values As New List(Of T)() 'habe jetzt beides auf Private geändert, Public war falsch
    3. Private Priorities As New List(Of Integer)()
    4. Public ReadOnly Property NumItems() As Integer
    5. Get
    6. Return Values.Count
    7. End Get
    8. End Property
    9. ' Add an item to the queue.
    10. Public Sub Enqueue(ByVal new_value As T, ByVal _
    11. new_priority As Integer)
    12. Values.Add(new_value)
    13. Priorities.Add(new_priority)
    14. End Sub
    15. ' Remove the item with the largest priority from the
    16. ' queue.
    17. Public Sub Dequeue(ByRef top_value As T, ByRef _
    18. top_priority As Integer)
    19. top_priority = Priorities.Max()
    20. Dim best_index = Priorities.IndexOf(top_priority)
    21. ' Return the corresponding item.
    22. top_value = Values(best_index)
    23. ' Remove the item from the lists.
    24. Values.RemoveAt(best_index)
    25. Priorities.RemoveAt(best_index)
    26. End Sub
    27. Public Sub Dequeue(ByRef top_value As T)
    28. Dim top_priority = Priorities.Max()
    29. Dim best_index = Priorities.IndexOf(top_priority)
    30. ' Return the corresponding item.
    31. top_value = Values(best_index)
    32. ' Remove the item from the lists.
    33. Values.RemoveAt(best_index)
    34. Priorities.RemoveAt(best_index)
    35. End Sub
    36. End Class


    OnChanged-Event kannst du dir bei Enqueue und Dequeue selbst hinzufügen...

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „WhitePage“ ()

    Willkommen im Forum. :thumbup:

    Mojo schrieb:

    welche mit einem Rang versehen sind z.B (1,2,3)
    Da brauchst Du 3 Standard-Queues. Feddich.
    Die kannst Du natürlich in eine gemeinsame Klasse packen, um Deine Zusatzfunktionalität zu implementieren.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hi
    @WhitePage
    Das ist ein ziemlich unperformantes Stück Code.

    Da ist die Überlegung, wie man das am besten strukturiert. Ich würde eine Liste mit den Prioritäten anlegen und zu jeder Priorität eine Queue.
    Die Liste würde ich als Liste wählen.
    Ist die Priorität eines abzulegenden Elements höher, als die des letzten Elements der Liste, so wird eine neue Queue eingereiht (kann man als Structure modellieren mit Priorität und Queue) und dort das Element hinzugefügt. Ansonsten wird in der Liste über eine binäre Suche das der Priorität entsprechende Element gesucht.
    Beim Dequeue wird einfach das letzte Element der Prioritätenliste gewählt und dort wiederum das letzte Element entfernt (also list(list.Count - 1)). Ist die Liste anschließend leer, so wird das Element aus der Prioritätenliste gestrichen.

    Gruß
    ~blaze~
    Ich hatte auch noch gerade eine Idee, ob sie performant ist, kann ich leider nicht beurteilen.

    VB.NET-Quellcode

    1. Public Class TestCollection
    2. Inherits CollectionBase
    3. Private Rang1 As Integer
    4. Private Rang2 As Integer
    5. Private Rang3 As Integer
    6. Sub testinsert(ByVal index As Integer, ByVal obj As Test)
    7. Select Case obj.Rang
    8. Case 1
    9. MyBase.List.Insert(Rang1 + 1, obj)
    10. Case 2
    11. MyBase.List.Insert(Rang2 + 1, obj)
    12. Case 3
    13. MyBase.List.Insert(Rang3 + 1, obj)
    14. End Select
    15. End Sub
    16. End Class
    17. Public Class Test
    18. Public Rang As Integer
    19. End Class

    Müsste beim hinzufügen neuer Klassen natürlich die jeweiligen Zähler hochzählen lassen.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Mojo“ ()

    Mojo schrieb:

    natürlich die jeweiligen Zähler hochzählen lassen.
    Pack Dir 3 List(Of T) oder 3 Queues in diese Klasse und feddich. :rolleyes:
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    Hab's jetzt mal nicht getestet, aber so sähe mein Ansatz aus:
    Spoiler anzeigen

    VB.NET-Quellcode

    1. Public MustInherit Class PrioritizedQueue(Of T)
    2. Private _priorityList As List(Of KeyValuePair(Of Integer, Queue(Of T)))
    3. Protected MustOverride Function GetPriority(value As T) As Integer
    4. Public Sub New()
    5. _priorityList = New List(Of KeyValuePair(Of Integer, Queue(Of T)))()
    6. End Sub
    7. Public Function Dequeue() As T
    8. If IsEmpty Then Throw New InvalidOperationException("Queue is empty.")
    9. Dim q As Queue(Of T) = _priorityList(_priorityList.Count - 1).Value
    10. Dim v As T = q.Dequeue()
    11. If q.Count = 0 Then
    12. _priorityList.RemoveAt(_priorityList.Count - 1)
    13. End If
    14. Return v
    15. End Function
    16. Public Sub Enqueue(value As T)
    17. Dim prio As Integer = GetPriority(value)
    18. Dim q As KeyValuePair(Of Integer, Queue(Of T)) = _priorityList(_priorityList.Count - 1)
    19. If q.Key <> prio Then
    20. Dim i As Integer = _priorityList.BinarySearch(New KeyValuePair(Of Integer, Queue(Of T))(prio, Nothing), PriorityComparer.Instance)
    21. If i < 0 Then
    22. q = New KeyValuePair(Of Integer, Queue(Of T))(prio, New Queue(Of T)())
    23. _priorityList.Insert(Not i, q)
    24. Else
    25. q = _priorityList(i)
    26. End If
    27. End If
    28. q.Value.Enqueue(value)
    29. End Sub
    30. Public Sub Clear()
    31. _priorityList.Clear()
    32. End Sub
    33. Public ReadOnly Property IsEmpty As Boolean
    34. Get
    35. Return _priorityList.Count = 0
    36. End Get
    37. End Property
    38. Public Shared Function FromDelegate(priorityEvaluator As Func(Of T, Integer)) As PrioritizedQueue(Of T)
    39. If priorityEvaluator Is Nothing Then Throw New ArgumentNullException("priorityEvaluator")
    40. Return New DelegatePrioritizedQueue(priorityEvaluator)
    41. End Function
    42. Private NotInheritable Class PriorityComparer
    43. Implements IComparer(Of KeyValuePair(Of Integer, Queue(Of T)))
    44. Public Shared ReadOnly Instance As New PriorityComparer()
    45. Public Function Compare(
    46. x As KeyValuePair(Of Integer, Queue(Of T)),
    47. y As KeyValuePair(Of Integer, Queue(Of T))) As Integer Implements IComparer(Of KeyValuePair(Of Integer, Queue(Of T))).Compare
    48. Return x.Key.CompareTo(y.Key)
    49. End Function
    50. End Class
    51. Private NotInheritable Class DelegatePrioritizedQueue
    52. Inherits PrioritizedQueue(Of T)
    53. Private _eval As Func(Of T, Integer)
    54. Public Sub New(eval As Func(Of T, Integer))
    55. If eval Is Nothing Then Throw New ArgumentNullException("eval")
    56. _eval = eval
    57. End Sub
    58. Protected Overrides Function GetPriority(value As T) As Integer
    59. Return _eval(value)
    60. End Function
    61. End Class
    62. End Class


    Da ist die Verwendung auch relativ einfach: Einfach nur PrioritizedQueue(Of DeinTyp).FromDelegate(Function(v) v.priorität) angeben, dann sollte sich die Queue automatisch entsprechend organisieren.

    Edit: Fehlenden Teil des Codes hinzugefügt...

    Gruß
    ~blaze~
    Ich denk, der TE müsste sich erstmal klar ausdrücken, denn "PrioritätenListe" ist unvereinbar mit "Queue".

    Klassische und schnellste Form der Prioritätenliste ist übrigens der Heap - performante sortierte Datenstruktur.
    Leider habichs nicht gebacken gekriegt, meinem Heap ein effizientes Rebalancing einzubauen im Falle dass sich eine Priorität ändert.

    @TE: wofür brauchst du das?
    Weil ansonsten kannst du dir auch eine ObservableCollection(Of T) sortieren. Eine binäre Suche darin ist extrem schnell - ebenso die Entnahme des letzten(!) Elementes.
    Nur bei tausenden von elementen wird das Einfügen vergleichsweise unperformant (aber immer noch 100fach schneller, als alles, was auch ein versierter Coder selbst entwickeln könnte).