Реализация Матрицы C# [дубликат]

#c_sharp

    На данный вопрос уже ответили:
    
        
            Как написать метод/класс, который бы одинаково работал со всеми числовыми
типами?
                
                    3 ответа
                
        
    
    
Вот решил перейти с С++ на С# и наткнулся на такую проблему. Как я понял, в шарпе
нет шаблонов как таковых, и это компенсируется интерфейсами и обобщенными классами.
Вопрос: есть ли способ, дать понять компилятору, что Type - числа? , чтобы использовать
операторы стандартных типов, иначе не получается реализовать сложение и тп. матриц.
Или есть другое решение? Вот что сделал: 

public class Matrix /*where Type ...*/ 
{
       private List> MatrixValue;

       public Matrix(int rows, int cols)
       {
           MatrixValue = new List>(rows);
           foreach (var item in MatrixValue)
           {
               item.Capacity = cols;
           }
       }
       public Matrix()
       {
           MatrixValue = new List>();
       }
       public static Matrix operator +(Matrix left, Matrix right)
       {
           Matrix result = new Matrix(left.countRows(),   left.countColums());
           for (int i = 0; i < left.countRows(); i++)
           {
               for (int j = 0; j < left.countColums(); j++)
               {
                   result.set(left.get(i, j) + right.get(i, j); // ОШИБКА!
               }
           }
           return ;
       }
  ///...
}

    

Ответы

Ответ 1

Самый эффективный на данный момент метод — подключить из nuget System.Numerics.Vectors,
и векторизовать ваши операции. Заодно вы получите их в generic-виде. Для System.Numerics.Vectors.Vector
определена операция сложения, даже если сама структура T неизвестна!

Вот вам упрощённый класс, представляющий вектор произвольной длины с операцией сложения:

class VectorNum where T: struct
{
    List> payload;
    int size;

    public VectorNum(int size)
    {
        var vectorSize = System.Numerics.Vector.Count;
        var vectorCount = (size + vectorSize - 1) / vectorSize;
        payload = new List>(vectorCount);
        this.size = size;
    }

    public void AddTo(VectorNum r)
    {
        List> ldata = payload, rdata = r.payload;
        if (size != r.size)
            throw new ArgumentException();
        for (int i = 0; i < ldata.Count; i++)
            ldata[i] = ldata[i] + rdata[i];
    }
}


Бенчмарки внизу.



Более простой (но менее эффективный) метод, вероятно, такой:

static T add(T l, T r)
{
    return (T)((dynamic)l + r);
}




На текущий момент нельзя объяснить компилятору, что тип генерик-параметра — числовой.
Хуже того, это проблематично, поскольку для каждой инстанциации генерик-типа работает
один и тот же IL. А сложение int'ов и double'ов представлено на IL-уровне разными инструкциями.



Измерение эффективности.

Вот такая тестовая программа:

static class Program
{
    static void Main()
    {
        VectorExpr ve1 = new VectorExpr(2048),
                           ve2 = new VectorExpr(2048);
        VectorDyn  vd1 = new VectorDyn(2048),
                           vd2 = new VectorDyn(2048);
        VectorNatDouble    vn1 = new VectorNatDouble(2048),
                           vn2 = new VectorNatDouble(2048);
        VectorNum  vv1 = new VectorNum(2048),
                           vv2 = new VectorNum(2048);

        // прогрев
        ve1.Init(1.1, 2.2); ve2.Init(1.1, 2.2);
        vd1.Init(1.1, 2.2); vd2.Init(1.1, 2.2);
        vn1.Init(1.1, 2.2); vn2.Init(1.1, 2.2);
        vv1.Init(1.1, 2.2); vv2.Init(1.1, 2.2);

        ve1.AddTo(ve2); vd1.AddTo(vd2); vn1.AddTo(vn2); vv1.AddTo(vv2);

        Stopwatch swE = new Stopwatch(), swD = new Stopwatch(),
                  swN = new Stopwatch(), swV = new Stopwatch();

        swE.Start();
        for (int i = 0; i < 1000 * 1000; i++)
            ve1.AddTo(ve2);
        swE.Stop();
        var resultE = ve1.Sum();

        swD.Start();
        for (int i = 0; i < 1000 * 1000; i++)
            vd1.AddTo(vd2);
        swD.Stop();
        var resultD = vd1.Sum();

        swN.Start();
        for (int i = 0; i < 1000 * 1000; i++)
            vn1.AddTo(vn2);
        swN.Stop();
        var resultN = vn1.Sum();

        swV.Start();
        for (int i = 0; i < 1000 * 1000; i++)
            vv1.AddTo(vv2);
        swV.Stop();
        var resultV = vv1.Sum();

        Console.WriteLine($"Expression: elapsed time {swE.Elapsed}, result = {resultE}");
        Console.WriteLine($"Dynamic   : elapsed time {swD.Elapsed}, result = {resultD}");
        Console.WriteLine($"Native    : elapsed time {swN.Elapsed}, result = {resultN}");
        Console.WriteLine($"Vector    : elapsed time {swV.Elapsed}, result = {resultV}");
    }
}

class VectorExpr
{
    static readonly Func add;

    static VectorExpr()
    {
        var a = Expression.Parameter(typeof(T));
        var b = Expression.Parameter(typeof(T));
        add = Expression.Lambda>(Expression.Add(a, b), a, b).Compile();
    }

    T[] payload;

    public VectorExpr(int size)
    {
        payload = new T[size];
    }

    public void Init(T seed1, T seed2)
    {
        T curr = seed1;
        for (int i = 0; i < payload.Length; i++)
        {
            payload[i] = curr;
            curr = add(curr, seed2);
        }
    }

    public void AddTo(VectorExpr r)
    {
        T[] ldata = payload, rdata = r.payload;
        if (ldata.Length != rdata.Length)
            throw new ArgumentException();
        for (int i = 0; i < ldata.Length; i++)
            ldata[i] = add(ldata[i], rdata[i]);
    }

    public T Sum() => Enumerable.Aggregate(payload, add);
}

class VectorDyn
{
    static T add(T l, T r) => (T)((dynamic)l + r);

    T[] payload;

    public VectorDyn(int size)
    {
        payload = new T[size];
    }

    public void Init(T seed1, T seed2)
    {
        T curr = seed1;
        for (int i = 0; i < payload.Length; i++)
        {
            payload[i] = curr;
            curr = add(curr, seed2);
        }
    }

    public void AddTo(VectorDyn r)
    {
        T[] ldata = payload, rdata = r.payload;
        if (ldata.Length != rdata.Length)
            throw new ArgumentException();
        for (int i = 0; i < ldata.Length; i++)
            ldata[i] = add(ldata[i], rdata[i]);
    }

    public T Sum() => Enumerable.Aggregate(payload, add);
}

class VectorNum where T: struct
{
    List> payload;
    int size;

    public VectorNum(int size)
    {
        var vectorSize = System.Numerics.Vector.Count;
        var vectorCount = (size + vectorSize - 1) / vectorSize;
        payload = new List>(vectorCount);
        this.size = size;
    }

    public void Init(T seed1, T seed2)
    {
        var values = new T[System.Numerics.Vector.Count];
        T curr = seed1;
        for (int i = 0; i < size; i++)
        {
            int j = i % values.Length;
            values[j] = curr;
            curr = (T)((dynamic)curr + seed2);
            if (j == values.Length - 1 || i == size - 1)
            {
                payload.Add(new System.Numerics.Vector(values));
                Array.Clear(values, 0, values.Length);
            }
        }
    }

    public void AddTo(VectorNum r)
    {
        List> ldata = payload, rdata = r.payload;
        if (size != r.size)
            throw new ArgumentException();
        for (int i = 0; i < ldata.Count; i++)
            ldata[i] = ldata[i] + rdata[i];
    }

    public T Sum()
    {
        var vectorSum = Enumerable.Aggregate(payload, (v1, v2) => v1 + v2);
        return Enumerable.Range(0, System.Numerics.Vector.Count)
                         .Select(idx => vectorSum[idx])
                         .Aggregate((l, r) => (T)((dynamic)l + r));
    }
}

class VectorNatDouble
{
    double[] payload;

    public VectorNatDouble(int size)
    {
        payload = new double[size];
    }

    public void Init(double seed1, double seed2)
    {
        double curr = seed1;
        for (int i = 0; i < payload.Length; i++)
        {
            payload[i] = curr;
            curr = curr + seed2;
        }
    }

    public void AddTo(VectorNatDouble r)
    {
        double[] ldata = payload, rdata = r.payload;
        if (ldata.Length != rdata.Length)
            throw new ArgumentException();
        for (int i = 0; i < ldata.Length; i++)
            ldata[i] = ldata[i] + rdata[i];
    }

    public double Sum() => payload.Sum();
}


сравнивает подход с dynamic, подход с Expression, подход с векторизацией и нативный
необобщённой код.

Результаты (Release mode, вне Visual Studio, x64 на 64-битной Windows) по пяти запускам:

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:03.2824695, result = 4613743627468,84
Dynamic   : elapsed time 00:00:22.1788664, result = 4613743627468,84
Native    : elapsed time 00:00:01.3229095, result = 4613743627468,84
Vector    : elapsed time 00:00:01.0145604, result = 4613743627468,84

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:03.3579191, result = 4613743627468,84
Dynamic   : elapsed time 00:00:22.6582909, result = 4613743627468,84
Native    : elapsed time 00:00:01.3391487, result = 4613743627468,84
Vector    : elapsed time 00:00:01.0315590, result = 4613743627468,84

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:03.3705103, result = 4613743627468,84
Dynamic   : elapsed time 00:00:21.9322240, result = 4613743627468,84
Native    : elapsed time 00:00:01.3294231, result = 4613743627468,84
Vector    : elapsed time 00:00:01.0168434, result = 4613743627468,84

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:03.3426822, result = 4613743627468,84
Dynamic   : elapsed time 00:00:22.5870899, result = 4613743627468,84
Native    : elapsed time 00:00:01.3227761, result = 4613743627468,84
Vector    : elapsed time 00:00:01.0202565, result = 4613743627468,84

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:03.3142676, result = 4613743627468,84
Dynamic   : elapsed time 00:00:21.8089834, result = 4613743627468,84
Native    : elapsed time 00:00:01.2854937, result = 4613743627468,84
Vector    : elapsed time 00:00:00.9963579, result = 4613743627468,84


Среднее для Expression 3.3336 секунд, для dynamic 22.2331 секунд, нативный код 1,3200
секунд, и векторизованный код 1.0159 секунд. Так что векторизованный вариант быстрее
даже нативного на 30%.

Результаты для int ещё лучше:

...\bin\x64\Release>Test.exe
Expression: elapsed time 00:00:02.9075671, result = -1870659584
Dynamic   : elapsed time 00:00:22.9417084, result = -1870659584
Native    : elapsed time 00:00:01.5297815, result = -1870659584
Vector    : elapsed time 00:00:00.5281395, result = -1870659584


Векторизация даёт ускорение втрое по сравнению с нативным кодом.


Ответ 2

Вот так можно попробовать:

class Matrix {
  static readonly Func add, sub, mul;

  static Matrix() {
    var a = Expression.Parameter(typeof(T));
    var b = Expression.Parameter(typeof(T));

    add = Expression.Lambda>(Expression.Add(a, b), a, b).Compile();
    sub = Expression.Lambda>(Expression.Subtract(a, b), a, b).Compile();
    mul = Expression.Lambda>(Expression.Multiply(a, b), a, b).Compile();
  }

  // использование:
  // var r = add(left.get(i, j), right.get(i, j));
}


Должно работать быстрее чем через dynamic - но медленнее чем нормальное сложение.



Еще немного времени можно выгадать, запихнув внутрь Expression алгоритм целиком:

class Matrix2
{
    delegate void MatrixOperation (int lb0, int ub0, int lb1, int ub1, T[,] a, T[,]
b, T[,] c);
    static readonly MatrixOperation add;

    static Expression MakeRangeFor(Expression min, Expression max, Func body) {
        var i = Expression.Variable(min.Type);
        var exit = Expression.Label();
        return Expression.Block(new[]{ i }, 
          Expression.Assign(i, min),
          Expression.Loop(
            Expression.Block(
                body(i),
                Expression.Condition(
                    Expression.LessThanOrEqual(Expression.PreIncrementAssign(i), max),
                    Expression.Empty(),
                    Expression.Break(exit)
                )
            ),
            exit
          )
        );
    }

    static Matrix2()
    {
        var lb0 = Expression.Parameter(typeof(int));
        var ub0 = Expression.Parameter(typeof(int));
        var lb1 = Expression.Parameter(typeof(int));
        var ub1 = Expression.Parameter(typeof(int));
        var a = Expression.Parameter(typeof(T[,]));
        var b = Expression.Parameter(typeof(T[,]));
        var c = Expression.Parameter(typeof(T[,]));

        add = Expression.Lambda(
            MakeRangeFor(lb0, ub0, i =>
                MakeRangeFor(lb1, ub1, j =>
                    Expression.Assign(
                        Expression.ArrayAccess(a, i, j),
                        Expression.Add(
                            Expression.ArrayAccess(b, i, j),
                            Expression.ArrayAccess(c, i, j)
                        )
                    )
                )
            ),
            lb0, ub0, lb1, ub1, a, b, c).Compile();
    }

   private readonly T[,] items;

   public static Matrix operator +(Matrix a, Matrix b)
   {
       int lb0 = a.items.GetLowerBound(0),
           ub0 = a.items.GetUpperBound(0),
           lb1 = a.items.GetLowerBound(1),
           ub1 = a.items.GetUpperBound(1);

       var result = new Matrix(lb0, ub0, lb1, ub1);
       add(lb0, ub0, lb1, ub1, result.items, a.items, b.items);
   }
}


Как видно в бенчмарке - подобное преобразование еще больше уменьшает время работы,
приближаясь к времени алгоритма, не использующего обобщения.


Ответ 3

Интерфейса для чисел, к сожалению, нет, максимум что есть - это базовый ValueType
для типов-значений