Extract Min fra Dictionary

Dictionary er hash baseret. Det giver O(1) for lookup by key. Men altsaa ogsaa O(n) for
at finde mindste key.

Bemærk at du også kan anvende SortedDictionary

SortedDictionary<int, string> dictionary = new SortedDictionary<int, string>();

som er nyttig hvis du skal løbe gennem dine prioriteter.

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;
            }
        }
    }
}

Tak for input.

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. :^)

"Bulgroz - Er Extract Min, så at starte en foreach og breake den efter første element? Eller har du et bedre forslag"....
Ja det ville jeg gøre.

Men hvis dit ID kun er indsat for at holde orden i kaos, så ville jeg nok glemme alt om Id og lave en fifo løsning i stil med det "nille" foreslår.

Bulgroz: Prioriteterne har en betydning, så kan ikke "nøjes" med en FIFO løsning.
Men jeg takker for input.

Nielle: Jeg har desværre ikke nået at teste din løsning op med Heap løsningen endnu. Sorry. Men den får chancen inden længe :-)

Arne, du svarede på det oprindelige spørgsmål. Så smid et svar.
Nielle. Tak for dit bud på en prio kø. Du deler i porten med Arne. Smid et svar.

Svar :^)

En variant:

using System;
using System.Collections.Generic;

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);
        }
    }
}

og et svar.

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 gad virkelig godt have en Fibonacci kø implementering. Men jeg kan ikke finde nogen på nettet i C# og jeg er ikke meget for selv at skrive en :-)

Har du en vis_dk?

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!

Du kan hente den her: http://uldall.eu/files/SplayTree.cs

vis_dk --> Det er top klasse

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