Priority_Queue / SortedList

micha7

µ schrieb:

Bist Du mit bestimmten Sprachmitteln (Generics, Extension-Methods) nicht vertraut

ja, das ist das Problem.

Kannst du mir sagen was an meinem Comparer falsch ist? Er sortiert ja auch dann nicht, wenn gar keine doppelten Einträge vorkommen, d.h. wenn er sowieso niemals 0 zurückliefern müsste.

Gruß
Michael

Dein Comparer hält sich nicht an die Regeln, die für das interface vorgeschrieben sind. Es ist ganz egal welche Details im Hintergrund schief gehen: So darf man es einfach nicht machen.

Edit: Ich hatte kurz nach Deinem Beitrag oben editiert und einen Link angefügt. Sorry für das durcheinander

Hier die Idee ohne generics und mit massiv schreibaufwand:

SortedList sl = new SortedList();

ArrayList l1 = new ArrayList();
sl.Add(2, l1);
l1.Add("hallo");
l1.Add("welt");

ArrayList l2 = new ArrayList();
sl.Add(3, l2);
l2.Add("!!!!");

Ist das klar?

Firefighter

Also das hat alles nichts mit Priority-Queues zu tuen.
Du musst wohl selbst eine Implementieren, ala Heap oder aehnliches.

Will er ja nicht. Dann nutzt man halt was zur Verfügung steht oder googlet. Bin mir ziemlich sicher, dass jemand schon eine gute Priority-Queue für C# gebaut hat.

Th69

Oder bei CodeProject "klauen" gehen:
http://www.codeproject.com/Articles/126751/Priority-queue-in-C-with-the-help-of-heap-data-str
http://www.codeproject.com/Articles/187229/Priority-Queue-and-Multi-Value-Sorted-Dictionary-i
http://www.codeproject.com/Articles/17333/Generic-Version-of-Priority-Queue-and-Priority-Bas

Firefighter

µ schrieb:

Will er ja nicht. Dann nutzt man halt was zur Verfügung steht oder googlet. Bin mir ziemlich sicher, dass jemand schon eine gute Priority-Queue für C# gebaut hat.

Das das schonmal jemand gebaut hat da stimm ich dir zu. Aber gewisse Datenstrukturen sollte man mit den Built-In Mitteln nicht versuchen "nachzubauen" weil die einfach nicht dafuer gemacht sind. Nicht umsonst basiert die P-Queue auf einer speziellen Technik.

Firefighter schrieb:

Aber gewisse Datenstrukturen sollte man mit den Built-In Mitteln nicht versuchen "nachzubauen" weil die einfach nicht dafuer gemacht sind. Nicht umsonst basiert die P-Queue auf einer speziellen Technik.

Wenn man wirklich eine P-Queue braucht: Kein Widerspruch

Aber genauso wie LinkedLists heutzutage fast unbrauchbar sind, stellt sich die Frage ob der OP eine P-Queue benötigt, oder eine List ohne nennenswerte Performanceprobleme nicht auch ihren Dienst tuen würde.

Firefighter

µ schrieb:

Firefighter schrieb:

Aber gewisse Datenstrukturen sollte man mit den Built-In Mitteln nicht versuchen "nachzubauen" weil die einfach nicht dafuer gemacht sind. Nicht umsonst basiert die P-Queue auf einer speziellen Technik.

Wenn man wirklich eine P-Queue braucht: Kein Widerspruch

Aber genauso wie LinkedLists heutzutage fast unbrauchbar sind, stellt sich die Frage ob der OP eine P-Queue benötigt, oder eine List ohne nennenswerte Performanceprobleme nicht auch ihren Dienst tuen würde.

Affirmative!

micha7

Hallo,

µ schrieb:

Dein Comparer hält sich nicht an die Regeln, die für das interface vorgeschrieben sind. Es ist ganz egal welche Details im Hintergrund schief gehen: So darf man es einfach nicht machen.

Im Allgemeinen stimme ich dir natürlich zu, die Regeln muss man beachten. Im konkreten Fall kann ich mir aber nicht vorstellen was schieflaufen soll, wenn der Vergleicher bei Gleichheit nicht 0 sondern -1 zurückliefert. Jedenfalls läuft das Beispiel jetzt genau so wie es soll, auch dann wenn die gleiche Priorität mehrfach vorkommt.

Gruß
Michael

using System;
using System.Collections;

namespace Priority_Queue
{
    class PriorityQueue
    {
        private System.Collections.SortedList sl;

        public PriorityQueue()
        {
            sl = new System.Collections.SortedList(new myComparer());
        }

        /// <summary>
        /// Ordnet ein Objekt entsprechend seiner Priorität an der richtigen Stelle
        /// in die Priority Queue ein 
        /// </summary>
        /// <param name="priority"></param>
        /// <param name="obj"></param>
        public void push(int priority, object obj)
        {
            sl.Add(priority, obj);
        }

        /// <summary>
        /// Liefert das Objekt mit der höchsten Priorität zurück und entfernt es aus der Queue 
        /// </summary>
        /// <returns></returns>
        public object pop()
        {
            object a = sl.GetByIndex(0);
            sl.RemoveAt(0);
            return(a);
        }

        /// <summary>
        /// Gibt die Anzahl der Elemente zurück, die in der Priority Queue drinstehen
        /// </summary>
        /// <returns></returns>
        public int count()
        {
            return(sl.Count);
        }

        /// <summary>
        /// Ein Vergleicher der niemals 0 zurück liefert
        /// </summary>
        private class myComparer : IComparer
        {
            public int Compare(object x, object y)
            {
                if ((Int32)x < (Int32)y)
                    return (1);
                else
                    return (-1);
            }
        }

    }

}

using System;
using System.Windows.Forms;

namespace Priority_Queue
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            PriorityQueue todo = new PriorityQueue();

            todo.push(3, "drei");      // viele Objekte in die PriorityQueue reinschreiben 
            todo.push(2, "zwei");
            todo.push(2, "zwei a");    // wobei die gleiche Priorität auch mehrfach vorkommen kann
            todo.push(5, "fuenf");
            todo.push(2, "zwei b");
            todo.push(2, "zwei c");
            todo.push(2, "zwei d");
            todo.push(4, "vier");
            todo.push(2, "zwei e");
            todo.push(1, "eins");

            while (todo.count() != 0)       // Liste nach Priorität geordnet ausgeben
                richTextBox1.AppendText(todo.pop() + "\n");     
        }       

    }
}

Firefighter

Wenn du das ganze nun noch als Generic machst und dich etwas an die grundlegenden Codekonventionen von C# haelst kann man das fuer den Moment durchgehen lassen.

micha7

Hallo,

Firefighter schrieb:

Wenn du das ganze nun noch als Generic machst

Eins nach dem anderen... ich habe hier ein Projekt bei dem es weitergehen soll, da will ich mich jetzt nicht verzetteln und die Priority_Queue tut erstmal was sie soll.

Firefighter schrieb:

und dich etwas an die grundlegenden Codekonventionen von C# haelst

Ja, daran möchte ich mich halten. Was könnte ich denn konkret besser machen?

Gruß
Michael

Firefighter

micha7 schrieb:

Hallo,

Firefighter schrieb:

Wenn du das ganze nun noch als Generic machst

Eins nach dem anderen... ich habe hier ein Projekt bei dem es weitergehen soll, da will ich mich jetzt nicht verzetteln und die Priority_Queue tut erstmal was sie soll.

Firefighter schrieb:

und dich etwas an die grundlegenden Codekonventionen von C# haelst

Ja, daran möchte ich mich halten. Was könnte ich denn konkret besser machen?

Gruß
Michael

Find ich klasse deine Einstellung.
Also grundsaetzlich ging es mir um die Benamung deiner Klassen wie auch Funktionen. Wie du am .NET Framework erkennen kannst werden Klassen und Methoden gross geschrieben. Wenn du das erstmal beherzigst sieht der Code noch sauberer aus