Postępowałem zgodnie ze wskazówkami podanymi w this question (odpowiedź Jason) w celu napisania mojej PriorityQueue<T>
przy użyciu SortedList
. Rozumiem, że pole count
w tej klasie służy do zapewnienia unikalnych priorytetów i zachowania porządku kolejkowania pośród tego samego priorytetu.Zmiana priorytetu w niestandardowej kolejce priorytetowej
Jednakże, gdy count
osiągnie swoją maksymalną wartość, a ja sumuję 1 do niego, ta ostatnia rozpocznie się ponownie od 0, więc priorytet kolejnych elementów będzie wyższy niż priorytet poprzednich pozycji. Stosując to podejście mogłem potrzeba sposobu, aby „bezpiecznie” reset licznika count
... W rzeczywistości, załóżmy mieć następujący stan kolejki (w priorytecie Format | liczyć | przedmiot):
0 | 123 | A
0 | 345 | B
1 | 234 | C
2 | 200 | D
Teraz załóżmy, że limit licznika został osiągnięty, więc muszę zresetować go do 0: w konsekwencji, następny wstawiony element będzie miał licznik 0: na przykład, jeśli wstawię element z priorytetem równym 1, to zostanie błędnie wstawiony przed 1 | 234 | D
0 | 123 | A
0 | 345 | B
1 | 000 | nowy element
1 | 234 | C
2 | 200 | D
Problem priorytetu może być rozwiązany poprzez wdrożenie sterty: Stworzyłem klasę Heap
, następnie użyłem Heap<KeyValuePair<TPriority, TElement>
i zwyczaj PriorityComparer
w celu uporządkowania elementów przez TPriority
. Biorąc TPriority jako int
i TElement jako string
The PriorityComparer
jest następujący:
public class MyComparer : IComparer<KeyValuePair<int, string>>
{
public int Compare(KeyValuePair<int, string> x, KeyValuePair<int, string> y)
{
return x.Key.CompareTo(y.Key);
}
}
...
int capacity = 10;
Heap<KeyValuePair<int, string>> queue;
queue = new Heap<KeyValuePair<int, string>>(capacity, new PriorityComparer());
...
UPDATE W ten sposób (przy użyciu PriorityComparer
), udało mi się zaimplementować kolejkę priorytetową. Teraz chciałbym dodać wsparcie, aby zmodyfikować jego zachowanie w czasie wykonywania, tzn. Przełączyć z FIFO na sortowanie priorytetowe i na odwrót. Ponieważ moja realizacja priorytetu kolejki ma pole IComparer
, myślę, że to wystarczy dodać obiekt Comparer
edytować to pole, podobnie jak następuje:
public IComparer
{
set
{
this._comparer = value;
}
}
w międzyczasie pomyślałem, że wezmę innego podejścia: zamiast używać sterówki binarnej do zarządzania priorytetami, mógłbym owijać różne kolejki (każda kolejka odnosi się do danego priorytetu) w następujący sposób.
public class PriorityQueue<T, int>
{
private Queue<T> _defaultQueue;
private bool _priority;
private SortedList<int, Queue<T>> _priorityQueues;
public PriorityQueue(int capacity)
{
this._defaultQueue = new Queue<T>(capacity);
this._priority = false;
this._priorityQueues = new SortedList<int, Queue<T>>(0);
}
public void PriorityEnable()
{
this._priority = true;
}
public void PriorityDisable()
{
this._priority = false;
}
public void Enqueue(T item)
{
if (this._priority)
{
// enqueue to one of the queues
// with associated priority
// ...
}
else this._defaultQueue.Enqueue(item);
}
public T Dequeue()
{
if (this._priority)
{
// dequeue from one of the queues
// with associated priority and
// return
// ...
}
return this._defaultQueue.Dequeue();
}
}
- Jak zarządzać przejście od FIFO Tryb do trybie priorytetu gdy wciąż istnieją elementy w domyślnej kolejce? Mogę skopiować je w kolejkach priorytetowych na podstawie priorytetu pozycji ... Inne lepsze rozwiązania?
- Jak zarządzać przejściem z trybu priorytetowego na Tryb FIFO? W tym przypadku miałbym kilka kolejek priorytetowych, które mogą zawierać elementy, ale nie muszą już nimi zarządzać zgodnie z priorytetem i nawet nie znają oryginalnej kolejności przyjazdu ...
- Jak zarządzać przepustowością różnych kolejki?
- Co z wykonaniem powyższych dwóch rozwiązań? Który używa więcej pamięci?
Czy moja odpowiedź stanowi pomoc w rozwiązaniu problemu? – JeremyK