Многомерный массив против одномерного

Question

Это в основном повторение этого вопроса: Java: многомерный массив против одномерного , но для C #.

У меня есть определенное количество элементов, которые имеют смыслхранить как сетку.Должен ли я использовать массив [x * y] или массив [x] [y]?

РЕДАКТИРОВАТЬ: О, так что есть одномерный массив [x * y], многомерный массив [x, y] инеровный массив [x] [y], и я, вероятно, хочу неровный?

Answer 1

Я провел тест на неоправданно больших массивах и был удивлен, увидев, что неровные массивы ([y] [x]) оказываются быстрее, чем одномерный массив с умножением вручную [y * ySize + x]. А многомерные массивы [,] медленнее, но не намного.

Конечно, вам придется тестировать свои конкретные массивы, но может показаться, что разница невелика, поэтому вам следует просто использовать тот подход, который подходит вам лучше всего.

0.280 (100.0% | 0.0%) 'Jagged array 5,059x5,059 - 25,593,481'
|       0.006 (2.1% | 2.1%) 'Allocate'
|       0.274 (97.9% | 97.9%) 'Access'


0.336 (100.0% | 0.0%) 'TwoDim array 5,059x5,059 - 25,593,481'
|       0.000 (0.0% | 0.0%) 'Allocate'
|       0.336 (99.9% | 99.9%) 'Access'


0.286 (100.0% | 0.0%) 'SingleDim array 5,059x5,059 - 25,593,481'
|       0.000 (0.1% | 0.1%) 'Allocate'
|       0.286 (99.9% | 99.9%) 'Access'



0.552 (100.0% | 0.0%) 'Jagged array 7,155x7,155 - 51,194,025'
|       0.009 (1.6% | 1.6%) 'Allocate'
|       0.543 (98.4% | 98.4%) 'Access'


0.676 (100.0% | 0.0%) 'TwoDim array 7,155x7,155 - 51,194,025'
|       0.000 (0.0% | 0.0%) 'Allocate'
|       0.676 (100.0% | 100.0%) 'Access'


0.571 (100.0% | 0.0%) 'SingleDim array 7,155x7,155 - 51,194,025'
|       0.000 (0.1% | 0.1%) 'Allocate'
|       0.571 (99.9% | 99.9%) 'Access'



for (int i = 6400000; i < 100000000; i *= 2)
{
    int size = (int)Math.Sqrt(i);
    int totalSize = size * size;

    GC.Collect();

    ProfileTimer.Push(string.Format("Jagged array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[][] Jagged = new double[size][];
    for (int x = 0; x < size; x++)
    {
        Jagged[x] = new double[size];
    }

    ProfileTimer.PopPush("Allocate", "Access");

    double total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                total += Jagged[y][x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("Jagged array");


    GC.Collect();

    ProfileTimer.Push(string.Format("TwoDim array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[,] TwoDim = new double[size,size];

    ProfileTimer.PopPush("Allocate", "Access");

    total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            for (int x = 0; x < size; x++)
            {
                total += TwoDim[y, x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("TwoDim array");


    GC.Collect();

    ProfileTimer.Push(string.Format("SingleDim array {0:N0}x{0:N0} - {1:N0}", size, totalSize));

    ProfileTimer.Push("Allocate");

    double[] Single = new double[size * size];

    ProfileTimer.PopPush("Allocate", "Access");

    total = 0;
    for (int trials = 0; trials < 10; trials++)
    {
        for (int y = 0; y < size; y++)
        {
            int yOffset = y * size;
            for (int x = 0; x < size; x++)
            {
                total += Single[yOffset + x];
            }
        }
    }

    ProfileTimer.Pop("Access");
    ProfileTimer.Pop("SingleDim array");
}

Answer 2

В C # есть много преимуществ использования зубчатых массивов (array[][]).На самом деле они часто превосходят многомерные массивы.

При этом я бы лично использовал многомерный или зубчатый массив вместо одномерного массива, поскольку это более близко соответствует проблемному пространству.Использование одномерного массива увеличивает сложность вашей реализации, которая не дает реальных преимуществ, особенно по сравнению с двумерным массивом, поскольку внутренне это все еще один блок памяти.

Answer 3

Плюсы array[x,y]:
- Runtime выполнит больше проверок для вас . Каждый индекс доступа будет проверен, чтобы быть в пределах допустимого диапазона. С другим подходом вы можете легко сделать что-то вроде a[y*numOfColumns + x], где x может быть больше, чем «количество столбцов», и этот код извлечет некоторое неправильное значение, не вызывая исключения.
- Более понятный индексный доступ . a[x,y] чище, чем a[y*numOfColumns + x]

Плюсы array[x*y]:
- Упрощенная итерация по всему массиву . Вам нужен только один цикл вместо двух.

И победитель ... Я бы предпочел array[x,y]