30. august 2007 - 14:58Der er
11 kommentarer og 2 løsninger
Extract Min fra Dictionary
Hej eksperter
Kan man få fat i værdien med den mindste nøgle i en Dictionary.
Jeg har snakket med en gut, der påstår at det er muligt i STL i C++, men jeg kan ikke finde noget om det på nettet for Dictionary i C# og så er det vel ikke muligt?
Hvis man kan få den mindste nøgle ud, så vil man jo kunne bruge en Dictionary til Prioritetskø og jeg kunne forestille mig, at denne ville være ret hurtig. Jeg har kun brug for Insert, ExtractMin og UpdateKey.
.... kan få fat i den string, hvis key har den laveste værdi i vores Dictionary.
I ovenstående tilfælde er jeg altså interesseret i at slette entry (10,"string1") og få "string1" returneret som resultat på Extract Min.
På forhånd tak Allan
(Angående prioritetskøer, så kan jeg ikke dy mig for at spørge om der mon findes en ekspert derude som har en implementering af Fibonacci Heap liggende)
Ingen af eksemplerne er en rigtig prioritets-kø som jo bl.a. kan have flere elementer med samme prioritet (som så skal komme First-In-First-Out):
using System; using System.Collections.Generic;
namespace e794105 { class Program { static void Main(string[] args) { PriorityQueue<string> prioQueue = new PriorityQueue<string>(); prioQueue.Enqueue(10, "string1"); prioQueue.Enqueue(20, "string2"); prioQueue.Enqueue(30, "string3");
string førstePrioritet = prioQueue.Dequeue(); } }
class PriorityQueue<T> { // Denne værdi kan sættes som man ønsker. private const int maxPriority = 100;
private Queue<T>[] queueArr = new Queue<T>[maxPriority + 1];
public void Enqueue(int priority, T item) { if (priority < 0 || maxPriority < priority) throw new ArgumentException( string.Format("Prioriteten skal være mellem 0 og {0}.", maxPriority) );
if (queueArr[priority] == null) queueArr[priority] = new Queue<T>();
queueArr[priority].Enqueue(item); }
public T Dequeue() { for (int priority = 0; priority <= maxPriority; priority++) { if (queueArr[priority] != null && queueArr[priority].Count > 0) return queueArr[priority].Dequeue(); }
return default(T); }
public int Count { get { int countTmp = 0; for (int priority = 0; priority <= maxPriority; priority++) { if (queueArr[priority] != null && queueArr[priority].Count > 0) countTmp += queueArr[priority].Count; } return countTmp; } } } }
Hastighed er ret vigtig for mig og jeg har allerede lavet en Heap baseret prioritetskø, der er ret hurtig. Prioritetskøen er dog en essentiel del af mit projekt og den skal fyldes/tømmes MANGE gange.
Jeg skal som sagt kun bruge Insert, ExtractMin og UpdateKey.
Jeg prøver lige at holde Nielle forslag op mod min eksisterende Heap for at se om den er konkurrencedygtig :-)
Jeg er lidt luren ved SortedList, fordi jeg ikke ved hvad den laver inde bag hjelmen, når den sorterer, men den får nok også en chance.
Bulgroz - Er Extract Min, så at starte en foreach og breake den efter første element? Eller har du et bedre forslag.
Jeg er stadig åben for andre alternativer til en superhurtig prioritskø. Ville virkelig gerne have en Fibonacci kø implementering, men kan ikke finde nogen i C#.
Arne: Kunne heller ikke forstå, at man skulle kunne få mindste element ud af en Dictionary uden at løbe det hele igennem. Jeg havde ikke min Data Struktur bog ved hånden, da jeg stillede spørgsmålet og kunne ikke huske hvordan et Hash map fungerer. Så gutten, der påstod, at man kunne få det mindste element ud i STL med et opslag fik mig på glatis. Tror jeg låner ham DataStruktur bogen!!
Man kan få mindste element ud i en SortedDictionary, men der har man så en bagvedliggende ukendt indsættelsesmekanisme, der skal opretholde sorteringen. Den er sandsynligvis ret dyr O(n).
Så tillad mig at komme med en version som performer lidt bedre:
class PriorityQueue<T> { // Denne værdi kan sættes som man ønsker. private const int maxPriority = 100;
private Queue<T>[] queueArr = new Queue<T>[maxPriority + 1];
public PriorityQueue() { for (int priority = 0; priority <= maxPriority; priority++) queueArr[priority] = new Queue<T>(); }
public void Enqueue(int priority, T item) { /* Du kan droppe dette tjek, hvis du alligevel * ikke har i side at overtræde det: if (priority < 0 || maxPriority < priority) throw new ArgumentException( string.Format("Prioriteten skal være mellem 0 og {0}.", maxPriority) ); */
queueArr[priority].Enqueue(item); }
public T Dequeue() { for (int priority = 0; priority <= maxPriority; priority++) { if (queueArr[priority].Count > 0) return queueArr[priority].Dequeue(); }
return default(T); }
public int Count { get { /* Count kan bringes til at performe bedre hvis du selv tæller * antal op og ned ved hhv. Enqueue og Dequeue */ int countTmp = 0; for (int priority = 0; priority <= maxPriority; priority++) { if (queueArr[priority].Count > 0) countTmp += queueArr[priority].Count; } return countTmp; } } }
Dette er en noget naivistisk implementation, og der kan gøre meget for f.eks. at gøre den mere thread-sikker. :^)
namespace E { public class PriorityQueue<T> { private SortedList<int, Queue<T>> q = new SortedList<int, Queue<T>>(); public void Enqueue(int priority, T item) { if(!q.ContainsKey(priority)) { q.Add(priority, new Queue<T>()); } q[priority].Enqueue(item); } public T Dequeue() { int lowpriority = q.Keys[0]; T res = q[lowpriority].Dequeue(); if(q[lowpriority].Count == 0) { q.Remove(lowpriority); } return res; } public bool Empty() { return q.Count == 0; } } public class Test { public static void Main(string[] args) { PriorityQueue<string> q = new PriorityQueue<string>(); q.Enqueue(30, "A"); q.Enqueue(10, "B"); q.Enqueue(20, "C"); while(!q.Empty()) { Console.WriteLine(q.Dequeue()); } Console.ReadKey(true); } } }
Hvis køretid er vigtig for dig kunne du også forsøge dig med en mere avanceret prioritets kø. Eksempler kunne være en vEB træ, fibonacci heap eller splay tree.
Jeg har faktisk lige lavet en Splay tree implementation. Den er ikke bulletproof, men skulle gerne køre i logn på alle operationer. Fibonacci heaps har vist O(1) i insert.
Hvis du skal bruge kø'en til dijkstra shortest path er Splay trees vist alligevel hurtigere end fibonacci heaps, da de udfører operationer hurtigt på elementer som du lige har rørt.
Hvis du finder fejl i implementationen må du meget gerne sige til!
Jeg har lige hentet din implementering og har sat en mand på at teste den. Den skal ganske rigtig anvendes i forbindelse med noget shortest path.
Jeg regner ikke med at finde fejl i din klasse, men du skal nok høre fra mig, hvis vi finder nogle forslag til ændringer.
Jeg takker og bukker
Synes godt om
Ny brugerNybegynder
Din løsning...
Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.
