Как улучшить производительность 2d массива? - PullRequest
Новая
       16

Как улучшить производительность 2d массива?

0 голосов
/ 04 октября 2018

Я пытался использовать класс плотной матрицы Math.Net .Но он не поддерживает int.Итак, мне нужно создать оболочку для зубчатого 2d массива.

Я знал, что зубчатые массивы имеют лучшие характеристики .

Data Size          : 966 x 345
Naked 2d Array     : 10 milliseconds
Naked Jagged Array : 6 milliseconds
Jagged Wrapper     : 82 milliseconds
Dense Wrapper      : 88 milliseconds
2d Wrapper         : 62 milliseconds

Согласно результатам моего теста, голый зубчатый массив самый быстрый из всех.Но, с точки зрения обертки, 2d обертка относительно быстрее.

Теперь у меня есть два вопроса:

  1. Почему зубчатая оболочка медленнее, чем двумерная оболочка?
  2. Можно ли заставить оболочку работать так же быстро, как иголый?

.

Исходный код

Тестовый код 

Bitmap bmpImage = DataConverter2d.ReadGray("image.jpg");

int[][] intNakedJagged = DataConverter2d.ToInteger(bmpImage);
int[,] intNaked2d = JagMatrix<int>.To2d(intNakedJagged);

JagMatrix<int> intJaggedWrapper = new JagMatrix<int>(intNakedJagged);
DenMatrix<int> intDenWrapper = new DenMatrix<int>(intNaked2d);
Matrix<int> int2dWrapper = new Matrix<int>(intNaked2d);

Stopwatch sw1 = new Stopwatch();
sw1.Start();
double[,] dImage = DataConverter2d.ToDouble(intNaked2d);
sw1.Stop();
Console.WriteLine("Naked 2d Array : " + sw1.ElapsedMilliseconds.ToString() + " milliseconds", "Elapsed time");


Stopwatch sw2 = new Stopwatch();
sw2.Start();
double[][] dImageJagged = DataConverter2d.ToDouble(intNakedJagged);
sw2.Stop();
Console.WriteLine("Naked Jagged Array : " + sw2.ElapsedMilliseconds.ToString() + " milliseconds", "Elapsed time");


Stopwatch sw3 = new Stopwatch();
sw3.Start();
JagMatrix<double> dJagArray2d = DataConverter2d.ToDouble(intJaggedWrapper);
sw3.Stop();
Console.WriteLine("Jagged Wrapper : " + sw3.ElapsedMilliseconds.ToString() + " milliseconds", "Elapsed time");

Stopwatch sw4 = new Stopwatch();
sw4.Start();
DenMatrix<double> dDenArray2d = DataConverter2d.ToDouble(intDenWrapper);
sw4.Stop();
Console.WriteLine("Dense Wrapper : " + sw4.ElapsedMilliseconds.ToString() + " milliseconds", "Elapsed time");

Stopwatch sw5 = new Stopwatch();
sw5.Start();
Matrix<double> dArray2d = DataConverter2d.ToDouble(int2dWrapper);
sw5.Stop();
Console.WriteLine("2d Wrapper : " + sw5.ElapsedMilliseconds.ToString() + " milliseconds", "Elapsed time");

Console.ReadKey();

2d Matrix 

public class Matrix<T> : IDisposable where T : struct , IComparable<T>
{
    private T[,] __array2d;
    public int Width { get; set; }
    public int Height { get; set; }
    public bool IsEmpty
    {
        get
        {
            if (__array2d == null) return true;
            else return false;
        }
    }

    public Matrix() { }
    public Matrix(T[,] data)
    {
        this.Set(data);
    }

    public Matrix(int rows, int cols)
    {
        Width = rows;
        Height = cols;
        __array2d = new T[Width, Height];
    }
    public T Get(int x, int y)
    {
        if (__array2d == null)
        {
            throw new Exception("array is empty");
        }
        if (x < Width && y < Height)
        {
            if (__array2d != null)
            {
                return __array2d[x, y];
            }
            else
            {
                throw new Exception("array is null");
            }
        }
        else
        {
            string message = string.Empty;

            if (x >= Width) message = "x-value exceeds Width ";
            if (y >= Height) message += "y-value exceeds Height ";
            message += "in Array2d.Get(x,y).";
            throw new Exception(message);
        }
    }

    public void Set(int x, int y, T val)
    {
        if (__array2d == null)
        {
            __array2d = new T[Width, Height];
        }
        else
        {
            if (Width != __array2d.GetLength(0))
            {
                __array2d = null;
                __array2d = new T[Width, Height];
            }
        }

        if (x < Width && y < Height)
        {
            __array2d[x, y] = val;
        }
        else
        {

            throw new Exception(x + ", " + Width + "," + y + "," + Height);
        }
    }

    public T this[int x, int y]
    {
        get
        {
            return Get(x, y);
        }
        set
        {
            Set(x, y, value);
        }
    }

    public void Set(T[,] arr)
    {
        if (arr != null)
        {
            int rows = arr.GetLength(0);
            int cols = arr.GetLength(1);

            __array2d = arr;
            Width = rows;
            Height = cols;
        }
        else
        {
            throw new Exception("array is null");
        }
    }

    #region IDisposable implementation
    ~Matrix()
    {
        this.Dispose(false);
    }

    protected bool Disposed { get; private set; }

    public void Dispose()
    {
        this.Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (!this.Disposed)
        {
            if (disposing)
            {
                // Perform managed cleanup here.
                //IDisposable disp = (IDisposable)_2dArray;

                __array2d = null;
            }

            // Perform unmanaged cleanup here.
            Width = 0;
            Height = 0;

            this.Disposed = true;
        }
    }
    #endregion
}

2d Матрица с зазубринами 

public class JagMatrix<T> : IDisposable where T : struct , IComparable<T>
{
    private T[][] __array2d;
    public int Width { get; set; }
    public int Height { get; set; }
    public bool IsEmpty
    {
        get
        {
            if (__array2d == null) return true;
            else return false;
        }
    }

    public JagMatrix() { }
    public JagMatrix(T[][] data)
    {
        this.Set(data);
    }

    public JagMatrix(int rows, int cols)
    {
        Width = rows;
        Height = cols;

        __array2d = new T[Width][];
        for (int i = 0; i < Width; i++)
        {
            __array2d[i] = new T[Height];
        }
    }
    public T Get(int x, int y)
    {
        if (__array2d == null)
        {
            throw new Exception("array is empty");
        }
        if (x < Width && y < Height)
        {
            if (__array2d != null)
            {
                return __array2d[x][y];
            }
            else
            {
                throw new Exception("array is null");
            }
        }
        else
        {
            string message = string.Empty;

            if (x >= Width) message = "x-value exceeds Width ";
            if (y >= Height) message += "y-value exceeds Height ";
            message += "in Array2d.Get(x,y).";

            throw new Exception(message);
        }
    }

    public void Set(int x, int y, T val)
    {
        if (__array2d == null)
        {
            __array2d = new T[Width][];
            for (int i = 0; i < Width; i++)
            {
                __array2d[i] = new T[Height];
            }
        }
        else
        {
            if (Width != __array2d.GetLength(0))
            {
                __array2d = null;

                __array2d = new T[Width][];
                for (int i = 0; i < Width; i++)
                {
                    __array2d[i] = new T[Height];
                }
            }
        }

        if (x < Width && y < Height)
        {
            __array2d[x][y] = val;
        }
        else
        {

            throw new Exception(x + ", " + Width + "," + y + "," + Height);
        }
    }

    public static T[,] To2d(T[][] source)
    {
        T[,] dest = new T[source.Length, source[0].Length];

        for (int i = 0; i < source.Length; i++)
        {
            for (int j = 0; j < source[0].Length; j++)
            {
                dest[i,j] = source[i][j];
            }
        }

        return dest;
    }

    public T this[int x, int y]
    {
        get
        {
            return Get(x, y);
        }
        set
        {
            Set(x, y, value);
        }
    }

    public void Set(T[][] arr)
    {
        if (arr != null)
        {
            int rows = arr.Length;
            int cols = arr[0].Length;

            __array2d = arr;

            Width = rows;
            Height = cols;
        }
        else
        {
            throw new Exception("array is null");
        }
    }

    #region IDisposable implementation
    ~JagMatrix()
    {
        this.Dispose(false);
    }

    protected bool Disposed { get; private set; }

    public void Dispose()
    {
        this.Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (!this.Disposed)
        {
            if (disposing)
            {
                // Perform managed cleanup here.
                //IDisposable disp = (IDisposable)_2dArray;

                __array2d = null;
            }

            // Perform unmanaged cleanup here.
            Width = 0;
            Height = 0;

            this.Disposed = true;
        }
    }
    #endregion
}

2d Плотная матрица 

public class DenMatrix<T> : IDisposable where T : struct , IComparable<T>
{
    private T[] __array1d;
    public int Width { get; set; }
    public int Height { get; set; }
    public int Length { get { return Width * Height; } }
    public bool IsEmpty
    {
        get
        {
            if (__array1d == null) return true;
            else return false;
        }
    }

    public DenMatrix() { }
    public DenMatrix(T[,] data)
    {
        this.Set(data);
    }

    public DenMatrix(int rows, int cols)
    {
        Width = rows;
        Height = cols;

        __array1d = new T[Length];
    }

    public T Get(int x, int y)
    {
        if (__array1d == null)
        {
            throw new Exception("array is empty");
        }
        if (x < Width && y < Height)
        {
            if (__array1d != null)
            {
                return __array1d[x + y * Width];
            }
            else
            {
                throw new Exception("array is null");
            }
        }
        else
        {
            string message = string.Empty;

            if (x >= Width) message = "x-value exceeds Width ";
            if (y >= Height) message += "y-value exceeds Height ";
            message += "in Array2d.Get(x,y).";
            throw new Exception(message);
        }
    }

    public void Set(int x, int y, T val)
    {
        int length = Length;

        if (__array1d == null)
        {
            __array1d = new T[length];
        }
        else
        {
            if (length != __array1d.Length)
            {
                __array1d = null;
                __array1d = new T[length];
            }
        }

        if (x < Width && y < Height)
        {
            __array1d[x + y * Width] = val;
        }
        else
        {

            throw new Exception(x + ", " + Width + "," + y + "," + Height);
        }
    }

    public T[] To1d(T[,] array2d)
    {
        T[] array1d = new T[Length];

        for (int x = 0; x < Height; x++)
        {
            for (int y = 0; y < Width; y++)
            {
                T val = array2d[x, y];

                int index = x * Width + y;

                array1d[index] = val;
            }
        }

        return array1d;
    }

    public T this[int x, int y]
    {
        get
        {
            return Get(x, y);
        }
        set
        {
            Set(x, y, value);
        }
    }

    public void Set(T[,] arr)
    {
        if (arr != null)
        {
            int rows = arr.GetLength(0);
            int cols = arr.GetLength(1);

            Width = cols;
            Height = rows;

            __array1d = To1d(arr);
        }
        else
        {
            throw new Exception("array is null");
        }
    }

    #region IDisposable implementation
    ~DenMatrix()
    {
        this.Dispose(false);
    }

    protected bool Disposed { get; private set; }

    public void Dispose()
    {
        this.Dispose(true);
        GC.SuppressFinalize(this);
    }

    protected virtual void Dispose(bool disposing)
    {
        if (!this.Disposed)
        {
            if (disposing)
            {
                // Perform managed cleanup here.
                //IDisposable disp = (IDisposable)_2dArray;

                __array1d = null;
            }

            // Perform unmanaged cleanup here.
            Width = 0;
            Height = 0;

            this.Disposed = true;
        }
    }
    #endregion
}

double [] [] ToDouble (int [][] изображение) 

    public static double[][] ToDouble(int[][] image)
    {
        int Width = image.Length;
        int Height = image[0].Length;

        double[][] array2d = new double[Width][];

        for (int x = 0; x < Width; x++)
        {
            array2d[x] = new double[Height];

            for (int y = 0; y < Height; y++)
            {
                double d = image[x][y] / 255.0;

                array2d[x][y] = d;
            }
        }

        return array2d;
    }

DataConverter2d.Todouble (матричное изображение) 

    public static Matrix<double> ToDouble(Matrix<int> image)
    {
        int Width = image.Width;
        int Height = image.Height;

        Matrix<double> array2d = new Matrix<double>(Width, Height);

        for (int x = 0; x < Width; x++)
        {
            for (int y = 0; y < Height; y++)
            {
                double d = image[x, y] / 255.0;

                array2d[x, y] = d;
            }
        }

        return array2d;
    }

Ответы [ 2 ]

0 голосов
/ 11 октября 2018

Согласно результатам моего теста, голый зубчатый массив самый быстрый из всех.Но, с точки зрения обертки, обертка 2d относительно быстрее.

Что ж, мои тесты (запуск кода из ответа Дж. Коенена через exe, встроенный в режим выпуска) показываютразные результаты: 

Data Size          : 4000 x 4000
Naked 2d Array     : 70 milliseconds
Naked Jagged Array : 67 milliseconds
Jagged Wrapper     : 205 milliseconds
Dense Wrapper      : 391 milliseconds
2d Wrapper         : 227 milliseconds
Faster versions:
FastMatrix         : 143 milliseconds
FastMatrix.Map     : 130 milliseconds

Я запускал его несколько раз, и обе реализации Jagged немного быстрее, чем их 2d-аналоги.Реализация Dense значительно медленнее.

Можно ли сделать так, чтобы оболочка работала так же быстро, как и голая?

Абсолютно!Ваши методы Get / Set выполняют много ненужной работы, в основном дублируя работу CLR неэффективным, избыточным и не полностью корректным способом (например, нет проверки на отрицательные индексы).Не делай этого. J.Коенен показал верное направление, но вы можете пойти дальше.В C # 7.0 появилась (долгожданная людьми, которая заботится о производительности) функция, называемая Ref locals и возвращает , которая позволяет создавать пользовательские индексаторы классов с характеристиками производительности, подобными массивам CLR.Это даже сопровождается прецедентом / примером для матриц:)

Все, что вам нужно, это изменить указатели вашего класса на:

Matrix 

public ref T this[int x, int y] => ref __array2d[x, y];

JagMatrix 

public ref T this[int x, int y] => ref __array2d[x][y];

DenMatrix 

public ref T this[int x, int y] => ref __array1d[x + y * Width];

Теперь тот же тест показывает разные результаты:

Data Size          : 4000 x 4000
Naked 2d Array     : 71 milliseconds
Naked Jagged Array : 68 milliseconds
Jagged Wrapper     : 77 milliseconds
Dense Wrapper      : 355 milliseconds
2d Wrapper         : 79 milliseconds
Faster versions:
FastMatrix         : 144 milliseconds
FastMatrix.Map     : 132 milliseconds

Как видите, обертки Jagged / 2d имеют почти такую ​​же производительность, как и их "голые" аналоги.Реализация Dense по-прежнему значительно медленнее (возможно, из-за ручного расчета индекса в дополнение к проверкам границ CRL), а «более быстрые версии» из другого ответа находятся посередине.

0 голосов
/ 11 октября 2018
  1. Почему зубчатая оболочка медленнее, чем двумерная оболочка?

Я не могу воссоздать результаты вашего теста, используя этот код: 

Data Size          : 4000 x 4000
Naked 2d Array     : 188 milliseconds
Naked Jagged Array : 202 milliseconds
Jagged Wrapper     : 311 milliseconds
Dense Wrapper      : 501 milliseconds
2d Wrapper         : 343 milliseconds
Можно ли сделать так, чтобы обертка работала так же быстро, как и голая?

Давайте попробуем:

  • , упростив Get(x, y)и Set(x, y, value) методы, позволяющие самим массивам проверять границы: 

    public T this[int x, int y]
{
    get
    {
        try {
            return _array[x, y]; 
        } catch (IndexOutOfRangeException e) {
            throw new Exception(String.Format(
                "index ({0}, {1}) exceeds size of Matrix ({2}, {3})",
                x, y, Width, Height
            ));
        }
    }
    set
    {
        try {
            _array[x, y] = value; 
        } catch (IndexOutOfRangeException e) {
            throw new Exception(String.Format(
                "index ({0}, {1}) exceeds size of Matrix ({2}, {3})",
                x, y, Width, Height
            ));
        }
    }
}

    Результаты: 

    Data Size          : 4000 x 4000
Naked 2d Array     : 186 milliseconds
matrix (2d Wrapper): 308 milliseconds
FastMatrix         : 246 milliseconds

  • Использование метода map (называется Select в Linq): 

    public FastMatrix<R> Map<R>(Func<T, R> func) where R : struct, IComparable<R>
{
    FastMatrix<R> array2d = new FastMatrix<R>(Width, Height);

    for (int x = 0; x < Width; x++)
    {
        for (int y = 0; y < Height; y++)
        {
            array2d._array[x, y] = func(_array[x, y]);
        }
    }
    return array2d;
}

    вызов map: 

    FastMatrix<double> dFastMatrix2 = intFastMatrix.Map(v => (double)v / 255.0);

    Результаты: 

    Data Size          : 4000 x 4000
Naked 2d Array     : 186 milliseconds
matrix (2d Wrapper): 308 milliseconds
FastMatrix.Map     : 184 milliseconds

    Это так же быстро, как голый2d Array!

Краткое описание: 

Data Size          : 4000 x 4000
Naked 2d Array     : 186 milliseconds
Naked Jagged Array : 200 milliseconds
Jagged Wrapper     : 308 milliseconds
Dense Wrapper      : 486 milliseconds
2d Wrapper         : 308 milliseconds
Fast versions:
FastMatrix         : 246 milliseconds
FastMatrix.Map     : 184 milliseconds

Полный код здесь .

...