Реализация Матрицы C#

458
09 декабря 2016, 08:58

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

public class Matrix<Type> /*where Type ...*/ 
{
       private List<List<Type>> MatrixValue;
       public Matrix(int rows, int cols)
       {
           MatrixValue = new List<List<Type>>(rows);
           foreach (var item in MatrixValue)
           {
               item.Capacity = cols;
           }
       }
       public Matrix()
       {
           MatrixValue = new List<List<Type>>();
       }
       public static Matrix<Type> operator +(Matrix<Type> left, Matrix<Type> right)
       {
           Matrix<Type> result = new Matrix<Type>(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 ;
       }
  ///...
}
Answer 1

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

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

class VectorNum<T> where T: struct
{
    List<System.Numerics.Vector<T>> payload;
    int size;
    public VectorNum(int size)
    {
        var vectorSize = System.Numerics.Vector<T>.Count;
        var vectorCount = (size + vectorSize - 1) / vectorSize;
        payload = new List<System.Numerics.Vector<T>>(vectorCount);
        this.size = size;
    }
    public void AddTo(VectorNum<T> r)
    {
        List<System.Numerics.Vector<T>> 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<double> ve1 = new VectorExpr<double>(2048),
                           ve2 = new VectorExpr<double>(2048);
        VectorDyn<double>  vd1 = new VectorDyn<double>(2048),
                           vd2 = new VectorDyn<double>(2048);
        VectorNatDouble    vn1 = new VectorNatDouble(2048),
                           vn2 = new VectorNatDouble(2048);
        VectorNum<double>  vv1 = new VectorNum<double>(2048),
                           vv2 = new VectorNum<double>(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<T>
{
    static readonly Func<T, T, T> add;
    static VectorExpr()
    {
        var a = Expression.Parameter(typeof(T));
        var b = Expression.Parameter(typeof(T));
        add = Expression.Lambda<Func<T, T, T>>(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<T> 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<T>
{
    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<T> 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<T> where T: struct
{
    List<System.Numerics.Vector<T>> payload;
    int size;
    public VectorNum(int size)
    {
        var vectorSize = System.Numerics.Vector<T>.Count;
        var vectorCount = (size + vectorSize - 1) / vectorSize;
        payload = new List<System.Numerics.Vector<T>>(vectorCount);
        this.size = size;
    }
    public void Init(T seed1, T seed2)
    {
        var values = new T[System.Numerics.Vector<T>.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<T>(values));
                Array.Clear(values, 0, values.Length);
            }
        }
    }
    public void AddTo(VectorNum<T> r)
    {
        List<System.Numerics.Vector<T>> 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<T>.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

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

Answer 2

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

class Matrix<T> {
  static readonly Func<T, T, T> add, sub, mul;
  static Matrix() {
    var a = Expression.Parameter(typeof(T));
    var b = Expression.Parameter(typeof(T));
    add = Expression.Lambda<Func<T, T, T>>(Expression.Add(a, b), a, b).Compile();
    sub = Expression.Lambda<Func<T, T, T>>(Expression.Subtract(a, b), a, b).Compile();
    mul = Expression.Lambda<Func<T, T, T>>(Expression.Multiply(a, b), a, b).Compile();
  }
  // использование:
  // var r = add(left.get(i, j), right.get(i, j));
}

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

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

class Matrix2<T>
{
    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<Expression, Expression> 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<MatrixOperation>(
            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<T> operator +(Matrix<T> a, Matrix<T> 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<T>(lb0, ub0, lb1, ub1);
       add(lb0, ub0, lb1, ub1, result.items, a.items, b.items);
   }
}

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

Answer 3

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

READ ALSO
Точка входа в MVVM: App.xaml.cs или представление?
c#

Точка входа в MVVM: App.xaml.cs или представление?

Начал изучать MVVM и столкнулся, как наверное и многие другие, с определенным недопониманиемВ многочисленных примерах реализации MVVM, доступных...

 271
Как создать папку с текстовыми файлами в проекте и пользоваться ими?
c#

Как создать папку с текстовыми файлами в проекте и пользоваться ими?

Хочу добавить в проект несколько csv файлов и пользоваться ими, как текстовыми ресурсамиНу и чтобы лежали вместе в папке для порядка

 370
C# selenuim phantomJS error: can&#39;t find JQuery
c#

C# selenuim phantomJS error: can't find JQuery

ПриветствуюРешил поработать с selenium в C# посредством веб-драйвера phantomJS, но при запуске phantomjs

 275
C#, parallel loop, output to richtextbox
c#

C#, parallel loop, output to richtextbox

Есть код:

 283