Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

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
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von m0rius am .
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo Morius,

das sieht korrekt aus. Du bist dran.

Gruß, MarsSTein
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
Campac68
myCSharp.de - Member



Dabei seit:
Beiträge: 68

beantworten | zitieren | melden

tja ich sags mal so: versuch wars wert ich hatte nich viel zeit und war todmüde;)
beim nächsten mal!
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von m0rius am .
Mein Blog: blog.mariusschulz.com
Hochwertige Malerarbeiten in Magdeburg und Umgebung: M'Decor, Ihr Maler für Magdeburg
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

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!
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 4 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

Hallo zusammen,
Zitat
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
private Nachricht | Beiträge des Benutzers
m0rius
myCSharp.de - Member

Avatar #avatar-3125.png


Dabei seit:
Beiträge: 1043

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

*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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Floste am .
Attachments
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
der-schlingel
myCSharp.de - Member

Avatar #avatar-3239.jpg


Dabei seit:
Beiträge: 820
Herkunft: Österreich/Wien

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

        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 ;-)
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal am .
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
Gelöschter Benutzer

beantworten | zitieren | melden

Zitat
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]
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Geht bestimmt schöner, aber funktioniert :D


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
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Corpsegrinder am .
private Nachricht | Beiträge des Benutzers
Campac68
myCSharp.de - Member



Dabei seit:
Beiträge: 68

beantworten | zitieren | melden

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^^
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3429
Herkunft: Trier -> München

beantworten | zitieren | melden

Hallo,
Zitat von Campac68
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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

So, ich hol den Thread mal wieder hoch, damit er nicht verloren geht ;-)
Zitat von herbivore
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
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

Hi herbivore,

keine Einwände.


Gruß

Dario
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 416

beantworten | zitieren | melden

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
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von Corpsegrinder am .
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 52329
Herkunft: Berlin

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Floste
myCSharp.de - Member

Avatar #avatar-2376.jpg


Dabei seit:
Beiträge: 1158
Herkunft: Norddeutschland

beantworten | zitieren | melden

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...)
Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von Floste am .
Projekte:Jade, HttpSaver
Zum Rechtschreiben gibts doch schon die Politiker. Aber die bauen auch nur mist!
private Nachricht | Beiträge des Benutzers
zommi
myCSharp.de - Member

Avatar #avatar-2617.png


Dabei seit:
Beiträge: 1380
Herkunft: Berlin

beantworten | zitieren | melden

Hi Floste,
Zitat von herbivore
änderbare Property MaxSize
;-)

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

beste Grüße
zommi
private Nachricht | Beiträge des Benutzers