File d’attente prioritaire dans .Net

Je recherche une implémentation .NET d’une queue prioritaire ou d’une structure de données de tas

Les files d’attente prioritaires sont des structures de données qui offrent plus de flexibilité que le simple sorting, car elles permettent à de nouveaux éléments d’entrer dans un système à des intervalles arbitraires. Il est beaucoup plus rentable d’insérer un nouveau travail dans une file d’attente prioritaire que de tout sortinger à chaque arrivée.

La queue de priorité de base prend en charge trois opérations principales:

  • Insérer (Q, x). Étant donné un élément x avec la clé k, insérez-le dans la queue prioritaire Q.
  • Find-Minimum (Q). Renvoie un pointeur sur l’élément dont la valeur de clé est inférieure à toute autre clé de la queue de priorité Q.
  • Supprimer-Minimum (Q). Supprimer l’élément de la queue prioritaire Q dont la clé est minimale

Sauf si je regarde au mauvais endroit, il n’y en a pas dans le cadre. Est-ce que quelqu’un est au courant d’un bon, ou devrais-je rouler le mien?

J’aime utiliser les classes OrderedBag et OrderedSet dans PowerCollections en tant que files d’attente prioritaires.

Vous pourriez aimer IntervalHeap de la bibliothèque C5 Generic Collection . Pour citer le guide de l’ utilisateur

La classe IntervalHeap implémente l’interface IPriorityQueue aide d’un IPriorityQueue d’intervalle stocké sous la forme d’un tableau de paires. Les opérations FindMin et FindMax, ainsi que le get-accessor de l’indexeur, prennent le temps O (1). Les opérations DeleteMin, DeleteMax, Add et Update et le set-accessor de l’indexeur prennent le temps O (log n). Contrairement à une queue prioritaire ordinaire, un segment d’intervalle offre des opérations minimales et maximales avec la même efficacité.

L’API est assez simple

 > var heap = new C5.IntervalHeap(); > heap.Add(10); > heap.Add(5); > heap.FindMin(); 5 

Installer à partir de Nuget https://www.nuget.org/packages/C5 ou GitHub https://github.com/sestoft/C5/

Voici ma tentative pour un tas .NET

 public abstract class Heap : IEnumerable { private const int InitialCapacity = 0; private const int GrowFactor = 2; private const int MinGrow = 1; private int _capacity = InitialCapacity; private T[] _heap = new T[InitialCapacity]; private int _tail = 0; public int Count { get { return _tail; } } public int Capacity { get { return _capacity; } } protected Comparer Comparer { get; private set; } protected abstract bool Dominates(T x, T y); protected Heap() : this(Comparer.Default) { } protected Heap(Comparer comparer) : this(Enumerable.Empty(), comparer) { } protected Heap(IEnumerable collection) : this(collection, Comparer.Default) { } protected Heap(IEnumerable collection, Comparer comparer) { if (collection == null) throw new ArgumentNullException("collection"); if (comparer == null) throw new ArgumentNullException("comparer"); Comparer = comparer; foreach (var item in collection) { if (Count == Capacity) Grow(); _heap[_tail++] = item; } for (int i = Parent(_tail - 1); i >= 0; i--) BubbleDown(i); } public void Add(T item) { if (Count == Capacity) Grow(); _heap[_tail++] = item; BubbleUp(_tail - 1); } private void BubbleUp(int i) { if (i == 0 || Dominates(_heap[Parent(i)], _heap[i])) return; //correct domination (or root) Swap(i, Parent(i)); BubbleUp(Parent(i)); } public T GetMin() { if (Count == 0) throw new InvalidOperationException("Heap is empty"); return _heap[0]; } public T ExtractDominating() { if (Count == 0) throw new InvalidOperationException("Heap is empty"); T ret = _heap[0]; _tail--; Swap(_tail, 0); BubbleDown(0); return ret; } private void BubbleDown(int i) { int dominatingNode = Dominating(i); if (dominatingNode == i) return; Swap(i, dominatingNode); BubbleDown(dominatingNode); } private int Dominating(int i) { int dominatingNode = i; dominatingNode = GetDominating(YoungChild(i), dominatingNode); dominatingNode = GetDominating(OldChild(i), dominatingNode); return dominatingNode; } private int GetDominating(int newNode, int dominatingNode) { if (newNode < _tail && !Dominates(_heap[dominatingNode], _heap[newNode])) return newNode; else return dominatingNode; } private void Swap(int i, int j) { T tmp = _heap[i]; _heap[i] = _heap[j]; _heap[j] = tmp; } private static int Parent(int i) { return (i + 1)/2 - 1; } private static int YoungChild(int i) { return (i + 1)*2 - 1; } private static int OldChild(int i) { return YoungChild(i) + 1; } private void Grow() { int newCapacity = _capacity*GrowFactor + MinGrow; var newHeap = new T[newCapacity]; Array.Copy(_heap, newHeap, _capacity); _heap = newHeap; _capacity = newCapacity; } public IEnumerator GetEnumerator() { return _heap.Take(Count).GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); } } public class MaxHeap : Heap { public MaxHeap() : this(Comparer.Default) { } public MaxHeap(Comparer comparer) : base(comparer) { } public MaxHeap(IEnumerable collection, Comparer comparer) : base(collection, comparer) { } public MaxHeap(IEnumerable collection) : base(collection) { } protected override bool Dominates(T x, T y) { return Comparer.Compare(x, y) >= 0; } } public class MinHeap : Heap { public MinHeap() : this(Comparer.Default) { } public MinHeap(Comparer comparer) : base(comparer) { } public MinHeap(IEnumerable collection) : base(collection) { } public MinHeap(IEnumerable collection, Comparer comparer) : base(collection, comparer) { } protected override bool Dominates(T x, T y) { return Comparer.Compare(x, y) <= 0; } } 

Quelques tests:

 [TestClass] public class HeapTests { [TestMethod] public void TestHeapBySorting() { var minHeap = new MinHeap(new[] {9, 8, 4, 1, 6, 2, 7, 4, 1, 2}); AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray()); minHeap = new MinHeap { 7, 5, 1, 6, 3, 2, 4, 1, 2, 1, 3, 4, 7 }; AssertHeapSort(minHeap, minHeap.OrderBy(i => i).ToArray()); var maxHeap = new MaxHeap(new[] {1, 5, 3, 2, 7, 56, 3, 1, 23, 5, 2, 1}); AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray()); maxHeap = new MaxHeap {2, 6, 1, 3, 56, 1, 4, 7, 8, 23, 4, 5, 7, 34, 1, 4}; AssertHeapSort(maxHeap, maxHeap.OrderBy(d => -d).ToArray()); } private static void AssertHeapSort(Heap heap, IEnumerable expected) { var sorted = new List(); while (heap.Count > 0) sorted.Add(heap.ExtractDominating()); Assert.IsTrue(sorted.SequenceEqual(expected)); } } 

Voici celui que je viens d’écrire, peut-être que ce n’est pas aussi optimisé (utilise juste un dictionnaire sortingé) mais simple à comprendre. vous pouvez insérer des objects de différents types, donc pas de files d’attente génériques.

 using System; using System.Diagnostics; using System.Collections; using System.Collections.Generic; namespace PrioQueue { public class PrioQueue { int total_size; SortedDictionary storage; public PrioQueue () { this.storage = new SortedDictionary (); this.total_size = 0; } public bool IsEmpty () { return (total_size == 0); } public object Dequeue () { if (IsEmpty ()) { throw new Exception ("Please check that priorityQueue is not empty before dequeing"); } else foreach (Queue q in storage.Values) { // we use a sorted dictionary if (q.Count > 0) { total_size--; return q.Dequeue (); } } Debug.Assert(false,"not supposed to reach here. problem with changing total_size"); return null; // not supposed to reach here. } // same as above, except for peek. public object Peek () { if (IsEmpty ()) throw new Exception ("Please check that priorityQueue is not empty before peeking"); else foreach (Queue q in storage.Values) { if (q.Count > 0) return q.Peek (); } Debug.Assert(false,"not supposed to reach here. problem with changing total_size"); return null; // not supposed to reach here. } public object Dequeue (int prio) { total_size--; return storage[prio].Dequeue (); } public void Enqueue (object item, int prio) { if (!storage.ContainsKey (prio)) { storage.Add (prio, new Queue ()); } storage[prio].Enqueue (item); total_size++; } } } 

J’en ai trouvé un par Julian Bucknall sur son blog ici – http://www.boyet.com/Articles/PriorityQueueCSharp3.html

Nous l’avons légèrement modifié pour que les éléments à faible priorité dans la queue finissent par «remonter» dans le temps, afin qu’ils ne souffrent pas de la famine.

Vous pouvez trouver utile cette implémentation: http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

il est générique et basé sur la structure de données de tas

 class PriorityQueue { IComparer comparer; T[] heap; public int Count { get; private set; } public PriorityQueue() : this(null) { } public PriorityQueue(int capacity) : this(capacity, null) { } public PriorityQueue(IComparer comparer) : this(16, comparer) { } public PriorityQueue(int capacity, IComparer comparer) { this.comparer = (comparer == null) ? Comparer.Default : comparer; this.heap = new T[capacity]; } public void push(T v) { if (Count >= heap.Length) Array.Resize(ref heap, Count * 2); heap[Count] = v; SiftUp(Count++); } public T pop() { var v = top(); heap[0] = heap[--Count]; if (Count > 0) SiftDown(0); return v; } public T top() { if (Count > 0) return heap[0]; throw new InvalidOperationException("优先队列为空"); } void SiftUp(int n) { var v = heap[n]; for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2) heap[n] = heap[n2]; heap[n] = v; } void SiftDown(int n) { var v = heap[n]; for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2) { if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++; if (comparer.Compare(v, heap[n2]) >= 0) break; heap[n] = heap[n2]; } heap[n] = v; } } 

facile.

Comme mentionné dans Microsoft Collections pour .NET , Microsoft a écrit (et partagé en ligne) 2 classes PriorityQueue internes au sein du .NET Framework. Leur code est disponible pour essayer.

EDIT: Comme @ mathusum-mut l’a commenté, il y a un bogue dans l’une des classes PriorityQueue internes de Microsoft (la communauté SO a bien sûr apporté des correctifs): Bug dans PriorityQueue interne de Microsoft?

Utilisez un traducteur Java vers C # sur l’implémentation Java (java.util.PriorityQueue) dans la structure Java Collections, ou utilisez plus intelligemment l’algorithme et le code central et twigz-le dans une classe C # qui respecte la structure C # Collections API pour les files d’attente, ou au moins les collections.

Voici l’autre implémentation de l’équipe NGenerics:

NGenerics PriorityQueue

AlgoKit

J’ai écrit une bibliothèque open source appelée AlgoKit , disponible via NuGet . Il contient:

  • Tas implicites d-ary (ArrayHeap),
  • Tas binomiaux ,
  • Pairage des tas .

Le code a été largement testé. Je vous recommande vraiment d’essayer.

Exemple

 var comparer = Comparer.Default; var heap = new PairingHeap(comparer); heap.Add(3, "your"); heap.Add(5, "of"); heap.Add(7, "disturbing."); heap.Add(2, "find"); heap.Add(1, "I"); heap.Add(6, "faith"); heap.Add(4, "lack"); while (!heap.IsEmpty) Console.WriteLine(heap.Pop().Value); 

Pourquoi ces trois tas?

Le choix optimal de l’implémentation dépend fortement des intrants, comme le montrent Larkin, Sen et Tarjan dans Une étude empirique de base sur les files d’attente prioritaires , arXiv: 1403.0252v1 [cs.DS] . Ils ont testé des tas d-ary implicites, des tas d’appariement, des tas de Fibonacci, des tas binomiaux, des tas de d-aires explicites, des tas de paires, des tas de tremblements de terre, des tas faibles et des tas de Fibonacci.

AlgoKit propose trois types de tas qui semblent être les plus efficaces parmi ceux testés.

Astuce sur le choix

Pour un nombre relativement petit d’éléments, vous seriez probablement intéressé par l’utilisation de tas implicites, en particulier les tas quaternaires (4-aire implicite). Dans le cas d’opérations sur des tailles de tas plus grandes, les structures amorties telles que les tas binomiaux et les tas d’appariement devraient donner de meilleurs résultats.

J’ai eu le même problème récemment et j’ai fini par créer un package NuGet pour cela.

Cela implémente une queue prioritaire standard basée sur le tas. Il possède également toutes les fonctionnalités habituelles des collections BCL: implémentation ICollection et IReadOnlyCollection , IComparer , possibilité de spécifier une capacité initiale et un DebuggerTypeProxy pour faciliter la DebuggerTypeProxy de la collection dans le débogueur

Il existe également une version Inline du package qui installe simplement un seul fichier .cs dans votre projet (utile si vous souhaitez éviter de prendre des dépendances visibles de l’extérieur).

Plus d’informations sont disponibles sur la page github .

Une implémentation Simple Max Heap.

https://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/MaxHeap.cs

 using System; using System.Collections.Generic; using System.Linq; namespace AlgorithmsMadeEasy { class MaxHeap { private static int capacity = 10; private int size = 0; int[] items = new int[capacity]; private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1; } private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2; } private int getParentIndex(int childIndex) { return (childIndex - 1) / 2; } private int getLeftChild(int parentIndex) { return this.items[getLeftChildIndex(parentIndex)]; } private int getRightChild(int parentIndex) { return this.items[getRightChildIndex(parentIndex)]; } private int getParent(int childIndex) { return this.items[getParentIndex(childIndex)]; } private bool hasLeftChild(int parentIndex) { return getLeftChildIndex(parentIndex) < size; } private bool hasRightChild(int parentIndex) { return getRightChildIndex(parentIndex) < size; } private bool hasParent(int childIndex) { return getLeftChildIndex(childIndex) > 0; } private void swap(int indexOne, int indexTwo) { int temp = this.items[indexOne]; this.items[indexOne] = this.items[indexTwo]; this.items[indexTwo] = temp; } private void hasEnoughCapacity() { if (this.size == capacity) { Array.Resize(ref this.items,capacity*2); capacity *= 2; } } public void Add(int item) { this.hasEnoughCapacity(); this.items[size] = item; this.size++; heapifyUp(); } public int Remove() { int item = this.items[0]; this.items[0] = this.items[size-1]; this.items[this.size - 1] = 0; size--; heapifyDown(); return item; } private void heapifyUp() { int index = this.size - 1; while (hasParent(index) && this.items[index] > getParent(index)) { swap(index, getParentIndex(index)); index = getParentIndex(index); } } private void heapifyDown() { int index = 0; while (hasLeftChild(index)) { int bigChildIndex = getLeftChildIndex(index); if (hasRightChild(index) && getLeftChild(index) < getRightChild(index)) { bigChildIndex = getRightChildIndex(index); } if (this.items[bigChildIndex] < this.items[index]) { break; } else { swap(bigChildIndex,index); index = bigChildIndex; } } } } } /* Calling Code: MaxHeap mh = new MaxHeap(); mh.Add(10); mh.Add(5); mh.Add(2); mh.Add(1); mh.Add(50); int maxVal = mh.Remove(); int newMaxVal = mh.Remove(); */ 

L’implémentation suivante d’un PriorityQueue utilise SortedSet de la bibliothèque System.

 using System; using System.Collections.Generic; namespace CDiggins { interface IPriorityQueue where K : IComparable { bool Empty { get; } void Enqueue(T x, K key); void Dequeue(); T Top { get; } } class PriorityQueue : IPriorityQueue where K : IComparable { SortedSet> set; class Comparer : IComparer> { public int Compare(Tuple x, Tuple y) { return x.Item2.CompareTo(y.Item2); } } PriorityQueue() { set = new SortedSet>(new Comparer()); } public bool Empty { get { return set.Count == 0; } } public void Enqueue(T x, K key) { set.Add(Tuple.Create(x, key)); } public void Dequeue() { set.Remove(set.Max); } public T Top { get { return set.Max.Item1; } } } }