Laden...

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Erstellt von abra_joe vor 14 Jahren Letzter Beitrag vor 3 Jahren 771.547 Views
72 Beiträge seit 2008
vor 14 Jahren

Ok, dann mal weg von den reinen Algorithmen.

Ich hätte gern die Implementierung des Marienbad Spieles mit einem Computergegner. Als Darstellung reicht die Anzahl der Hölzer als Zahl der jeweiligen Reihe. Die Ausgangsposition sieht also so aus:

1
3
5
7

Der Computergegner soll, wenn es möglich ist, die optimale Strategie fahren. Optional kann auch noch berechnet werden ob für die jeweilige Spielsituation des Computergegners eine Gewinnstrategie existiert. Einen Hinweis dazu, wie das gehen kann findet ihr hier:

http://www-i1.informatik.rwth-aachen.de/~algorithmus/algo14.php

Die Aufgabe ist ein wenig umfangreicher als ein reiner Algorithmus aber die meiste Arbeit bezieht sich eigentlich auf die Eingabe. Falls eine solche Aufgabe den Rahmen des Threads sprengt - ich hätte auch noch eine etwas kleinere.

Gelöschter Account
vor 14 Jahren

die vorgabe lautet "in ca. 50 zeilen code umsetzbar".

72 Beiträge seit 2008
vor 14 Jahren

@JAck30lena: Hmm, ich finde in diesem Thread mindestens 3 Lösungen die dieser Vorgabe nicht entsprechen und so aufwendig ist die Implementierung auch nicht.

Aber gut, dann die etwas weniger spassige Aufgabe:
Das Programm muss einen Kreis "zeichnen" können durch Eingabe des Radius. Als Zeichenfeld soll ein einfaches 2 Dimensionales boolsches Array verwendet werden bei dem der Hintergrund false und der Kreis selbst true ist. Der Mittelpunkt des Kreises ist immer der Mittelpunkt des Arrays.
Die Implementierung darf nicht den naiven Ansatz verwenden, dh. einfach nur die Berechnung der Koordinaten durch:

x = Rcos(alpha) und y = Rsin(alpha)

ist nicht ausreichend. Ich schätze, daß die Implementierung in 50 Zeilen mit Eingabe möglich ist da der eigentliche Algorithmus ca. 20 Zeilen umfasst.

S
401 Beiträge seit 2008
vor 14 Jahren

Hallo,

ich erwecke das Thema mal aus dem Winterschlaf. Ich lass immer mit hohem Interesse mit.

Die Implementierung darf nicht den naiven Ansatz verwenden, dh. einfach nur die Berechnung der Koordinaten durch:
x = Rcos(alpha) und y = Rsin(alpha)

Am Ende lässt sich alles darauf zurück führen 😃 Dennoch gibt es wohl ein paar Möglichkeiten, da du das Koordinatensystem nicht festgelegt hast 😉
Ich benutze die ganze normale Kreisgleichung: R² = x² + y² mit: x [-R ; R]

/// <summary>
/// 
/// </summary>
/// <param name="args">
/// A <see cref="String[]"/>
/// </param>
public static void Main(String[] args)
{
	uint R = 1;
	uint aufl = 1;
	bool[][] a = calcCircleArray (R, aufl);

	int i, j;
	for (i = 0; i < a.Length; i++) {
		for (j = 0; j < a[i].Length; j++)
			if (a[i][j])
				System.Console.Write ("+");
			else
				System.Console.Write ("#");

		System.Console.WriteLine ();
	}
}


/// <summary>
/// 
/// </summary>
/// <param name="R">
/// 	Radius des Kreises
/// </param>
/// <param name="n">
/// 	Auflösung: xStep = R * n
/// </param>
/// <returns>
/// 	
/// </returns>               
public static bool[][] calcCircleArray (uint R, uint n)
{
	uint xStep = R * n;
	uint xMax = xStep << 1;
	
	return calcCircleArray (R, n, xMax + 1, xMax + 1);
}


/// <summary>
/// 
/// </summary>
/// <param name="R">
/// 	Radius des Kreises
/// </param>
/// <param name="n">
/// 	n * R = Werte in X-Richtung für R
/// 	n: Bits für die Zahl 1
/// 
/// 	Auflösung: xStep = R * n
/// 	xmax = xStep * R <= xLength
/// 	xmax = xStep * R <= yLength
/// </param>
/// <param name="xLength">
/// 	Länge des Array in x-Richtung
/// 	xmax = xStep * R <= xLength
/// </param>
/// <param name="yLength">
/// 	Länge des Array in y-Richtung
/// 	xmax = xStep * R <= yLength
/// </param>
/// <returns>
/// 	
/// </returns>
public static bool[][] calcCircleArray (uint R, uint n, uint xLength, uint yLength)
{
	uint xStep = R * n;
	uint xMax = xStep << 1;
	uint xm = xLength >> 1;
	uint ym = yLength >> 1;

	if (xLength < xMax)
		throw new ArgumentException ("xLength = " + xLength + " < xMax = " + xMax);
	
	else if (yLength < xMax)
		throw new ArgumentException ("yLength = " + yLength + " < xMax = " + xMax);
	
	else if ((xStep << 1) >= xLength)
		throw new ArgumentException ("xStep * 2 = " + xStep * 2 + " >= xLength = " + xLength);
	
	else if ((xStep << 1) >= yLength)
		throw new ArgumentException ("xStep * 2 = " + xStep * 2 + " >= yLength = " + yLength);

	// init. Array
	bool[][] res = new bool[xLength][];
			
	for (uint i = 0; i < res.Length; i++) {
		res[i] = new bool[yLength];
	}

	// Berechne Array
	// Kreisformel: R² = x² + y²
	double y;
	double R2 = Math.Pow (xStep, 2.0);
//			double xmd = (double) xm;
			double ymd = (double) ym;
	
	// Optimierung noch möglich
	for (uint i = 0; i <= xStep; i++) {
		y = Math.Sqrt (R2 - Math.Pow (i, 2.0));
		
		if(Double.IsNaN(y)) // Außerhabl des Wertebereiches
		   continue;
		
		res[xm + i][(int) Math.Round(ymd + Math.Round(y))] = true;
		res[xm - i][(int) Math.Round(ymd + Math.Round(y))] = true;
		
		res[xm + i][(int) Math.Round(ymd - Math.Round(y))] = true;
		res[xm - i][(int) Math.Round(ymd - Math.Round(y))] = true;
	}

	return res;
}

Ausgabe:

#+#
+#+
#+#

// Edit: Rundungsfehler reduziert

@fz 7090 Das liegt daran, dass ich den y-Wert zu bald in int überführe

F
155 Beiträge seit 2009
vor 14 Jahren

Hallo,

dein Code ergibt für größere R kein geschlossenen Kreis...

Grü0e FZ

"We better hurry up and start coding, there are going to be a lot of bugs to fix."

72 Beiträge seit 2008
vor 14 Jahren

Sorry, hatte gestern und heute Mamutbesprechungen und habe die Antwort jetzt erst gesehen.
Grundsätzlich gilt, was fz7090 schon sagte - leider kein geschlossener Kreis. Der Grund liegt in der von Dir verwendeten Kreisformel welche sich nur bedingt auf diskrete Darstellungen übertragen lässt. Es gibt einen Weg ohne Quadrat und Wurzel .... der aber so (mit Absicht) nicht gefordert ist, also keine Angst.

Grundsätzlich bist Du schon auf dem richtigen Weg, da Du die Spiegelung an den Achsen beachtet und damit nicht den rein naiven Ansatz gewählt hast. Nun noch die Lücken schliessen und Du hast es. 😉

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

Es gibt einen Weg ohne Quadrat und Wurzel .... ...und nennt sich Bresenham-Algorithmus.
Ich hab ihn mal für den Spezialfall angepasst.

  class Program
  {
    static void BuildOctant(int r, bool[,] res)
    {
      int f = 1 - r;
      int fx = 0;
      int fy = -2*r;
      int x = 0;
      int y = r;
    
      res[x+r, y+r] = true;
      while (x < y)
      {
        if (f >= 0)
        {
          y--;
          fy += 2;
          f += fy;
        }
        x++;
        fx += 2;
        f += fx + 1;
        res[x+r, y+r] = true;
      }
    }
    public static void Main(string[] args)
    {
      int r = 0;
      Console.Write("Radius: ");
      while(!(int.TryParse(Console.ReadLine(), out r) && (r > 0))){
        Console.WriteLine("Der Radius muss eine Ganzzahl größer 0 sein!");
        Console.Write("Radius: ");
      }
      bool[,] res = new bool[2*r+1, 2*r+1];
      // Grundoktant
      BuildOctant(r, res);
      //Spiegelung:
      for(int y = 2*r; y >= 3*r/4; y--)
      {
        for(int x = r; x <= 2*r; x++)
        {
          res[y, x] = res[x, y];
          res[2*r-x, y] = res[x, y];
          res[x, 2*r-y] = res[x, y];
          res[2*r-x, 2*r-y] = res[x, y];
        }
      }
      // Ausgabe:
      for(int y = 0; y <= 2*r; y++)
      {
        for(int x = 0; x <= 2*r; x++)
        {
          Console.Write(res[x, y] ? "0" : "x");
        }
        Console.WriteLine();
      }
      Console.ReadKey();
    }
  }

Ausgabe mit r=1:

x0x
0x0
x0x

Ausgabe mit r=15:

xxxxxxxxxxxx0000000xxxxxxxxxxxx
xxxxxxxxx000xxxxxxx000xxxxxxxxx
xxxxxxx00xxxxxxxxxxxxx00xxxxxxx
xxxxxx0xxxxxxxxxxxxxxxxx0xxxxxx
xxxxx0xxxxxxxxxxxxxxxxxxx0xxxxx
xxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx
xxx0xxxxxxxxxxxxxxxxxxxxxxx0xxx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
0xxxxxxxxxxxxxxxxxxxxxxxxxxxxx0
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
x0xxxxxxxxxxxxxxxxxxxxxxxxxxx0x
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xx0xxxxxxxxxxxxxxxxxxxxxxxxx0xx
xxx0xxxxxxxxxxxxxxxxxxxxxxx0xxx
xxxx0xxxxxxxxxxxxxxxxxxxxx0xxxx
xxxxx0xxxxxxxxxxxxxxxxxxx0xxxxx
xxxxxx0xxxxxxxxxxxxxxxxx0xxxxxx
xxxxxxx00xxxxxxxxxxxxx00xxxxxxx
xxxxxxxxx000xxxxxxx000xxxxxxxxx
xxxxxxxxxxxx0000000xxxxxxxxxxxx

Hab leiuder heut keine Zeit mehr für was neues... das muss bis morgen warten.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

also doch noch auf die Schnelle die nächste Aufgabe:
Schreibt eine Funtion, die aus 2 übergebenen Integer-Arrays der Länge 4 (ein Geheimnis und ein Versuch) ermittelt, wie viele schwarze und weiße Pins bei einem Mastermind-Spiel zu setzen sind.
Gleiche Werte entsprechen gleichen Farben. Mehrfachbenutzung einer Farbe im Geheimnis ist möglich.
Die Methode soll die Signatur

bool MastermindTest(int[] geheimnis, int[] versuch,
                    out int schwarz, out int weiss)

besitzen, und true zurückgeben, wenn alle Farben im Versuch mit denen im Geheimnis in der exakten Reihenfolge übereinstimmen (richtige Lösung).
Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

C
63 Beiträge seit 2010
vor 14 Jahren

Hi,

Ich hab genau 4minuten und 28sekunden programmiert würde mich mal interessieren ob diese tolle Funktion hier das bringt was du wolltest(Achtung: 0 ist bei mir keine Farbe d.h. falls 0 als Farbe benutzt wird, müsste man etwas ergänzen wie: wenn ein Array 0 enthält dann alles Inkrementieren):

        
bool MastermindTest(int[] geheimnis, int[] versuch, out int schwarz, out int weiss)
        {
            schwarz = 0;
            weiss = 0;
            for (int i = 0; i < 4; i++)
            {
                if (geheimnis[i] == versuch[i])
                {
                    geheimnis[i] = 0;
                    schwarz++;
                }
                else if (geheimnis.Contains(versuch[i]))
                {
                    for (int i2 = 0; i2 < 4; i2++)
                    {
                        if (geheimnis[i2] == versuch[i])
                        {
                            geheimnis[i2] = 0;
                            break;
                        }
                    }
                    weiss++;
                }
            }
            if (schwarz == 4) return true;
            return false;
        }

Ok ich geb zu das is weder kurz noch elegant, aber dafür schnell;)

Mfg Campac

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo Campac68,

Ich hab genau 4minuten und 28sekunden programmiert

das war wohl etwas zu wenig Zeit oder du hättest zumindest nochmal soviel Zeit in den Test investieren sollen 😃 denn die Funktion ist falsch, d.h. sie liefert nicht in allen Fällen das richtige Ergebnis. Sie liefert in bestimmten Situationen zuwenig schwarz, z.B. in folgendem Fall (laut Wikipedia darf eine Farbe mehr als einmal vorkommen):

MastermindTest (new int [] {1, 2, 3, 3},
                new int [] {3, 1, 3, 2},
                out schwarz, out weiss);

Ergebnis ist 0 4 statt korrekt 1 3.

herbivore

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo,

hier meine Lösung. Ist ein Stück länger, dafür zum Verständnis kommentiert.

private static bool MastermindTest(int[] geheimnis, int[] versuch, out int schwarz, out int weiss)
{
    schwarz = 0;
    weiss = 0;

    // Arrays zum Angeben bereits ausgewerteter Stellen
    bool[] geheimnisIndizes = new bool[4];
    bool[] versuchIndizes = new bool[4];

    // Anzahl zu setzender schwarzer Stecker ermitteln
    for (int i = 0; i < 4; i++)
    {
        if (geheimnis[i] == versuch[i])
        {
            schwarz++;

            geheimnisIndizes[i] = true;
            versuchIndizes[i] = true;
        }
    }

    // Über Geheimnis-Array iterieren
    for (int i = 0; i < 4; i++)
    {
        // Geheimnis-Ziffer wurde bereits ausgewertet
        if (geheimnisIndizes[i])
        {
            continue;
        }

        // Über Versuch-Array iterieren
        for (int j = 0; j < 4; j++)
        {
            // Versuch-Ziffer wurde bereits ausgewertet
            if (versuchIndizes[j])
            {
                continue;
            }

            // "Halb-Treffer" (weiss) gefunden
            if (geheimnis[i] == versuch[j])
            {
                weiss++;

                geheimnisIndizes[i] = true;
                versuchIndizes[j] = true;
            }
        }
    }

    return (schwarz == 4);
}

Edit: kleine Änderungen nach Anregungen von herbivore eingearbeitet.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo Morius,

das sieht korrekt aus. Du bist dran.

Gruß, MarsSTein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

C
63 Beiträge seit 2010
vor 14 Jahren

tja ich sags mal so: versuch wars wert ich hatte nich viel zeit und war todmüde;)
beim nächsten mal!

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo,

okay, weiter geht's: Da wir gerade beim Thema Spiele waren, setze ich diesen Trend mal fort.

Es soll eine Methode [TT]ErzeugeSpielfeld()[/TT] geschrieben werden, die ein Schiffe-Versenken-Spielfeld der Größe 10x10 generiert.
Dazu gehört die valide, zufällige Positionierung der Schiffsflotte eines Spielers (s. Link unten) sowie die anschließende Ausgabe der Schiffe ("X") und der unbesetzten Wasserfelder (".").
Es sind folgende [URL]Spielregeln zur Aufstellung[/URL] zu verwenden.

Viel Spaß!

Edit: Auf Hinweis von herbivore wurden die Regeln konkretisiert.

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

1.130 Beiträge seit 2007
vor 14 Jahren

Funkt bei mir:

public static void Main()
        {
            int[] zahlen = new int[6]
            {
                0,//0
                0,//1
                4,//Uboot(2)
                3,//Kreutzer(3)
                2,//Zerstörer(4)
                1,//Schlachtschiff(5)
            };

            int[,] feldx = new int[10, 10];
            int[,] feldy = new int[10, 10];
            for(int x=0;x<10;x++)
                for (int y = 0; y < 10; y++)
                {
                    feldx[x, y] = 10 - x;
                    feldy[x, y] = 10 - y;
                }
            Random rnd = new Random();
            for (int i = zahlen.Length - 1; i >= 0; i--)
            {
                for (int i2 = zahlen[i] - 1; i2 >= 0; i2--)
                {
                    int xcount = feldx.Cast<int>().Count((f) => f >= i);
                    int ycount = feldy.Cast<int>().Count((f) => f >= i);
                    int c = rnd.Next(xcount + ycount);
                    if (c < xcount)
                    {
                        for(int x=0;x<10;x++)
                            for (int y = 0; y < 10; y++)
                            {
                                if (feldx[x, y]>=i)
                                {
                                    if (c > 0)
                                    {
                                        c--;
                                    }
                                    else
                                    {
                                        for (int ilen = 0; ilen < i; ilen++)
                                        {
                                            Set(x,y,feldx,feldy);
                                            x++;
                                        }
                                        goto breakout;
                                    }
                                }
                            }
                    breakout:{}
                    }
                    else
                    {
                        c -= xcount;
                        for (int x = 0; x < 10; x++)
                            for (int y = 0; y < 10; y++)
                            {
                                if (feldy[x, y] >= i)
                                {
                                    if (c > 0)
                                    {
                                        c--;
                                    }
                                    else
                                    {
                                        for (int ilen = 0; ilen < i; ilen++)
                                        {
                                            Set(x, y, feldx, feldy);
                                            y++;
                                        }
                                        goto breakout;
                                    }
                                }
                            }
                    breakout: { }
                    }
                }
            }

            for (int y = 0; y < 10; y++)
            {
                for (int x = 0; x < 10; x++)
                {
                    if (feldx[x, y] == -1 && feldy[x, y] == -1)
                        Console.Write("X");
                    else
                        Console.Write(".");
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }

        private static void Set(int x, int y, int[,] feldx, int[,] feldy)
        {
            Setx(x, y, feldx);
            Setx(x, y + 1, feldx);
            Setx(x, y - 1, feldx);

            Sety(x, y, feldy);
            Sety(x + 1, y, feldy);
            Sety(x - 1, y, feldy);
        }

        private static void Setx(int x, int y, int[,] feldx)
        {
            if (y < 0 || y >= 10) return;
            if (x < 9)
            {
                feldx[x + 1, y] = 0;
            }
            int dist = -1;
            for (int x2 = x; x2 >= 0; x2--)
            {
                if (feldx[x2, y] < dist) break;
                feldx[x2, y] = dist;
                dist++;
            }
        }

        private static void Sety(int x, int y, int[,] feldy)
        {
            if (x < 0 || x >= 10) return;
            if (y < 9)
            {
                feldy[x, y+1] = 0;
            }
            int dist = -1;
            for (int y2 = y; y2 >= 0; y2--)
            {
                if (feldy[x, y2] < dist) break;
                feldy[x, y2] = dist;
                dist++;
            }
        }

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo Floste,

ich habe mich noch nicht mit deinem Code beschäftigt bzw. mit der Funktionsweise, aber er scheint zu funktionieren - du bist dran!

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

1.130 Beiträge seit 2007
vor 14 Jahren

Da es programmier-SPIEL heißt, dachte ich, es kann auch mal ein spiel rauskommen.

Das wird, wenn es auch keine besonders anspruchsvolle Aufgabe ist, doch eine recht Lange.
Spielidee: Man schießt aus der Mitte mit Geschossen herumfligende Brocken ab, damit diese einem nicht zu nahe kommen.

Um die Sache einfach zu halten ist alles rechteckig:
-Das Spielfeld ist 500x500 Pixel groß
-Genau in der Mitte ist ein zu verteidigendes Quadrat, das 20x20 Pixel groß ist
-Aus der Mitte herkommend kann man zum Mauszeiger hin 10x10 große Quadrate (am besten rot) schießen, die sich mit 200px/sekunde Fortbewegen
-Von oben herab regnet es Rechtecke, die 10 bis 50px Seitenlänge haben , sich mit 50 bis 100px/Sekunde nach unten bewegen und mit -50 bis +50px/Sekunde seitwärts bewegen. Sie behalten genau wie die Geschosse ihre Richtung und Größe bei. Die Blöcke sollen sich von Geschossen und dem Hintergrund abheben. Alle Werte sollen innherhalb der Vorgaben möglichst zufällig sein.
-Wenn ein Geschoss einen Block trifft, verschwinden Beide, es wird aber ein neuer Block erzeugt, sodass die Blockanzahl konstant ist.
-Wenn ein Block das Spielfeld verlässt, wird er zerstört und ein neuer erzeugt.
-Wenn ein Geschoss das Spielfeld verlässt wird es ersatzlos zerstört.
-Alle 5 Sekunden kommt ein Block hinzu, am Anfang gibt es genau 5 Stück.
-Wenn ein Block die mitte erreicht hat man verloren und die zeit wird angezeigt.
-Man kan alle 250ms schießen.
-Blöcke haben mit anderen blöcken keine kollision, selbiges gild für geschosse. (ok, eine Variante mit Blockkollision wäre auch mal lustig.)

-Für Grafik sollte Gdi reichen (bitte flackerfrei), anderes ist erlaubt

-Markus111 ist, weil er die Lösung kennt ausgeschlossen.
-Alle, die sich das Programm von markus111 geholt haben sind ebenfalls ausgeschlossen.

Damit es nich so lange dauert, ist heir ein Stub, man muss ihn aber nicht unbedingt benutzen und kann ihn abwandeln.
Tipp1: eine for-Schleife rückwärts ist hilfreich!
Tipp2: rectangle.IntersectsWith testet Kollision!

public class Asteriods : Form
    {
        public Asteriods()
        {
            this.Size = new Size(500, 500);
            this.FormBorderStyle = FormBorderStyle.FixedDialog;
            SetStyle(ControlStyles.OptimizedDoubleBuffer | ControlStyles.AllPaintingInWmPaint,true);
            DoubleBuffered = true;
            sw = new Stopwatch();
            sw.Start();
            //TODO:Ergänzen
        }

        Stopwatch sw;
        float nowMilliseconds=0;
        float lastShot = 0;
        Random rnd = new Random();
        List<Particle> asteroids=new List<Particle>();
        List<Particle> missils=new List<Particle>();
        RectangleF center;

        protected override void OnPaint(PaintEventArgs e)
        {
            float timeOffset = sw.ElapsedMilliseconds - nowMilliseconds;
            UpdateParticles(missils, timeOffset);//bewegen und aussortieren, was aus dem Rahmen fällt
            UpdateParticles(asteroids, timeOffset);
            //TODO:Ergänzen

            using (SolidBrush sb = new SolidBrush(Color.Green))
                e.Graphics.FillRectangle(sb,center);
            foreach (Particle p in asteroids.Concat(missils))
            {
                using (SolidBrush sb = new SolidBrush(p.c))
                    e.Graphics.FillRectangle(sb, p.rect);
            }
            nowMilliseconds += timeOffset;
            Invalidate();
        }

        protected override void OnMouseDown(MouseEventArgs e)
        {
            //TODO:Ergänzen
        }

        class Particle
        {
            public RectangleF rect;
            public float speedx;
            public float speedy;
            public Color c;
        }
    }

ps: inklusive gegebenen Code und using-krimskrams hab ich 122 Zeilen gebraucht
wenn man tipp1 beachtet gibts in meinen Augen auch keinerlei "fallen" mehr.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo zusammen,

ps: inklusive gegebenen Code hab ich 122 Zeilen gebraucht

das ist in meinen Augen eine wichtige Information. Die Aufgabe ist also nicht so aufwändig, wie man vielleicht denkt. Also probiert euch ruhig mal dran.

herbivore

1.002 Beiträge seit 2007
vor 14 Jahren

Hallo Floste,

um das Programmierspiel mal wieder "aufzuwecken": Vielleicht solltest du eine neue Aufgabe mit kleinerem Umfang stellen, da an der jetzigen anscheinend kein großes Interesse besteht ...

m0rius

Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

oder du wartest bis heut abend... ich hab's nämlich am WE implementiert, weil ich den Thread auch aufwecken wollte, kam aber nicht mehr zum Hochladen.

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

es geht sicherlich schöner / kürzer / besser, aber ich denke es erfüllt alle geforderten Vorgaben.
Ich hab' die Main() mal mir reingepackt, so dass sich der folgende Codeblock direkt zur .exe kompilieren lässt 😃


using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;
using System.Windows.Forms;

public class Asteriods : Form
{
    static void Main()
    {
      Application.Run(new Asteriods());
    }
    Stopwatch sw;
    int lastPaint = 0;
    int lastShot = 0;
    int lastBlock = 0;
    List<Particle> asteroids=new List<Particle>();
    List<Particle> missils=new List<Particle>();
    RectangleF center = new RectangleF(240f,240f,20f,20f);
    bool end = false;

    public Asteriods()
    {
      this.Size = new Size(500, 500);
      this.FormBorderStyle = FormBorderStyle.FixedDialog;
      this.BackColor = Color.Black;
      SetStyle(ControlStyles.OptimizedDoubleBuffer | ControlStyles.AllPaintingInWmPaint,true);
      DoubleBuffered = true;
      for(int i = 0; i < 5; i++)
      {
        asteroids.Add(new Particle());
      }
      sw = new Stopwatch();
      sw.Start();
    }

    protected override void OnPaint(PaintEventArgs e)
    {
      int snapshot = (int)sw.ElapsedMilliseconds;
      int timeOffset = snapshot - lastPaint;
      lastPaint = snapshot;
      Particle p1;
      Particle p2;
      bool updateMissiles = true;
      for(int i = asteroids.Count-1; i>=0; i--)
      {
        p1 = asteroids[i];
        p1.rect = new RectangleF(p1.rect.Left + p1.speedx*timeOffset,
                                 p1.rect.Top + p1.speedy*timeOffset,
                                 p1.rect.Width, p1.rect.Height);
        if(p1.rect.IntersectsWith(this.ClientRectangle))
        {
          if(p1.rect.IntersectsWith(center))
          {
            end = true;
          }
          for(int j = missils.Count-1; j>=0; j--)
          {
            p2 = missils[j];
            if(updateMissiles)
            {
              p2.rect = new RectangleF(p2.rect.Left + p2.speedx*timeOffset,
                                       p2.rect.Top + p2.speedy*timeOffset,
                                       p2.rect.Width, p2.rect.Height);
              updateMissiles = (j!=0);
            }
            if(p2.rect.IntersectsWith(this.ClientRectangle))
            {
              if(p1.rect.IntersectsWith(p2.rect))
              {
                asteroids[i] = new Particle();
                missils.RemoveAt(j);
              }
            }
            else
            {
              missils.RemoveAt(j);
            }
          }
        }
        else
        {
          asteroids[i] = new Particle();
        }
        e.Graphics.FillRectangle(Brushes.Green, asteroids[i].rect);
      }
      if((lastBlock+5000) <= snapshot)
      {
        lastBlock = snapshot-(snapshot%5000);
        asteroids.Add(new Particle());
      }
      foreach(Particle p in missils)
      {
        e.Graphics.FillRectangle(Brushes.Red, p.rect);
      }
      e.Graphics.FillRectangle(Brushes.Blue, center);
      if(end)
      {
        e.Graphics.DrawString((snapshot/1000f).ToString("0.000")+"s",
                              new Font("system",25), Brushes.White, 
                              Point.Empty);
      }
      else
      {
        Invalidate();
      }
    }

    protected override void OnMouseDown(MouseEventArgs e)
    {
      int snapshot = (int)sw.ElapsedMilliseconds;
      if((lastShot+250) <= snapshot)
      {
        lastShot = snapshot;
        missils.Add(new Particle(e.X-250, e.Y-250));
      }
    }

    class Particle
    {   
      static Random rand = new Random();
      public RectangleF rect;
      public float speedx;
      public float speedy;

      public Particle()
      {
        float height = rand.Next(10,50);
        int width = rand.Next(10,50);
        rect = new RectangleF(rand.Next(0,500-width),1-height,rand.Next(10,50),height);
        speedx = rand.Next(-50,50)/1000f;
        speedy = rand.Next(50,100)/1000f;
      }
      public Particle(int mouseX, int mouseY)
      {
        rect = new RectangleF(245f,245f,10f,10f);
        float dia = (float)Math.Sqrt(mouseX*mouseX+mouseY*mouseY);
        speedx = mouseX/dia/5;
        speedy = mouseY/dia/5;
      }
    }
}

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

1.130 Beiträge seit 2007
vor 14 Jahren

*Grr* das gibts doch garned! Ich kann einfach nix finden, dass ich daran auszusetzen hätte!

Spaß beiseite: MarsStein, du bist dran!

Ich hab MarsSteins code mal durch nen Compiler geschickt, das Resultat ist im Anhang.

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

die nächste Aufgabe:

erstell eine Queue-Klasse, die folgendes Interface implementiert.

Haken: Die Namespaces System.Collections und System.Collections.Generic sind ausgeschlossen und dürfen nicht verwendet werden.


interface IQueue<T>
{
  // gibt die Anzahl der Elemente an.
  int Count
  {
    get;  
  }
 
  // entfernt das Element am Anfang der Queue und gibt es zurück
  T Dequeue();
  
  // fügt das Element "elem" am Ende der Queue an
  void Enqueue(T elem);
  
  // Gibt true zurück, wenn das Element elem in der Queue enthalten ist, sonst false
  bool Contains(T elem);
}

Gruß, MarsStein

Edit: Habe mich vielleicht anfangs etwas unverständlich ausgedrückt.
Nach Jack30lenas nächster Antwort habe ich die Kommentare eingefügt, um kenntlich zu machen wie die Klasse arbeiten soll.

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

799 Beiträge seit 2007
vor 14 Jahren

Sind die Namespaces auch ausgeschlossen wenn nur die Interfaces implementiert werden?

As a man thinketh in his heart, so he is.

  • Jun Fan
    Es gibt nichts Gutes, außer man tut es.
  • Erich Kästner
    Krawutzi-Kaputzi
  • Kasperl
Gelöschter Account
vor 14 Jahren
        class MyQueue<T> : IQueue<T>
        {
            private T[] internalArray = new T[10];
            private int queueIndex = -1;

            public int Count
            {
                get { return queueIndex + 1; }
            }

            public T Dequeue()
            {
                T result = internalArray[queueIndex];
                internalArray[queueIndex] = default(T);
                queueIndex--;
                return result;
            }

            public void Enqueue(T elem)
            {
                if(internalArray.Length == queueIndex + 1)
                {
                    T[] newArray = new T[internalArray.Length * 2];
                    Array.Copy(internalArray, newArray, internalArray.Length);
                    internalArray = newArray;
                }

                internalArray[++queueIndex] = elem;
            }

            public bool Contains(T elem)
            {
                return internalArray.Any(item => item.Equals(elem));
            }
        }

edit: der code hat keinerlei ansprüche auf robustheit 😉

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo Jack30lena,

wenn ich es richtig blicke, hast Du einen Stack gebaut.
Unter einer Queue verstehe ich eigentlich einen FIFO.

Gruß, MarsStein

Edit: siehe "Edit" der Aufgabenstellung

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

Gelöschter Account
vor 14 Jahren

wenn ich es richtig blicke, hast Du einen Stack gebaut.
Unter einer Queue verstehe ich eigentlich einen FIFO.

oha... mist 😃 da hab ich nciht ordendlich nachgedacht.

[edit=herbivore]Eigentlich wurde dieser Beitrag erst am 17.03.2010 um 09:38:04 gepostet, aber ich habe ihn aus Gründen der Übersichtlichkeit und des direkten Zusammenhangs an diese Stelle verschoben.[/edit]

C
401 Beiträge seit 2007
vor 14 Jahren

Geht bestimmt schöner, aber funktioniert 😄


public class Queue<T> : IQueue<T>
	{
		QueueItem<T> _items;
		object _lock;
		public Queue ()
		{
			_lock = new object();
		}
		
		public int Count
		{
			get{
				lock(_lock) {
					if(_items != null) {
						return _items.Count;
					} else {
						return 0;
					}
				}
			}
		}
		
		public T Dequeue() {
			T item = default(T);
			lock(_lock) {
				if(Count > 1) {
					item = _items.Data;
					_items = _items.Next;
					_items.Parent = null;
				} else if(Count == 1) {
					item = _items.Data;
					_items = null;
				}
			}
			return item;
		}
		
		public void Enqueue(T elem) {
			lock(_lock) {
				if(_items != null)
					_items.Add(elem);
				else
					_items = new QueueItem<T>(null, elem);
			}
		}
		
		public bool Contains(T elem) {
			lock(_lock) {
				if(_items != null)
					return _items.Contains(elem);
				else
					return false;
			}
		}
	}

public class QueueItem<T>
	{
		object _lock = new object();
		public QueueItem<T> Parent {
			get; set;
		}
		public T Data {
			get; set;
		}
		public QueueItem<T> Next {
			get; set;
		}
		public QueueItem (QueueItem<T> parent, T data)
		{
			if(parent != null) {
				Parent = parent;
				Parent.Next = this;
			}
			Data = data;
		}
		public void Add(T item) {
			lock(_lock) {
				if(Next != null) {
					Next.Add(item);
				} else {
					Next = new QueueItem<T>(this, item);
				}
			}
		}
		
		public int Count {
			get {
				if(Next != null) { 
					return 1 + Next.Count;
				} else {
					return 1;
				}
			}
		}
		
		public bool Contains(T item) {
			if(Data.Equals(item)) {
				return true;
			} else if(Next != null) {
				return Next.Contains(item);
			} else {
				return false;
			}
		}
	}


edit: kleinen Fehler behoben, der eine Exception beim Aufruf von Dequeue auf eine leere Liste erzeugt hat... danke @ MarsStein

C
63 Beiträge seit 2010
vor 14 Jahren

Tja du warst schneller, meiner sähe so aus:

    class MyQueue<T> : IQueue<T>
    {
        private int _count;
        private QueueElement<T> front;

        public MyQueue()
        {
            _count = 0;
        }

        public int Count
        {
            get { return _count; }
        }

        public void Enqueue(T elem)
        {
            if (Count > 0)
            {
                front.enter(elem);
                _count++;
            }
            else
            {
                front = new QueueElement<T>(elem);
                _count++;
            }
        }

        public T Dequeue()
        {
            if (Count > 0)
            {
                T frontContent = front.Content;
                front = front.leave();
                _count--;
                return frontContent;
            }
            else
            {
                return default(T);
            }
        }

        public bool Contains(T elem)
        {
            if (Count > 0)
            {
                return front.Contains(elem);
            }
            else
            {
                return false;
            }
        }

        private class QueueElement<T>
        {
            QueueElement<T> next;
            public T Content
            {
                get;
                private set;
            }

            public QueueElement(T Content)
            {
                this.Content = Content;
            }

            public void enter(T elem)
            {
                if (next != null)
                {
                    next.enter(elem);
                }
                else
                {
                    next = new QueueElement<T>(elem);
                }

            }

            /// <summary>
            /// Gibt die nächste front zurück
            /// </summary>
            /// <returns></returns>
            public QueueElement<T> leave()
            {
                return next;
            }

            public bool Contains(T elem)
            {
                if (next != null)
                {
                    return Content.Equals(elem) || next.Contains(elem);
                }
                else
                {
                    return Content.Equals(elem);
                }
            }
        }
    }

Wurde nich lange getestet aber ich denke vom Prinzip her sollte es so ähnlich sein wie das von Corpsegrinder^^

3.170 Beiträge seit 2006
vor 14 Jahren

Hallo,

Tja du warst schneller,

so ist es...

@Corpsegrinder
...und deshalb bist Du jezt auch dran!

Gruß, MarsStein

Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca

C
401 Beiträge seit 2007
vor 14 Jahren

Okay, dann hätte ich gerne eine einfache Listenklasse, die als binärer Differenzbaum implementiert wird. Es sollen Elemente vorne und hinten angefügt werden können und ein Zugriff auf die Elemente über den Index soll möglich sein. Natürlich soll auch eine hübsche ToString() Methode vorhanden sein 😉

zum binären Differenzbaum:

mal angenommen wir haben 7 Elemente, dann sieht er so aus:

        4
      /   \
    -2    +2
   /  \   /  \
 -1   +1  -1  +1

Das erste Element ist das mittlere der Liste und hat somit auch den Index dieses Elements in der Liste. Sämtliche andere Knoten enthalten immer als Index einen relativen Wert zum vorherigen Knoten. Also der linke Knoten vom Root-Element enthält -2, also ist der wahre Index 4 - 2 = 2.

nach außen soll es eine Liste sein. Nur INTERN soll es ein Baum sein.

ToString sieht bei einer Liste z.B. so aus, dass für alle Elemente ToString ausgegeben wird.


interface IList<T> {
  int Count { get; }
  IList<T> Add(T item); // fügt das Item am Ende der Liste an
  IList<T> AddToHead(T item); // fügt das Item am Anfang der Liste an
  IList<T> RemoveFirst(); // entfernt das erste Element
  IList<T> RemoveLast(); // entfernt das letzte Element
  T Get(int index); // liefert das entsprechende Element zum Index
  String ToString(); // gibt für jedes Element ToString aus
}

So, habe gleich die Gelegenheit genutzt und wie aus dem Interface hervorgeht soll die Liste Immutable sein 😉

Also, da die Liste Immutable sein soll muss bei einem "Mutator" immer eine neue Liste, sprich IList<T> zurückgegeben werden.

49.485 Beiträge seit 2005
vor 14 Jahren

Hallo zusammen,

nach Möglichkeit sollten alle Aufgabenstellungen von Anfang an so ausführlich und gleichzeitig so präzise sein, dass jeder sofort ohne Nachfragen loslegen kann. Da bei der letzten Aufgabestellung viele Nachfragen nötig waren und es daher sehr unübersichtlich geworden war, habe ich alle Antworten/Angaben von Corpsegrinder in einem Post zusammengefasst und die zugehörigen Fragen ganz entfernt.

Damit sollte die Aufgabenstellung jetzt klar sein.

Eine solche Liste immutable zu implementieren, macht in meinen Augen zwar für den praktischen Einsatz nicht viel Sinn, weil es den Aufwand der Hinzufüge- und Löschoperationen unnötig auf die Aufwandsklasse O(n) erhöht, aber das soll für das Spiel mal egal sein. Der Aufgabensteller ist ja frei in dem, was er vorgibt, solange die Vorgaben eindeutig sind und das sind sie ja. Nehmt die Aufgabenstellung also so wie sie ist. Ich wünsche viel Erfolg bei der Umsetzung.

herbivore

C
401 Beiträge seit 2007
vor 13 Jahren

So, ich hol den Thread mal wieder hoch, damit er nicht verloren geht 😉

Hallo zusammen,
Eine solche Liste immutable zu implementieren, macht in meinen Augen zwar für den praktischen Einsatz nicht viel Sinn, weil es den Aufwand der Hinzufüge- und Löschoperationen unnötig auf die Aufwandsklasse O(n) erhöht, aber das soll für das Spiel mal egal sein.

Das macht Sinn, wenn man auf Multicore Systemen arbeitet, da ansonsten nach jeder Änderung jede CPU ihren Cache aus dem Arbeitsspeicher aktualisieren muss, was ggf. mehr Zeit verbraucht als bei immutable Listen.

So, da scheinbar keiner Lust hat die Aufgabe zu lösen stell ich hier mal eine Lösung in Scala rein. Wer Lust hat kann auf Basis dessen gerne noch eine Lösung in C# erstellen.



// EmptyNode.scala
import java.lang.IndexOutOfBoundsException

case class EmptyNode[A] extends Tree[A] {
  override def isEmptyNode = true
  def toList[B >: A]: List[B] = List()
  def get[B >: A](i: Int): B = {
    throw new IndexOutOfBoundsException
  }

  def get[B >: A](i: Int, parentIndex: Int): B = {
    throw new IndexOutOfBoundsException
  }
}


//Leaf.scala

case class Leaf[A](data: A, index:Int) extends Tree[A] {
  def toList[B >: A]: List[B] = List(data)
  def get[B >: A](i: Int): B = {
    if(i == index)
      data
    else
      throw new IndexOutOfBoundsException
  }

  def get[B >: A](i: Int, parentIndex: Int): B = {
    val realIndex = parentIndex + index
    if(realIndex == i)
      data
    else
      throw new IndexOutOfBoundsException
  }
}


// MyList.scala

object MyList {
  def create[A](objects: A*): Tree[A] = {
    def creator(data: List[A], index: Int): Tree[A] = {
     data.size match {
       case 0 => EmptyNode[A]
       case 1 => Leaf(data.head, index)
       case 2 => Node(data(1), Leaf(data.head, -1), EmptyNode[A], index)
       case _ => {
        val split = data.splitAt(data.size / 2)
        Node(split._2.head, creator(split._1, ((split._1.size+1) / 2) * -1 ), creator(split._2.tail, (split._2.tail.size+1) / 2), index)
       }
     }
    }
    creator(objects.toList, objects.size / 2)
  }
}


// Node.scala


case class Node[A](data: A, left: Tree[A], right: Tree[A], index: Int) extends Tree[A] {
  def toList[B >: A]: List[B] = left.toList ++ List(data) ++ right.toList
  def get[B >: A](i: Int): B = {
    if(index == i) {
      data
    } else if(index > i) {
      left.get(i, index)
    } else {
      right.get(i, index)
    }
  }

  def get[B >: A](i: Int, parentIndex: Int): B = {
    val realIndex = parentIndex + index
    if(realIndex == i) {
      data
    } else if(realIndex > i) {
      left.get(i, realIndex)
    } else {
      right.get(i, realIndex)
    }
  }
}


// Tree.scala


trait Tree[A] {
  def toList[B >: A]: List[B]
  def isEmptyNode = false
  def addToHead[B >: A](o: B): Tree[B] = MyList.create[B]((List(o) ++ toList):_*)
  def addToTail[B >: A](o: B): Tree[B] = MyList.create[B]((toList ++ List(o)):_*)
  def removeFirst[B >: A]: Tree[B] = MyList.create[B](toList.tail:_*)
  def removeLast[B >: A]: Tree[B] = MyList.create[B](toList.dropRight(1):_*)
  override def toString = {
    val str = toList.toString
    str.substring(5, str.length -1)
  }

  def get[B >: A](i: Int): B
  def get[B >: A](i: Int, parentIndex: Int): B
}

Gruß

Dario

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Corpsegrinder,

um den Trauerspiel 😃 mal ein Ende zu machen, habe ich deine Aufgabe gelöst.

Dazu folgende Anmerkungen:

  • Dein Interface habe ich in IImmutableList <T> umbenannt, um einen Konflikt mit dem bestehenden Interface IList <T> aus System.Collections.Generic zu vermeiden.
  • Wenn ich die Liste aus deinem Beispiel erzeuge, bekommt die Wurzel den Index/Offset 3 und nicht 4. Ich denke, so ist es auch auch gemeint, denn in dem auf das Beispiel folgenden Text steht ja auch, dass sie "den Index dieses Elements in der Liste" bekommen soll. Im Kontext von C# würde ich davon ausgehen, dass damit der nullbasierte Index gemeint ist und der wäre ja im Beispiel 3.
  • Die Fehlerbehandlung in RemoveFirst und RemoveLast beruht darauf, dass das benutze RemoveAt fehlschlägt, wenn die Liste leer ist. Das könnte man sicher schöner machen. Auch die Fehlerbehandlung in Get ist sehr spartanisch.
  • Was die Multicore Systeme anbelangt: Wenn eine Liste immutable ist, also bei jeder Operation immer eine neue Liste erzeugt wird, die die Änderungen enthält, kann man gleiche eine normale, arraybasierte Liste nehmen. Man gewinnt durch einen binären Differenzbaum nichts, zumal ich die ändernden Operationen - genauso wie du - der Einfachheit halber so implementiert habe, dass aus dem Baum zuerst eine normale Liste erzeugt wird, die geändert wird und dann wieder in einen neuen Baum umgewandelt wird.

Aber das soll nun egal sein. Damit gibt es nun eine Lösung der Aufgabe. Und dass der Testcode im Main ohne Probleme durchgelaufen wird, spricht dafür, dass die Implementierung auch tatsächlich korrekt ist. (Ok, die ändernden Methoden habe ich nicht getestet, aber deren Implementierungen sind ja trivial).

Wenn kein Veto kommt, werde ich morgen eine neue Aufgabe stellen.

Hier noch der Code:



using System;
using System.Text;
using System.Collections.Generic;
using System.Diagnostics;

public interface IImmutableList <T> {
   int Count { get; }
   IImmutableList <T> Add (T item); // fügt das Item am Ende der Liste an
   IImmutableList <T> AddToHead (T item); // fügt das Item am Anfang der Liste an
   IImmutableList <T> RemoveFirst (); // entfernt das erste Element
   IImmutableList <T> RemoveLast (); // entfernt das letzte Element
   T Get (int index); // liefert das entsprechende Element zum Index
   String ToString (); // gibt für jedes Element ToString aus
}

public class BinaryDifferenceTreeList <T> : IImmutableList <T>
{
   #region Private Members

   private class Node
   {
      private T    _tValue;
      private int  _iOffset;
      private Node _nodeLeft;
      private Node _nodeRight;

      public Node (T tValue, int iOffset, Node nodeLeft, Node nodeRight)
      {
          _tValue    = tValue;
          _iOffset   = iOffset;
          _nodeLeft  = nodeLeft;
          _nodeRight = nodeRight;
      }

      public int Offset
      {
         get { return _iOffset; }
      }

      public T Value
      {
         get { return _tValue; }
      }

      public Node Left
      {
         get { return _nodeLeft; }
      }

      public Node Right
      {
         get { return _nodeRight; }
      }
   }

   private Node _root;

   private static Node ToTree (List <T> list, int iStart, int iLength, int iParentIndex) {
      if (iLength == 0) {
         return null;
      }
      int iCurrIndex = iStart + iLength / 2;
      return new Node (
         list [iCurrIndex],
         iCurrIndex - iParentIndex,
         ToTree (list, iStart,                   iLength       / 2, iCurrIndex),
         ToTree (list, iStart + 1 + iLength / 2, (iLength - 1) / 2, iCurrIndex)
      );
   }

   private List <T> ToList ()
   {
      List <T> list = new List <T> (_root == null ? 0 : _root.Offset * 2);
      ToList (_root, list);
      return list;
   }

   private static void ToList (Node node, List <T> list)
   {
      if (node == null) {
         return;
      }
      ToList (node.Left,  list);
      list.Add (node.Value);
      ToList (node.Right, list);
   }

   #endregion Private Members

   #region Public Members

   public BinaryDifferenceTreeList (List <T> list)
   {
      _root = ToTree (list, 0, list.Count, 0);
   }

   public int Count {
      get {
         if (_root == null) { return 0; }
         int iCount = 1;
         for (Node nodeCurr = _root; nodeCurr != null; nodeCurr = nodeCurr.Right) {
            iCount += nodeCurr.Offset;
         }
         return iCount;
      }
   }

   public T Get (int iIndex)
   {
      if (iIndex < 0) {
         throw new ArgumentOutOfRangeException ();
      }
      Node nodeCurr = _root;
      while (nodeCurr != null) {
         if (iIndex == nodeCurr.Offset) {
            return nodeCurr.Value;
         }
         iIndex -= nodeCurr.Offset;
         if (iIndex < 0) {
            nodeCurr = nodeCurr.Left;
         } else {
            nodeCurr = nodeCurr.Right;
         }
      }
      throw new ArgumentOutOfRangeException ();
   }

   public IImmutableList <T> Add (T tItem)
   {
      List <T> list = ToList ();
      list.Add (tItem);
      return new BinaryDifferenceTreeList <T> (list);
   }

   public IImmutableList <T> AddToHead (T tItem)
   {
      List <T> list = ToList ();
      list.Insert (0, tItem);
      return new BinaryDifferenceTreeList <T> (list);
   }

   public IImmutableList <T> RemoveFirst ()
   {
      List <T> list = ToList ();
      list.RemoveAt (0);
      return new BinaryDifferenceTreeList <T> (list);
   }

   public IImmutableList <T> RemoveLast ()
   {
      List <T> list = ToList ();
      list.RemoveAt (list.Count - 1);
      return new BinaryDifferenceTreeList <T> (list);
   }

   public override String ToString ()
   {
      List <T> list = ToList ();
      if (list.Count <= 0) { return ""; }

      StringBuilder sb = new StringBuilder ();
      String strDelimiter = ", ";

      foreach (T tValue in list) {
         sb.Append (tValue);
         sb.Append (strDelimiter);
      }
      sb.Length -= strDelimiter.Length;
      return sb.ToString ();
   }

   #endregion Public Members
}

static class App
{
   public static void Main (string [] astrArg)
   {
      List <int> list = new List <int> ();

      for (int i = 0 ; i <= 20; ++i) {
         BinaryDifferenceTreeList <int> tree = new BinaryDifferenceTreeList <int> (list);
         Console.WriteLine ("{0,2}: {1}", i, tree);

         Debug.Assert (tree.Count == i);

         for (int i2 = 0; i2 < i; ++i2) {
            Debug.Assert (tree.Get (i2) == i2 + 1);
         }

         try {
            tree.Get (-1);
            Debug.Assert (false);
         }
         catch (ArgumentOutOfRangeException) {
            Debug.Assert (true);
         }
         catch (Exception) {
            Debug.Assert (false);
         }

         try {
            tree.Get (i);
            Debug.Assert (false);
         }
         catch (ArgumentOutOfRangeException) {
            Debug.Assert (true);
         }
         catch (Exception) {
            Debug.Assert (false);
         }

         list.Add (i+1);
      }
   }
}

herbivore

C
401 Beiträge seit 2007
vor 13 Jahren

Hi herbivore,

keine Einwände.

Gruß

Dario

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Corpsegrinder, hallo zusammen,

ok, dann wird es jetzt ein bisschen kniffelig. 😃

Bei den zurückliegenden Aufgaben schien es mir meistens einen Wettlauf darum zu geben, wer am schnellsten eine Lösung postet. Das ging dann mitunter zulasten der Korrektheit. Bei der nun folgenden Aufgabe steht die Korrektheit im Vordergrund. Postet also bitte nicht vorschnell, sondern überlegt genau und in Ruhe, ob eure Lösung wirklich korrekt ist.

Die Aufgabe ist die Klasse [url]SyncQueue <T> - Eine praktische Job-Queue[/url] so zu erweitern, dass nicht nur Dequeue blockiert, wenn die Queue leer ist, sondern auch Enqueue, wenn die Queue voll ist. Um bestimmen zu können, wann die Queue voll ist, soll eine änderbare Property MaxSize eingeführt werden. MaxSize == 0 soll bedeuten, dass es keine Beschränkung gibt. In diesem Fall soll sich die neue SyncQueue genauso verhalten wie die jetzige.

Obwohl eine vollständige Lösung in 50 Zeilen möglich ist, liegen ziemlich viele Fallstricke in der Aufgabe. Mehr als man denkt! Der Reiz der Aufgabe liegt darin, keinen der Fallstricke zu übersehen.

Ich will nicht in die Details gehen, aber natürlich dürfen keine Deadlocks vorkommen und anderseits muss die Synchronisation in allen Fällen 100%ig wasserdicht erfolgen. Um ein Gefühl zu bekommen, was für Konstellationen man dabei durchdenken muss, schaut euch mal diesen Beitrag an SyncQueue <T> - Eine praktische Job-Queue.

Um nur ein Beispiel für einen Fallstrick zu geben: Mit einer Abfrage wie if (_q.Count == MaxSize) kann man leicht auf die Nase fallen, wenn MaxSize nachträglich auf einen Wert gesetzt wird, der kleiner ist als die Anzahl der schon in der Queue enthaltenen Elemente. Und das soll durchaus erlaubt sein. Die Queue gilt als voll, wenn die Anzahl der Elemente größer oder gleich der durch MaxSize angegebenen Schranke ist. Achtung: Die letzte Formulierung ist etwas gespreizt, weil hier schon der nächste Fallstrick lauert.

Um es nochmal zu sagen, es geht darum, eine robuste, threadsichere und blockierende Klasse mit den zwei Methoden Enqueue und Dequeue sowie der änderbaren Property MaxSize zu schreiben, die in allen denkbaren Anwendungsfällen und Szenarien korrekt funktioniert. Nicht einfach aber machbar!

Mit meinem Drängen auf Korrektheit möchte ich euch fordern, nicht abschrecken. Man kann viel daraus lernen, wenn man hier wirklich versucht, gründlich zu arbeiten. Wenn ihr euch nicht 100%ig sicher seid, könnt ihr mir eure Lösung auch gerne vorab per PM schicken.

herbivore

C
401 Beiträge seit 2007
vor 13 Jahren

Hi herbivore,

ich habe mal eine Lösung erstellt. Ich hoffe sie entspricht deinen Anforderungen.



using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;

namespace SyncQueueTest
{

	//*****************************************************************************
	public class SyncQueue <T>
	{
		   //--------------------------------------------------------------------------
		private Queue <T> _q   = new Queue <T> ();
		public int MaxSize { get; set; }
		public SyncQueue (int maxSize)
		{
			MaxSize = maxSize;
		}
	
		//==========================================================================
		// <summary>
		// Trägt einen Eintrag und wartet dabei nötigenfalls
	  // solange bis wieder Platz vorhanden ist.
		// </summary>
		public void Enqueue (T tItem)
		{
			lock (this) {
				while (_q.Count >= MaxSize && MaxSize != 0) {
					Debug.WriteLine (Thread.CurrentThread.Name + " Wait");
					Monitor.Wait (this);
				}
				_q.Enqueue (tItem);
				Monitor.Pulse (this);
				Debug.WriteLine (Thread.CurrentThread.Name + " Enqueue ==> " + _q.Count);
			}
		}
	
	   //==========================================================================
	   // <summary>
	   //    Holt einen Eintrag aus der Queue heraus und wartet dabei nötigenfalls
	   //    solange bis wieder ein Eintrag vorhanden ist.
	   // </summary>
	   public T Dequeue ()
	   {
	      lock (this) {
	         while (_q.Count == 0) {
	            Debug.WriteLine (Thread.CurrentThread.Name + " Wait");
	            Monitor.Wait (this);
	         }
			 Monitor.Pulse(this);
	         Debug.WriteLine (Thread.CurrentThread.Name + " Dequeue ==> " + (_q.Count - 1));
	         return _q.Dequeue ();
	      }
	   }
	}
}


Habe das ganze getestet, indem ich vorab die Liste gefüllt habe, danach die MaxSize drastisch verringert habe und dann einfach deinen ursprünglichen Test habe laufen lassen. Lief bei mir ohne Probleme durch.

Gruß

Dario

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Corpsegrinder,

sorry, nein, ich finde auf Anhieb (wobei ich mich allerdings schon länger mit dem Problem an sich beschäftigt habe) vier Stellen, an denen es nicht passt, was klemmt oder schief geht. Wie gesagt, es ist nicht ganz einfach und mit Testen kann man hier ganz, ganz schlecht die Abwesenheit von Fehlern feststellen.

Ich möchte noch nicht verraten, wo die Probleme liegen, weil der Reiz dieser Aufgabe in meinen Augen in gerade im Knobeln und im Kniffligen liegt. Man muss das Ganze wirklich tief durchdenken. Man muss, wie in dem o.g. Link exemplarisch beschrieben, versuchen, einen möglichst bösartigen Benutzer und zusätzlich einen möglichst fiesen Scheduler zu spielen. Der Benutzer führt die Aufrufe in möglichst böser Reihenfolge in einer vertrackten Umgebung von Threads aus und der Scheduler zerhackt das Ganze noch in möglichst ungünstige Häppchen und wechselt zum jeweils unpassendsten Thread. Und dann muss immer noch alles stimmen.

Den bösen Benutzer kann man natürlich auch in Form von gemeinen Testprogrammen "spielen". Aber den bösen Scheduler kann man bei einem Test, bei dem man das Programm einfach laufen lässt, gar nicht oder nur sehr, sehr schwer simulieren. Das geht weit besser im Kopf.

Das Angebot mit der PM steht weiterhin.

herbivore

PS: Wer selbst fiesen Scheduler spielen möchte, kann das - für mehrere andere Synchronisierungsaufgaben - auf der extrem coolen Seite The Deadlock Empire - Slay dragons, master concurrency! tun. Per Knopfdruck kann man dort bestimmen, welcher Thread die jeweils nächste Anweisung ausführen soll und man sieht quasi wie im Debugger sofort, wie sich daraufhin der Programmzustand ändert. Dabei ist es (Spiel-)Ziel, die (jeweils nicht korrekt implementierte) Synchronisierung auszutricksen oder das Programm in einen Ausnahmezustand zu versetzen.

1.130 Beiträge seit 2007
vor 13 Jahren

Jetzt weiß ich, wozu es semaphores gibt.
Dashier ist der 2. Versuch, dank an herbivore, der mich davon abgehalten hat waithandles zu verwenden, dashier ist auchnoch deutlich schneller als der erste versuch.
Dass weder monitor noch lock vorkommt hat damit zutun, dass es auf meiner Lockfreie threadsichere Queue beruht


    class SyncQueue<T>
    {
        public SyncQueue(int capacity)
        {
            first = new Node();
            last = first;
            deQueueableS = new Semaphore(0, capacity);
            enQueueableS = new Semaphore(capacity, capacity);
        }

        Semaphore deQueueableS;
        Semaphore enQueueableS;
        Node first;
        Node last;

        public void Enqueue(T item)
        {
            enQueueableS.WaitOne();
lock(this)
{
            Node newNode = new Node();
            newNode.item = item;
            Node old = first;
            first= newNode;
            old.next = newNode;
            deQueueableS.Release();
}
        }

        public T Dequeue()
        {
            deQueueableS.WaitOne();
            Node current;
            do
            {
                current = last;
            }
            while (current != Interlocked.CompareExchange(ref last, current.next, current));
            enQueueableS.Release();
            return current.next.item;
        }

        class Node
        {
            public T item;
            public Node next;
        }
    }

EDIT:Solange man nur einen geberthread hat war alles soweit ok.
sobald ein zweiter thread gibt, kann es passieren, dass ein element noch garnicht zur verfügung steht. hab das mit nem lock gefixt (unschön in meinen augen aber naja...)

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

1.361 Beiträge seit 2007
vor 13 Jahren

Hi Floste,

änderbare Property MaxSize

😉

Ich hab mich ja auch daran probiert, und genau dieses änderbar ist der wunde Punkt.

beste Grüße
zommi

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Floste,

leider ist schon die Abwesenheit der MaxSize-Property ein KO-Kriterium. 😦

Ansonsten ist es ein sehr interessanter Ansatz, eine lockfreie Queue und zwei Semaphoren zu einer blockierenden Queue zu verbinden. 😃

herbivore

1.130 Beiträge seit 2007
vor 13 Jahren
    class SyncQueue<T>
    {
        public SyncQueue(int capacity)
        {
            this.capacity=capacity;
            first = new Node();
            last = first;
            deQueueableS = new Semaphore(0, int.MaxValue);
            enQueueableS = new Semaphore(capacity, int.MaxValue);
        }

        int capacity;
        public int MaxSize
        {
            get
            {
                return capacity;
            }
            set
            {
                ModifyCapacity(value-this.capacity);
                this.capacity=value;
            }
        }

        Semaphore deQueueableS;
        Semaphore enQueueableS;
        Node first;
        Node last;

        public void Enqueue(T item)
        {
            enQueueableS.WaitOne();
lock(this)
{
            Node newNode = new Node();
            newNode.item = item;
            Node old = first;
            first= newNode;
            old.next = newNode;
            deQueueableS.Release();
}
        }

        public T Dequeue()
        {
            deQueueableS.WaitOne();
            Node current;
            do
            {
                current = last;
            }
            while (current != Interlocked.CompareExchange(ref last, current.next, current));
            enQueueableS.Release();
            return current.next.item;
        }

        class Node
        {
            public T item;
            public Node next;
        }

void ModifyCapacity(int change)
{
    if(change>0) enQueueableS.Release(change);
    else
    {
        for(int i=-change;i != 0; i--) enQueueableS.WaitOne();
    }
}
    }

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Floste,

hehe, jetzt aber bitte nicht Schlag auf Schlag posten, bis es stimmt. Momentan ist zumindest noch nicht der Fall berücksichtigt, dass mehrere Threads die MaxSize-Property gleichzeitig ändern. Nach möglichen weiteren Problemen hab ich noch nicht geschaut.

herbivore

1.130 Beiträge seit 2007
vor 13 Jahren

So: MaxSize Threadsicher gemacht und das Warten, bis die entfernten Plätze wieder frei sind ins Enqueue verlegt.


    public class SyncQueue<T>
    {
        public SyncQueue(int capacity)
        {
            this.capacity = capacity;
            first = new Node();
            last = first;
            deQueueableS = new Semaphore(0, int.MaxValue);
            enQueueableS = new Semaphore(capacity, int.MaxValue);
        }

        int capacity;
        public int MaxSize
        {
            get
            {
                return capacity;
            }
            set
            {
                int change = value - Interlocked.Exchange(ref this.capacity,value);
                if (change > 0) enQueueableS.Release(change);
                else Interlocked.Add(ref oversize, -change);
            }
        }

        int oversize = 0;

        Semaphore deQueueableS;
        Semaphore enQueueableS;
        Node first;
        Node last;

        public void Enqueue(T item)
        {
            enQueueableS.WaitOne();
            while (true)
            {
                int cachedOversize = oversize;
                if (cachedOversize <= 0) break;
                if (Interlocked.CompareExchange(ref oversize, cachedOversize - 1, cachedOversize) == cachedOversize)
                    enQueueableS.WaitOne();//Platz wurde dauerhaft entfernt. Da aber immernoch das Item eingefügt werden soll, muss eine neuer reserviert werden.
            }
            lock (this)//hinzufügen
            {
                Node newNode = new Node();
                newNode.item = item;
                Node old = first;
                first = newNode;
                old.next = newNode;
                deQueueableS.Release();
            }
        }

        public T Dequeue()
        {
            deQueueableS.WaitOne();
            Node current;
            do current = last;
            while (current != Interlocked.CompareExchange(ref last, current.next, current));
            enQueueableS.Release();
            return current.next.item;
        }

        class Node
        {
            public T item;
            public Node next;
        }
    }

hehe, jetzt aber bitte nicht Schlag auf Schlag posten, bis es stimmt.

Das mit der änderbaren maxsize hatte ich übersehen. Dann hatte ich erstmal was tzusammengehackt, um es änderbar zu machen. Jetzt habe ich es threadsicher versucht zu machen. Aber warum soll ich den code nicht verbessern, bis er stimmt?

Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Floste,

Aber warum soll ich den code nicht verbessern, bis er stimmt?

das sollst du ja. Es ging nur darum, dass du bitte nicht jeden Zwischenstand postetet. Aus meiner Sicht hätten die Schritte ...

Dann hatte ich erstmal was tzusammengehackt, um es änderbar zu machen. Jetzt habe ich es threadsicher versucht zu machen.

... zusammengehört, weil ja von vornherein klar war, dass es nicht darum ging, was "zusammenzuhacken", sondern was wirklich threadsicheres, korrektes und robustes abzuliefern. Aber sei es drum. 😃

Das threadsichere hast du nachgereicht (zumindest habe ich auf die Schnelle nichts offensichtliches schiefes gefunden). Die Korrektheit und Robustheit fehlt in meinen Augen noch an zwei Stellen.

Korrektheit: So weit ich das sehe, ist folgender Fall noch nicht berücksichtigt:

MaxSize == 0 soll bedeuten, dass es keine Beschränkung gibt.

Robustheit: Darunter fällt für mich, dass Eingabewerte darauf geprüft werden, ob sie in einem sinnvollen Bereich liegen, bzw. dass mit Werten außerhalb des sinnvollen Bereichs sinnvoll umgegangen wird.

Ich finde es interessant, dass der zunächst so elegante Ansatz durch die zusätzlichen Anforderungen ziemlich "ausgebeult" wird. Ich hatte, als ich die Aufgabe gestellt habe, eine Erweiterung im Sinn, die näher am Original liegt. Und bei der lassen sich alle genannten Anforderung viel leichter "unterbringen".

Hallo zusammen,

vielleicht versucht sich ja noch jemand an einer Lösung, die in die Richtung geht, die Corpsegrinder eingeschlagen hat.

herbivore

49.485 Beiträge seit 2005
vor 13 Jahren

Hallo zusammen,

vielleicht versucht sich ja noch jemand an einer Lösung, die in die Richtung geht, die Corpsegrinder eingeschlagen hat.

Ich möchte noch nicht verraten, wo die Probleme liegen, weil der Reiz dieser Aufgabe in meinen Augen in gerade im Knobeln und im Kniffligen liegt.

nachdem ihr nun eine Menge Zeit zum Knobeln "im eigenen Saft" hattet, will ich jetzt die zweite Stufe zünden und die Fallstricke, die ich (bei dem Lösungsansatz, den Corpsegrinder gewählt hat und der auch mir vorschwebt) sehe, doch verraten. Die Reihenfolge der Fallstricke ist willkürlich. Sie dient nur dazu, die einzelnen Punkte eindeutig identifizieren zu können:

Fallstrick 1:

Wertebereich von MaxSize: Zu einem robusten Programm gehört- wie schon im vorigen Beitrag gesagt, "dass Eingabewerte darauf geprüft werden, ob sie in einem sinnvollen Bereich liegen, bzw. dass mit Werten außerhalb des sinnvollen Bereichs sinnvoll umgegangen wird."

Fallstrick 2:

Zusätzlich zur allgemeinen Berücksichtigung des Wertebereichs, muss man den Speziallfall, dass MaxSize == 0 keine Beschränkung bedeutet, überall berücksichtigen.

Fallstrick 3: (den ich ja schon weiter oben genannt habe)

Wenn MaxSize verringert wird, kann es sein, dass die Queue "übervoll" ist. Das muss man bei der Formulierung der Abfrage, ob die Queue voll ist, berücksichtigen.

Fallstrick 4:

Man muss den Fall berücksichtige, dass möglicherweise wartende Enqueues weiterarbeiten können bzw. müssen, wenn MaxSize "vergrößert" wird (hier auch an Fallstrick 2 denken). Unabhängig davon, ob die Queue nur voll oder übervoll ist.

Fallstrick 5:

Man muss verhindern, dass durch Caching MaxSize in verschiedene Threads verschiedenen Werte hat.

Fallstrick 6:

Nicht nur die Zugriffe Enqueue und Dequeue müssen threadsafe sein, sondern auch die auf MaxSize (und dabei reicht es nicht unbedingt, dass MaxSize sich als int atomar ändern lässt).

Fallstricke 7 und 8: (besonders tricky)

Bei einem Enqueue muss dafür gesorgt werden, dass ein evtl. schon wartendes Dequeue weiterlauft. Und umgekehrt. Man könnte denke, dass das Pulse im Enqueue und im Dequeue genau das tut. Aber schaut euch mal diesen Fall an:

  1. Stand: Zwei Consumer, zwei Producer, Queue leer, keiner wartet auf die Sperre, keiner im Wait-Status, MaxSize == 1
  2. Consumer1 Dequeue: betritt die Sperre (bei lock) und läuft - da die Queue leer ist - aufs Wait (wodurch er in den Wait-Status geht und die Sperre wieder frei ist)
  3. Consumer2 Dequeue: betritt die Sperre (bei lock) und läuft - da die Queue leer ist - aufs Wait (wodurch er in den Wait-Status geht und die Sperre wieder frei ist)
  4. ProducerA Enqueue: betritt die Sperre (bei lock), aber dann erfolgt zufällig ein Threadwechsel, bevor das Pulse erreicht wurde
  5. ProducerB Enqueue: versucht die Sperre zu betreten, aber da ist ja ProducerA drin, also wartet ProducerB auf die Sperre (bei lock)
  6. ProducerA läuft weiter und führt das Pulse aus
  7. Dadurch wartet Consumer1 wieder auf die Sperre (bei Wait), stellt sich also hinter dem schon wartenden ProducerB an.
  8. ProducerA verlässt die Sperre
  9. Stand: Ein Item in der Queue, ProducerB und Consumer1 warten in dieser Reihenfolge auf die Sperre, Consumer2 wartet im Wait-Status
  10. ProducerB betritt die Sperre (bei lock), und läuft - da die Queue voll ist - aufs Wait (wodurch er in den Wait-Status geht und die Sperre wieder frei ist)
  11. Stand: Ein Item in der Queue, Consumer1 wartet auf die Sperre, Consumer2 und ProducerB warten in dieser Reihenfolge im Wait-Status
  12. Consumer1 betritt die Sperre (bei Wait), holt das von ProducerA eingestellt Element ab und und führt das Pulse aus
  13. Dadurch wartet Consumer2 wieder auf die Sperre (bei Wait). Vor ihm steht keiner.
  14. Consumer1 verlässt die Sperre
  15. Stand: Queue leer, Consumer2 wartet auf die Sperre, ProducerB wartet im Wait-Status
  16. Consumer2 betritt die Sperre (bei Wait) und läuft - da die Queue leer ist - aufs Wait (wodurch er in den Wait-Status geht und die Sperre wieder frei ist)
  17. Stand: Queue leer, keiner wartet auf die Sperre, ProducerB und Consumer2 warten in dieser Reihenfolge (für immer) im Wait-Staus, obwohl ProducerB und danach auch Consumer2 arbeiten könnte

Das Problem ist, dass in Schritt 12 durch das Pulse von Consumer1 fälschlich Consumer2 aufgeweckt wird und nicht wie beabsichtigt ProducerB. Und da der aufgeweckte Consumer2 auf eine leere Queue trifft, schläft er gleich wieder ein, wodurch das Pulse effektiv verloren ist.

Solche Fälle sind es, die die Aufgabe in meinen Augen so spannend machen. Solche Fälle muss man im Blick haben, wenn man sich überlegt, ob die eigene Lösung korrekt ist.

Fallstrick 9 (auch schon bekannt):

Statt einer if-Abfrage um die Waits, muss eine while-Schleife verwendet werden. Siehe den Fall in SyncQueue <T> - Eine praktische Job-Queue.

Damit habe ich die Fallstricke genannt, die man beachten muss. Ich habe absichtlich nicht gesagt, was man tun kann oder tun muss, um die Fallstricke zu umgehen.

Wem gelingt es mit dem Gesagten, eine fehlerfreie und robuste Implementierung hinzubekommen?

herbivore

C
401 Beiträge seit 2007
vor 13 Jahren

So, hier nun die von herbivore abgesegnete Lösung 😉



using System;
using System.Collections.Generic;
using System.Threading;
using System.Diagnostics;

namespace SyncQueueTest
{

	//*****************************************************************************
	public class SyncQueue <T>
	{
		   //--------------------------------------------------------------------------
		private Queue <T> _q   = new Queue <T> ();
		private volatile int _maxSize;
		public int MaxSize { 
			get { 
				return _maxSize; 
			} 
			set {
				lock(this) {
					if(value < 0) value = 0;
					int oldSize = _maxSize;
					_maxSize = value;
					if(_maxSize > oldSize || _maxSize == 0)
						Monitor.PulseAll(this);
				}
			} 
		}
		
		public SyncQueue (int maxSize)
		{
			MaxSize = maxSize;
		}
	
		//==========================================================================
		// <summary>
		// Trägt einen Eintrag und wartet dabei nötigenfalls
	  // solange bis wieder Platz vorhanden ist.
		// </summary>
		public void Enqueue (T tItem)
		{
			lock (this) {
				while (_q.Count >= MaxSize && MaxSize != 0) {
					Debug.WriteLine (Thread.CurrentThread.Name + " Wait");
					Monitor.Wait (this);
				}
				_q.Enqueue (tItem);
				Monitor.PulseAll(this);
				Debug.WriteLine (Thread.CurrentThread.Name + " Enqueue ==> " + _q.Count);
			}
		}
	
	   //==========================================================================
	   // <summary>
	   //    Holt einen Eintrag aus der Queue heraus und wartet dabei nötigenfalls
	   //    solange bis wieder ein Eintrag vorhanden ist.
	   // </summary>
	   public T Dequeue ()
	   {
	      lock (this) {
	         while (_q.Count == 0) {
	            Debug.WriteLine (Thread.CurrentThread.Name + " Wait");
	            Monitor.Wait (this);
	         }
			 Monitor.PulseAll(this);
	         Debug.WriteLine (Thread.CurrentThread.Name + " Dequeue ==> " + (_q.Count - 1));
	         return _q.Dequeue ();
	      }
	   }
	}
}


49.485 Beiträge seit 2005
vor 13 Jahren

Hallo Corpsegrinder,

So, hier nun die von herbivore abgesegnete Lösung 😉

richtig, ich hatte dir schon per PM bestätigt, dass ich die Lösung als korrekt ansehe.

Ich hoffe du bist mir nicht böse, wenn ich noch zwei winzige Schönheitfehler nenne, die mir aufgefallen sind. 😃 Zum einen die unnötige Zwischenvariable oldSize und zum anderen das unnötige PulseAll, wenn MaxSize von 0 auf 0 gesetzt wird. Aber wie ich selbst vorgegeben habe:

Eine Aufgabe gilt als gelöst, wenn der Code das vorgegebene Problem löst, egal wie wie gut oder schlecht der Programmierstil ist.

Und der Programmierstil ist insgesamt gar nicht übel. Egal wie gut man etwas macht, es geht fast immer noch ein bisschen besser. 😃

Du bist mit der nächsten Aufgabe dran!

herbivore

C
401 Beiträge seit 2007
vor 13 Jahren

Und der Programmierstil ist insgesamt gar nicht übel. Egal wie gut man etwas macht, es geht fast immer noch ein bisschen besser. 😃

Danke 😉, muss auch sagen, dass ich aus C# voll raus bin, da ich momentan fast nur noch mit Scala oder Objective-C arbeite. Und Concurrency unter C# habe ich auch noch nicht gemacht. Naja.. nun mal zu meiner nächsten Aufgabe:

Es soll eine möglichst performante Matrix-Klasse erstellt werden. Es sollen die normalen Matrix-Operationen (+, -, * und ^) implementiert werden. Wichtig ist, dass die Matrix absolut Threadsafe und alle Methoden pure sind (d.h. egal wie oft man sie aufruft, es kommt immer das gleiche Ergebnis heraus). Achso... eine schicke ToString() ist natürlich auch gerne gesehen 😉

2.921 Beiträge seit 2005
vor 13 Jahren

Dazu habe ich noch eine paar Fragen @Corpsegrinder

Ich stelle die Fragen mal hier öffentlich, weil ich denke dass mehrere Leute hier die gleichen Fragen haben könnten.

Es soll eine möglichst performante Matrix-Klasse erstellt werden.

Heißt möglichst performant elegant mathematisch mit möglichst wenigen Rechenoperationen oder heißt das zusätzlich noch parallele Berechnungen per Threads wenn mehrere benutzt werden?

Es sollen die normalen Matrix-Operationen (+, -, * und ^) implementiert werden.

Heißt hier ^ potenzieren oder meinst Du damit etwas anderes?

Wichtig ist, dass die Matrix absolut Threadsafe und alle Methoden pure sind (d.h. egal wie oft man sie aufruft, es kommt immer das gleiche Ergebnis heraus).

Heißt das wirklich "pure"? Ich kenne das als idempotent (kann mich auch irren). 😉

Achso... eine schicke ToString() ist natürlich auch gerne gesehen 😉

Wie soll ausgegeben werden? Ich meine in welchem Format.

Stellst Du Dir da so was vor:

3 5 2
4 3 1
3 4 2

oder etwas anderes?

Oder meinst Du gar eine Matrix aus der Prädikatenlogik? Das wäre dann etwas ganz anderes IMHO als die mathematische Variante.

Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.