Java: многомерный массив по сравнению с одномерным

Используйте первый вариант (3-мерный), потому что его легче понять и меньше шансов сделать какую-то логическую ошибку (особенно если вы используете его для моделирования 3-мерного пространства)

Если вы выберете второй маршрут, то вы ' re придется выполнять арифметические действия для каждого доступа к массиву. Это будет болезненно и подвержено ошибкам (если вы не заключите его в класс, обеспечивающий эту функциональность).

Я не верю, что есть какая-либо (значительная) оптимизация при выборе плоского массива (особенно с учетом арифметики, используемой для индексации в нем). Как всегда при оптимизации, вам нужно будет провести некоторые измерения и определить, действительно ли это того стоит.

На современных процессорах доступ к некэшированной памяти в сотни раз медленнее, чем арифметика (см. эту презентацию и прочтите То, что каждый программист должен знать о памяти ). Вариант а) приведет примерно к 3 поискам в памяти, тогда как вариант б) приведет примерно к 1 поиску в памяти. Также могут не работать алгоритмы предварительной выборки ЦП. Таким образом, вариант b) может быть быстрее в некоторых ситуациях (это горячая точка, и массив не помещается в кеш процессора). Насколько быстрее? - это будет зависеть от приложения.

Лично я сначала использовал бы вариант а), потому что это упростит код. Если профилировщик показывает, что доступ к массиву является узким местом, я бы преобразовал его в вариант b), чтобы была пара вспомогательных методов для чтения и записи значений массива (таким образом, беспорядочный код будет ограничен этими двумя методы).

Я провел тест для сравнения 3-мерных массивов int (столбец «Multi») с эквивалентными 1-мерными массивами int (столбец «Single»). Код здесь и тесты здесь . Я запускал его на 64-разрядной версии jdk1.6.0_18, Windows 7 x64, Core 2 Quad Q6600 @ 3,0 ГГц, 4 ГБ DDR2, используя параметры JVM -server -Xmx3G -verbose: gc -XX: + PrintCompilation (Я удалил отладочные данные из следующих результатов). Результаты были следующими:

Out of 20 repeats, the minimum time in milliseconds is reported.

Array dimensions: 100x100x100 (1000000)
            Multi   Single
Seq Write   1       1
Seq Read    1       1
Random Read 99      90    (of which generating random numbers 59 ms)

Array dimensions: 200x200x200 (8000000)
            Multi   Single
Seq Write   14      13
Seq Read    11      8
Random Read 1482    1239    (of which generating random numbers 474 ms)

Array dimensions: 300x300x300 (27000000)
            Multi   Single
Seq Write   53      46
Seq Read    34      24
Random Read 5915    4418    (of which generating random numbers 1557 ms)

Array dimensions: 400x400x400 (64000000)
            Multi   Single
Seq Write   123     111
Seq Read    71      55
Random Read 16326   11144    (of which generating random numbers 3693 ms)

Это показывает, что одномерный массив работает быстрее. Хотя различия настолько малы, что для 99% приложений не будут заметны.

Я также провел несколько измерений, чтобы оценить накладные расходы на генерацию случайных чисел в тесте Random Read, заменив preventOptimizingAway + = array.get (x, y, z); на preventOptimizingAway + = x * y * z; и вручную добавил измерения в приведенную выше таблицу результатов. Генерация случайных чисел занимает 1/3 или меньше общего времени теста произвольного чтения, поэтому доступ к памяти доминирует в тесте, как и ожидалось. Было бы интересно повторить этот тест с массивами из 4 и более измерений. Вероятно, это увеличило бы разницу в скорости, потому что самые верхние уровни многомерного массива поместятся в кэш ЦП, и только другие уровни потребуют поиска в памяти.