[.NET] Generics und Operatorüberladung

[Medium]

Moinmoin!

Ich implementiere gerade eine Matrix-Klasse in C#, und brauche diese mit generischem Typ. Hintergrund ist, dass eine Matrix wiederum Matrizen als Elemente beinhalten können muss, dies aber nicht zwangsweise tut. Es kommen also auch normale Typen wie Double oder Integer vor.
Das Problem hier ist nun, dass der Compiler (zurecht) meckert, dass die Operatoren die ich da überlade nicht unbedingt für den Typ <T> vorhanden sind. Ich suche nun also eine Möglichkeit, dem Compiler klar zu machen, dass dort lediglich Typen kommen, für die die Operatoren sehr wohl definiert sind.

Hier mal mein grobes Codegerüst (unwichtigen Krams ausgelassen):

Code:

   
public class Matrix<T>
{
   private T[,] M;
   
   public Matrix(int sizeX, int sizeY)
   {
      M = new T[sizeX, sizeY];
   }
   
   public Matrix(T[,] init)
   {
      M = (T[,])init.Clone();
   }
   
   // Und hier knallt es dann natürlich, da nicht alle Nachkommen von Object + rechnen können
        public static Matrix<T> operator +(Matrix<T> a, Matrix<T> b)
   {
      if ((a.XDimension != b.XDimension) || (a.YDimension != b.YDimension)) throw new ArrayTypeMismatchException("Operation + on mismatching matrices");
      else{
         Matrix<T> t = new Matrix<T>(a.XDimension, a.YDimension);
         for (int x=0; x<t.XDimension; x++)
            for (int y=0; y<t.YDimension; y++)
               t[x, y] = a[x, y] + b[x, y];
         return t;
      }
   }
}

Ich habe bis jetzt kein Interface oder Constraint gefunden, mit dem ich das realisieren kann. Gibbets da wat?

[Dax]

Nein. Du musst einen Wrapper (Structs, die nur deinen Typen enthalten, bieten sich da an) definieren, der ein entsprechendes Interface implementiert.

add: Diese Structs haben dann idealerweise implizite Konversionen zum/vom gewrapten Typ, dann merkt man das (fast) nicht, nur bei der Deklaration der Matrix.

[Elvis]

Zitat:

Zitat von Dax

Nein. Du musst einen Wrapper (Structs, die nur deinen Typen enthalten, bieten sich da an) definieren, der ein entsprechendes Interface implementiert.
add: Diese Structs haben dann idealerweise implizite Konversionen zum/vom gewrapten Typ, dann merkt man das (fast) nicht, nur bei der Deklaration der Matrix.

ValueTypes, die in Interfaces geboxt werden, werden aber leider... geboxt. ;-)
Es wird sich wohl eher lohnen Klassen für den Wrapper herzunehmen.
man kann es auch so lösen, dass du Delegates für einen Satz T hinterlegst, die wiederum den Code des Operators enthalten.
Mit ein paar Tricks kostet dich das fast gar nix zur Laufzeit.

Ich muss jetzt aber los, vllt kann ich es vor Montag noch genauer zeigen...

[Medium]

Verdammt, ich bin auch gerade auf diverse Seiten gestoßen wo sich groß darüber ausgelassen wird, dass das ein riesen Leck in C# ist. Seit Jahren schon, und trotz vieler vorgeschlagener Wege das zu umgehen, ist keiner davon für mich wirklich geeignet (bzw. die die es wären, sind teils vollständige Parser mit 1000+ Zeilen... zu langsam, zu komplex - Sitchwort LINQ).

Warum zum Geier stoße ich bei Fun-Projekten immer schon nach unter einer Stunde an die Grenzen meiner Tools? :stupid:

Ein einfaches Interface "IArithmetic" dass alle numerischen Typen implementieren wäre doch so eine tolle Sache. Aber Dax, was du da vorschlägst klingt nicht uninteressant, jedoch habe ich gerade keine Vorstellung davon wie das in Code gegossen aussehen könnte. (Ich bin noch nicht allzu geübt in C#.) Magst du mir ein kurzes strukturelles Beispiel zeigen?

\\Edit: Elvis' roter Kasten is kaputt :)
Um ehrlich zu sein wäre Boxing ein vergleichsweise kleiner Tradeoff. Wie sähe sowas aus? Auch die Variante mit den Delegates klingt nicht unspannend!
Einfach wäre es ja, wenn T nur von mir erstellte Typen beinhalten würde. Irgendwie muss ich da nur noch die primitiven mit rein kriegen...

[Dax]

Zitat:

Zitat von Elvis

ValueTypes, die in Interfaces geboxt werden, werden aber leider... geboxt. ;-)
Es wird sich wohl eher lohnen Klassen für den Wrapper herzunehmen.

Wenn er schon mehrdimensionale Arrays benutzt, tut das Boxen auch nicht mehr weh ;) Davon abgesehen werden Interfacecalls auf Valuetypes meiner Erinnerung nach doch in ein load address + static call übersetzt? Zumindest macht der gmcs das so ;)

[Dax]

Ein Beispiel für beides:

Code:

interface IArithmetic<T, V>
{
   T Add(T left, T right);
   V Value {
      get;
      set;
   }
}

struct DoubleArithmetic : IArithmetic<DoubleArithmetic, double>
{
   public double Value {
      get;
      set;
   }

   public DoubleArithmetic Add(DoubleArithmetic left, DoubleArithmetic right)
   {
      return new DoubleArithmetic { Value = left.Value + right.Value };
   }

   public static implicit operator DoubleArithmetic(double value)
   {
      return new DoubleArithmetic { Value = value };
   }

   public static implicit operator double(DoubleArithmetic da)
   {
      return da.Value;
   }
}

class Combiner<T>
{
   public Func<T, T, T> Add {
      get;
      private set;
   }

   public Combiner(Func<T, T, T> _add)
   {
      Add = _add;
   }
}

public class MainClass
{
   static void test<T, V>(V inc) where T : IArithmetic<T, V>, new()
   {
      var d = DateTime.Now;
      T da = new T();
      int max = 10000000;
      for (int i = 0; i < max; i++) {
         da = da.Add(da, new T { Value = inc });
      }
      Console.WriteLine((DateTime.Now - d).TotalMilliseconds / max * 1000000);
   }
   
   static void test2<T>(T inc, Combiner<T> ops) where T: new()
   {
      var d = DateTime.Now;
      T da = new T();
      int max = 10000000;
      for (int i = 0; i < max; i++) {
         da = ops.Add(da, inc);
      }
      Console.WriteLine((DateTime.Now - d).TotalMilliseconds / max * 1000000);
   }

   public static void Main(string[] args)
   {
      test<DoubleArithmetic, double>(1.0);
      test2<double>(1.0, new Combiner<double>((a, b) => a + b));
   }
}

Wobei ich die Delegate-Variante im Nachhinein doch eleganter finde. Schneller ist sie auch, was mich nicht sehr wundert ;)

[Medium]

Beide Varianten führen letztlich leider nicht zu dem, was ich mir so vorgestellt hatte. Mir ist es am wichtigsten, dass die Anwendung von Operatoren auf die Klasse Matrix am Ende so simpel ist wie auf primitive Datentypen. Der Grund ist, dass die Formeln die diese Matrizen enthalten an und für sich schon komplex genug sind, so dass formales "Rumgehampel" hier zu totaler Unübersichtlichkeit führen würde.

Ich möchte einfach "P = M*(A+B)" schreiben können, egal ob die Elemente der einzelnen Matrizen nun vom Typ double, int oder Matrix sind. Und für den Fall dass eine nicht lösbare Konstruktion auftritt (wenn z.B. Matrix+double auftaucht), würde ich das am liebsten via Exception aus dem entsprechenden Operator heraus abfangen. Insbesondere die Version mit dem Interface (die mir an sich gut gefiel) hat das Problem, dass Interfaces keine Operatoren vorschreiben können :(
Das erklärt nun auch, warum es nicht schon längst ein IArithmetic Interface gibt.

Ich fürchte ich werde es ganz hässlich lösen müssen: Da maximal eine Matrix von Matrizen von Doubles auftauchen kann (keine tiefere Verschachtelung), werde ich wohl doch 2 Matrix-Klassen nehmen. Eine für double, eine für Matrix. Das wird nur etwas interessanter bei den Operatoren, die dann eine Fülle an Kombinationen von Parametern bedenken müssen.
Es sei denn es lässt sich nicht doch eleganter lösen!

Danke euch beiden schon mal kräftig!

[Dax]

Wenn du dir eine MatrixFactory<T> definierst, die einen Combiner<T> als Konstruktorargument verlangt und eine Methode hat, die Matrizen erstellt und denen auch gleich den Combiner mitgibt, kannst du wunderbar Operatoren auf die Matrizen und deren Elementtypen definieren ;)

[Medium]

:freak: Ooookay, klingt toll, aber bis ich das verstanden und umgesetzt habe dürfte es .NET 10 geben ;). Das ärgerliche ist für mich grad, dass das der aller erste Schritt von zig anderen nicht minder komplexen Dingen - ganz im Gegenteil - ist die vor mir liegen, und dass nur um mal was auszuprobieren. Ich dachte mir halt: Okay, fängste mit was einfachem an, ne Matrixklasse ist ja fix runtergetippert. Ich bin schon etwas demoralisiert nun =] Mich erwarten noch ganz andere Brocken. Man hätte mir sagen sollen, dass Spline-Patches an und für sich schon nichts für ein gemütliches Wochenende sind, und die sind nur die absolute Basis des Ganzen *soifz*.

[Dax]

Wieso denn, das geht doch ganz fix ;)

Code:

class Combiner<T>
{
   public Func<T, T, T> Add {
      get;
      private set;
   }

   public Combiner(Func<T, T, T> _add)
   {
      Add = _add;
   }
}

class MatrixFactory<T>
{
   Combiner<T> combiner;

   public MatrixFactory(Combiner<T> combiner)
   {
      this.combiner = combiner;
   }

   public Matrix<T> New(int dimX, int dimY)
   {
      return new Matrix<T>(combiner, dimX, dimY);
   }
}

class Matrix<T>
{
   Combiner<T> ops;
   T[] values;
   int dimX, dimY;

   public Matrix(Combiner<T> ops, int dimX, int dimY)
   {
      this.ops = ops;
      this.dimX = dimX;
      this.dimY = dimY;
      this.values = new T[dimX * dimY];
   }

   public T this[int x, int y]
   {
      get { return values[(y - 1) * dimY + (x - 1)]; }
      set { values[(y - 1) * dimY + (x - 1)] = value; }
   }

   public override string ToString()
   {
      string result = "";
      for (int y = 1; y <= dimY; y++) {
         if (y > 0)
            result += "\n";
         for (int x = 1; x <= dimX; x++) {
            if (x > 0)
               result += "\t";
            result += this[x, y].ToString();
         }
      }
      return result;
   }

   public static Matrix<T> operator +(T left, Matrix<T> right)
   {
      Matrix<T> result = new Matrix<T>(right.ops, right.dimX, right.dimY);
      result.values = new T[right.values.Length];
      for (int i = 0; i < result.values.Length; i++) {
         result.values[i] = right.ops.Add(left, right.values[i]);
      }
      return result;
   }

   public static Matrix<T> operator +(Matrix<T> left, Matrix<T> right)
   {
      Matrix<T> result = new Matrix<T>(right.ops, right.dimX, right.dimY);
      result.values = new T[right.values.Length];
      for (int i = 0; i < result.values.Length; i++) {
         result.values[i] = right.ops.Add(left.values[i], right.values[i]);
      }
      return result;
   }
}

public class MainClass
{
   public static void Main(string[] args)
   {
      MatrixFactory<double> mf = new MatrixFactory<double>(new Combiner<double>((a, b) => a + b));
      Matrix<double> m = mf.New(4, 4);
      Matrix<double> m2 = mf.New(4, 4);
      Random r = new Random();
      for (int x = 1; x <= 4; x++)
         for (int y = 1; y <= 4; y++)
            m2[x, y] = r.NextDouble();
      m = 1 + m2 + m;
      Console.WriteLine(m);
   }
}

[Phoenix]

Erm.. Dax... musstest Du ihn jetzt so schocken? :mrgreen:
Gleich mit Anonymen Methoden so um Dich zu hauen ist ned nett auf einen Samstagnachmittag ;-)

[Medium]

Um ehrlich zu sein, gefällt mir das sogar garnicht schlecht! Und ich erwäge ernsthaft meine jetzt bereits bestehende 2-Klassen Lösung dafür zu opfern. Ich muss nur noch austüfteln wie ich da nun die Multiplikation mit umsetze, wobei ich, glaube ich, schon eine grobe Vorstellung hab. Phoenix' Bedenken waren nicht ungerechtfertigt - aber ich schein grad ne helle Minute zu haben :) Goßen Dank!

[Phoenix]

Zusätzlich zum Combiner<T> kannst Du ja noch einen Multiplier<T> mit übergeben. Der sieht dann im Prinzip genauso aus, multipliziert halt anstelle von Addition.

[Dax]

Zitat:

Zitat von Phoenix

Zusätzlich zum Combiner<T> kannst Du ja noch einen Multiplier<T> mit übergeben. Der sieht dann im Prinzip genauso aus, multipliziert halt anstelle von Addition.

Mein Gedanke war eigentlich, den Combiner alles tun zu lassen, aber so geht es natürlich auch ;)

[Medium]

Sooo, ich bin auf dem Wege, stoße aber gerade an.

Ich hab den Combiner um die Multiplikation erweitert:

Code:

   public class Combiner<T> 
   { 
      public Func<T, T, T> Add { 
         get; 
         private set; 
      }
      
      public Func<T, T, T> Mul {
         get;
         private set;
      }
   
      public Combiner(Func<T, T, T> _add, Func<T, T, T> _mul)
      { 
         Add = _add;
         Mul = _mul;
      } 
   }

Dann in der Matrix<T> Klasse folgenden Operator hinzugefügt:

Code:

      public static Matrix<T> operator *(Matrix<T> left, Matrix<T> right)
      {
         if (left.dimX != right.dimY) throw new ArrayTypeMismatchException("Operation * on mismatching matrices");
         else{
            Matrix<T> result = new Matrix<T>(right.ops, right.dimX, left.dimY); 
            result.values = new T[right.dimX*left.dimY];
            for (int x = 0; x < result.dimX; x++) {
               for (int y = 0; y < result.dimX; y++) {
                  for (int k=0; k<left.dimX; k++) {
                     result[x, y] = left.ops.Add(result[x, y], left.ops.Mul(left[k, y], right[x, k]));
                  }
               }
            }
            return result;
         }
      }

Ich erzeuge 2 MatrixFactories:

Code:

   MatrixFactory<double> mfd = new MatrixFactory<double>(new Combiner<double>((a, b) => a + b, (a, b) => a * b));
   MatrixFactory<Matrix<double>> mfm = new MatrixFactory<Matrix<double>>(new Combiner<Matrix<double>>((a, b) => a + b, (a, b) => a * b));

Und dann 2 Matrizen daraus:

Code:

   C = mfd.New(4, 4);

   Q = mfm.New(4, 4);
   for (int x=0; x<4; x++)
      for (int y=0; y<4; y++)
         Q[x, y] = mfd.New(2, 1);

Dann versuche ich sie zu multiplizieren:

Code:

   Matrix<Matrix<double>> tmp;
   tmp = Q*C;

Und der Compiler quittiert mit:
"Operator '*' cannot be applied to operands of type 'Matrix<double>' and 'Matrix<Matrix<double>>' (CS0019)

:gruebel: Was hab ich falsch gemacht?

[Phoenix]

Code:

public static Matrix<T> operator *(Matrix<T> left, Matrix<T> right);
Matrix<Matrix<double>> tmp = Q*C;

Der * Operator auf einer Matrix<T> liefert laut Definition eine Matrix<T>, also eine Matrix, die T aufnimmt, zurück.
Du definierst aber für tmp eine Matrix<Matrix<T>> als Rückgabetyp.
Also eine Matrix, die Matrizen von T aufnimmt, und nicht eine Matrix, die T aufnimmt.

Eine Matrix die T aufnimmt kann aber nicht automatisch in eine Matrix, die Matrizen von T aufnimmt, konvertiert werden.

[Dax]

Dein Operator in Q*C hat den Typ (T, Matrix<T>) => Matrix<T>, den hast du aber nicht implementiert. Das ist aber kein Problem, weil die Multiplikation Skalar * Matrix ja echt simpel ist.

[Medium]

Zitat:

Zitat von Phoenix

Der * Operator auf einer Matrix<T> liefert laut Definition eine Matrix<T>, also eine Matrix, die T aufnimmt, zurück.

Ich multipliziere jedoch eine Matrix<T> mit einer Matrix<Matrix<T>>, was wiederum eine Matrix<Matrix<T>> zurück liefern sollte. Glaub ich =)

Aber was Dax sagte kam mir vor 1min auch in den Sinn. Ich hab zwar die Matrizen mit welchem Inhalt auch immer abgedeckt, jeoch nicht den Fall Inhalt*Matrix bzw. umgekehrt, was ja am Ende dieser Kette ansteht. Das dürfte es gewesen sein, mal testen. Merci euch beiden mal wieder :)

[Medium]

Fies.

Folgende Konstruktion:

Code:

Matrix<double> k1;
Matrix<Matrix<double>> Q, k2;
k2 = k1 * Q;

Hier ergibt sich eine nicht eindeutige Situation:
Ist k1 nun ein T oder ein Matrix<T>?

Der compiler wählt jedenfalls die falsche Überladung:

Code:

// sollte es sein
public static Matrix<T> operator *(Matrix<T> left, Matrix<T> right)
// wird statt dessen genommen
public static Matrix<T> operator *(T left, Matrix<T> right)

Hintergrund ist der dass k1 eine 1x4 Matrix ist, Q aber eine 4x4|1x2. Somit trifft nachher 1x4 auf 1x2, obwohl ich nicht k1 mit den Komponenten von Q sondern mit Q selbst multiplizieren will, was 1x4*4x4 und damit gültig wäre. Das ist arg unschön :(

[Apollonius]

Was du vor hast, scheitert nicht an der Überladungsauflösung des Compilers. Vielmehr liegt es daran, dass du dich auf zwei Matrizen mit dem gleichen Elementtyp beschränkst. Denn du willst eben T = double für den linken Operanden und T = Matrix<double> für den rechten. Dafür brauchst du zwei generische Parameter.

[Medium]

Tatsache, das klingt sinnvoll. Ich fummel da mal was.
Edit: Hm, dafür müsste ich aber schon zum Zeitpunkt der Erzeugung der Matrizen wissen, welchen Typ ein späterer Multiplikationspartner haben wird oder? Das weiss ich nämlich leider nicht.
Edit2: Ausserdem fällt mit mit einem 2. Typ die Klamotte mit den Delegates wie ein Kartenhaus zusammen, zumindest wenn ich es nicht völlig missverstanden habe. Wat mach ich denn nu? Ich bin ja schon fast wieder so weit meine alte 2-Matrixtypen Lösung zu reaktivieren :(

[Dax]

Ich kann dir nicht ganz folgen - was willst du eigentlich tun?

[Medium]

Ich versuche mal eine Formel die ich hier habe mit meinen ASCII Art Künsten *hust* hier zu präsentieren:

Code:

/  1  \T  /  1  0  0  0 \   / (0,0) (1,0) (0,0) (1,0) \   /  1  0  0  0 \T  /  1  \
|  v  |   |  0  0  1  0 |   | (0,1) (1,1) (0,1) (1,1) |   |  0  0  1  0 |   |  u  |
| v^2 | * | -3  3 -2 -1 | * | (0,0) (1,0) (0,0) (0,0) | * | -3  3 -2 -1 | * | u^2 | = (x, y)
\ v^3 /   \ -2  2  1  1 /   \ (0,1) (1,1) (0,0) (0,0) /   \ -2  2  1  1 /   \ u^3 /

  VT    *        C        *              Q              *        CT       *    U    = P(u, v)

Das ist eine Formel für ein Splinepatch. Rein gehen Koordinaten u, v | u,v=(0..1), und raus kommen die Bildkoordinaten des resultierenden Punktes auf dem Patch. Q beinhaltet die Eck- und Kontrollpunkte des Patches. Und diese Rechnung muss ich einige Male machen, brauche aber die Matrix Klasse im selben Projekt auch noch in anderen Zusammenhängen. Das hier ist jedoch die einzige Stelle an der (bisher) eine Matrix<Matrix<>> vorkommt.

[Dax]

Was da nun passieren soll, ist mir immer noch völlig unklar :( Welcher Typ soll C * Q haben? Daran scheinst du ja vermutlich zu hängen.

[Medium]

C ist ein Matrix<double> und Q ist ein Matrix<Matrix<double>>. Heraus kommt dabei von Hand ein Matrix<Matrix<double>> mit Dimensionen 1x4, und inneren Matrizen der Dimension 1x2. Das Problem ist, dass der Compiler nicht C*Q, sondern C*Q[x,y] versucht, was knallen muss da die Matrizen Q[x,y] die Dimension 1x2 haben (und auch wenn es 4x1 wäre, immernoch zum falschen Ergebnis führen würde).


Edit: Halt mal! Das Ergebnis aus VT*C wird ja mit Q multipliziert. Deswegen kommt am Ende eine 1x4 Matrix heraus, weil VT*C ergibt ebenfalls eine 1x4 Matrix. Ändert nix am Problem an sich, sonst ist aber nicht ganz klar wie ich zu 1x4 komme.

[Dax]

Ah, jetzt sehe ich, was du meinst. Dazu müsstest du wohl noch einen Operator Matrix<T> * Matrix<Matrix<T>> implementieren (der sollte dann benutzt werden, immerhin matcht der besser), oder direkt die Matrizen mit variabler Dimension bauen.

[Medium]

Zitat:

Zitat von Dax

Ah, jetzt sehe ich, was du meinst. Dazu müsstest du wohl noch einen Operator Matrix<T> * Matrix<Matrix<T>> implementieren (der sollte dann benutzt werden, immerhin matcht der besser)

Nicht die schlechteste Idee. hat lediglich den Beigeschmack, dass man neue Operatoren für jede neue Verschachtelungstiefe bräuchte, ich erwarte aber dass es nicht schlimmer als Matrix<Matrix<>> wird. Das wäre auch schon ein Monster-Konstrukt dann :D
Das werd ich gleich mal probieren!

Zitat:

oder direkt die Matrizen mit variabler Dimension bauen.

Den versteh ich nun nicht. Sind sie doch :gruebel:

[Dax]

Zitat:

Zitat von Medium

Nicht die schlechteste Idee. hat lediglich den Beigeschmack, dass man neue Operatoren für jede neue Verschachtelungstiefe bräuchte

Wenn es darum geht, M<T> * M<M<T>>, M<T> * M<M<M<T>>>, ... zu haben, bei denen die Komponenten der zweiten Matrix mit den Komponenten der ersten multipliziert werden, würde dafür eine Methode ausreichen. Diese Methode würde bei M<T> * M<M<T>> die entsprechende Multiplikation durchführen und bei tieferen Schachtelungen die Methode für die erste Matrix und jedes Element der zweiten Matrix aufrufen. Zumindest denke ich, dass das das ist, was du willst.

Zitat:

Zitat von Medium

Den versteh ich nun nicht. Sind sie doch :gruebel:

Sein. Sie sind fester Dimension (2), aber variabler Größe. Du hast bei VT * C * Q eine 2^1|4 * 2^4|4 * 3^4|4|2-Konfiguration ;) Aber dafür entsprechende Strukturen zu definieren und die Multiplikation so umzusetzen, dass sie immer tut, was du willst, ist wohl nicht mehr ganz so einfach wie der Weg oben.

[Medium]

HEUREKA!

Ich hab zwar noch immer nicht kapiert was du im 2. Absatz meintest, aber mit Operatoren für M<T> * M<M<T>> und umgekehrt funktionniert es! :party:

Und dass diese schon ausreichen sollten um tiefere Verschachtelungen abzuhandeln leuchtet auch ein, zumindest so lange die beiden Multiplikanden sich nur um eine Verschachtelungstiefe unterscheiden. Und so arg wird's schon nicht mehr werden hier.

Gaaaaaaaaaaaaaaanz großen Dank! :love: