9

Вот решил перейти с С++ на С# и наткнулся на такую проблему. Как я понял, в шарпе нет шаблонов как таковых, и это компенсируется интерфейсами и обобщенными классами. Вопрос: есть ли способ, дать понять компилятору, что 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 ;
       }
  ///...
}
4

3 ответа 3

8

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

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);
   }
}

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

2
  • в 'местные' лямбда выражения еще не лез, но всеравно спасибо
    – Xambey
    4 сен 2016 в 12:04
  • Ого, круто! Я думал над этим путём, но не довёл до конца и пошёл в сторону рефлексии.
    – VladD
    4 сен 2016 в 12:09
6

Самый эффективный на данный момент метод — подключить из 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

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

12
  • Спасибо, а я думал, что реализован где-то иниерфейс для чисел, печаль(
    – Xambey
    4 сен 2016 в 7:55
  • 1
    А оно точно получится "не самым эффективным" методом? ЕМНИП, dynamic в цикле должен тормозить безбожно... 4 сен 2016 в 11:25
  • @PavelMayorov: Насколько я понимаю, dynamic кеширует свой делегат, так что очень плохо не будет. Более эффективно было бы (1) для простых типов просто завести готовые делегаты, (2) для пользовательских типов найти op_Addition через рефлексию, и превратить в делегат (у System.Int32 нету op_Addition).
    – VladD
    4 сен 2016 в 12:08
  • @VladD э... а почему у вас динамик делает в 10 раз меньше итераций?.. 4 сен 2016 в 12:36
  • 1
    @VladD про кеширование делегата я в курсе, но, как мне думается, сама по себе проверка на неизменность типа делается слишком долго для таких простых операций 4 сен 2016 в 12:40
1

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.