Является ли представление большой матрицы в виде одномерного массива более эффективным, чем двумерный массив?

Question

контекст

Я реализую алгоритм вырезания шва.

Я представляю пиксели на изображении в виде одномерного массива

private int[] picture;

каждый int представляет RGB пикселя.

Для доступа к пикселям я использую вспомогательные методы, такие как:

private int pixelToIndex(int x, int y) {return (y * width()) + x;}

Альтернативой было бы хранить в 2D массиве:

private int[][] picture;

Алгоритм вырезания шва состоит из двух частей.

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

Во-вторых, он удаляет этот связанный шов.

Для вертикальных швов я отмечаю удаляемый пиксель -1 и создайте новый массив картинок, пропуская удаленные пиксели следующим образом:

int i = 0, j = 0;
while (i < temp.length) {
    if (picture[j] != -1) {
        temp[i++] = picture[j];
    }
    j++;
}
picture = temp;

Для горизонтальных швов с учетом конкретного столбца я сдвигаю все пиксели после удаленного пикселя этого столбца на одну строку следующим образом:

for (int i = 0; i < temp.length; i++) {
    int row = indexToY(i);
    int col = indexToX(i);
    int deletedCell = seam[col];

    if (row >= deletedCell) temp[i] = picture[i + width()];
    else temp[i] = picture[i];
}
picture = temp;

Вопрос

Очевидно, что 1D-массив использует меньше физической памяти из-за накладных расходов для каждого подмассива, но, учитывая то, как я выполняю итерацию матрицы, 2D-массив будет более эффективно кэшироваться ЦП и, следовательно, более эффективно?

Как будут отличаться массивы в том, как они будут загружаться в кэш процессора и оперативную память? Будет ли часть 1D-массива попадать в L1-кеш? Как бы массив 1D и 2D был загружен в память? Будет ли это зависеть от размера массива?

Answer 1

Массив целых чисел просто представлен так: массив значений int. Массив массивов... добавляет определенные накладные расходы. Итак, короткий ответ: при работе с действительно большими объемами данных; простые одномерные массивы - ваш друг.

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

Кроме того: на конкретные показатели производительности влияет множество различных переменных. Итак, вы хотите сначала выполнить профилирование; и посмотрите, что происходит с другим оборудованием, различными наборами данных и так далее.

И еще одно примечание: иногда для хруста реального числа; это также может быть жизнеспособным вариантом для реализации чего-то в C++, может делать вызовы через JNI. Это действительно зависит от характера вашей проблемы; как часто вещи будут использоваться; ожидаемое пользователями время отклика; и так далее.

Answer 2

У Java есть массивы массивов для многомерных массивов. В твоем случае int[][] это массив int[] (и конечно int[] это массив int). Итак, матрица представлена ​​в виде набора строк и указателей для каждой строки. В этом случае это означает, что матрица NxM занимает NxM для данных и массива указателей.

Так как вы можете представить любую матрицу в виде массива, вы получите меньшее потребление памяти при ее хранении.

С другой стороны, манипулирование адресом в том случае, если 2D-матрица представлена ​​в виде арки, не так уж сложно.

Если мы предполагаем, что у вас есть матрица, к которой обращается NxM, и массив размером NxM, представляющий эту матрицу, вы можете получить доступ к элементу Matrix[x,y] как Array[x*n+y],

Array[i] компактен и имеет высокую вероятность быть в кеше L1 или даже в кеше регистров.

Matrix[x,y] требуется одно чтение памяти и дополнение Array[x*n+y] требуется одно умножение и одно сложение.

Итак, я положу свои два цента на Array, но в любом случае это должно быть проверено (не забудьте дождаться времени прогрева JIT-компилятора)