Сравнение производительности массива массивов и многомерных массивов

Java и C # выделяют память совершенно иначе, чем C ++. Фактически, в .NET наверняка все массивы AoA будут близко друг к другу, если они будут выделены один за другим, потому что в памяти есть только один непрерывный фрагмент без какой-либо фрагментации.

Но это все еще верно для C ++ и все еще имеет смысл, если вам нужна максимальная скорость. Хотя вам не следует следовать этому совету каждый раз, когда вам нужен многомерный массив, вы должны сначала написать поддерживаемый код, а затем профилировать его, если он медленный, преждевременная оптимизация является корнем всего зла в этом мире.

Стоит ли это усилий? Это слишком низкий уровень проблемы оптимизации для такого языка, как Java?

Вообще говоря, это не стоит усилий. Лучшая стратегия, чтобы забыть об этой проблеме в первой версии вашего приложения и реализовать ее простым (то есть простым в обслуживании) способом. Если первая версия работает слишком медленно для ваших требований, воспользуйтесь инструментом профилирования, чтобы найти узкие места приложения. Если профилирование предполагает, что массивы массивов, вероятно, являются проблемой, проведите несколько экспериментов, чтобы изменить структуры данных на моделируемые многомерные массивы и профилировать, чтобы увидеть, имеет ли это существенное значение. [Я подозреваю, что это не будет иметь большого значения. Но самое важное - не тратить время на оптимизацию чего-то без надобности.]

Должны ли мы просто отказаться от массивов и использовать списки даже для примитивов?

Я бы не пошел так далеко. Предполагая, что вы имеете дело с массивами заранее определенного размера:

• массивы объектов будут немного быстрее, чем эквивалентные списки объектов, и
• массивы примитивов будут значительно быстрее и занимать значительно меньше места, чем эквивалентные списки примитивов-оберток.

С другой стороны, если вашему приложению необходимо «увеличить» массивы, использование списка упростит ваш код.

Я бы не стал тратить силы на использование одномерного массива в качестве многомерного массива в Java, потому что здесь нет синтаксиса, который мог бы помочь. Конечно, можно определить функции (методы), чтобы скрыть работу за вас, но при использовании массива массивов вы просто вызываете функцию, а не следуете за указателем. Даже если компилятор / интерпретатор ускорит это для вас, я все равно не думаю, что это того стоит. Кроме того, вы можете столкнуться с проблемами при попытке использовать код, который ожидает массивы 2D (или N-Dim), которые ожидаются как массивы массивов. Я уверен, что наиболее общий код будет написан для таких массивов на Java. Также можно дешево переназначить строки (или столбцы, если вы решите так думать).

Если вы знаете, что этот массив multidim является узким местом, вы можете проигнорировать то, что я сказал, и посмотреть, поможет ли ручная оптимизация.

Из личного опыта в Java, многомерные массивы намного медленнее, чем одномерные массивы, если загружается большой объем данных или осуществляется доступ к элементам данных, которые находятся в разных положениях. Я написал программу, которая делала снимок экрана в формате BMP, а затем просматривала снимок экрана в поисках меньшего изображения. Загрузка снимка экрана (примерно 3 мб) в многомерный массив (трехмерный, [xPos] [yPos] [color] (где color = 0 - значение красного цвета и так далее)) заняла 14 секунд. Чтобы загрузить его в одномерный массив, потребовалась 1 секунда. Выигрыш от нахождения меньшего изображения на большом изображении был аналогичным. На поиск меньшего изображения в большом изображении ушло около 28 секунд, когда оба изображения хранились в виде многомерных массивов. Поиск меньшего изображения в большом изображении занимал около секунды, когда оба изображения хранились в виде одномерных массивов. Тем не менее, я сначала написал свою программу, используя размерные массивы для удобства чтения.