Версия TL; DR для тех, кто не хочет фона, представляет собой следующий конкретный вопрос:
Вопрос
Почему Java не реализует истинные многомерные массивы? Есть ли твердая техническая причина? Что мне здесь не хватает?
Фон
Java имеет многомерные массивы на уровне синтаксиса, поскольку можно объявить
int[][] arr = new int[10][10];
но кажется, что это действительно не то, что можно было ожидать. Вместо того, чтобы JVM выделял непрерывный блок ОЗУ, достаточно большой для хранения 100 int s, он выводится как массив массивов int s: поэтому каждый уровень является непрерывным блоком ОЗУ, но вещь как в целом нет. Таким образом, доступ к arr[i][j] довольно медленный: JVM должен
- найдите
int[], сохраненный вarr[i]; - укажите это, чтобы найти
int, сохраненный вarr[i][j].
Это включает в себя запрос объекта перейти от одного слоя к другому, что довольно дорого.
Почему Java делает это
На одном уровне нетрудно понять, почему это невозможно оптимизировать для простого масштабирования и добавления, даже если все они были выделены в одном фиксированном блоке. Проблема в том, что arr[3] является ссылкой, и может быть изменена. Поэтому, хотя массивы имеют фиксированный размер, мы могли бы легко написать
arr[3] = new int[11];
и теперь масштаб и добавление завинчиваются, потому что этот слой вырос. Во время работы вам нужно знать, все ли все те же размеры, что и раньше. Кроме того, конечно, это будет затем распределено в другом месте в ОЗУ (это должно быть, поскольку оно больше, чем то, что он заменяет), поэтому он даже не в нужном месте для масштабирования и добавления.
Какая проблема с этим
Мне кажется, что это не идеально, и это по двум причинам.
Во-первых, он медленный. Тест, который я запускал с помощью этих методов для суммирования содержимого одномерного или многомерного массива, занимал почти в два раза (714 секунд против 371 секунды) для многомерного случая (a int[1000000] и int[100][100][100] соответственно, заполненных случайным int, запустите 1000000 раз с теплым кешем).
public static long sumSingle(int[] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
total+=arr[i];
return total;
}
public static long sumMulti(int[][][] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
for (int j=0; j<arr[0].length; j++)
for (int k=0; k<arr[0][0].length; k++)
total+=arr[i][j][k];
return total;
}
Во-вторых, поскольку он медленный, он тем самым поощряет неясное кодирование. Если вы столкнулись с чем-то критичным по производительности, которое было бы естественно сделано с помощью многомерного массива, у вас есть стимул писать его как плоский массив, даже если это делает неестественным и трудночитаемым. У вас остался неприятный выбор: скрытый код или медленный код.
Что можно сделать с этим
Мне кажется, что основная проблема может быть легко решена. Единственная причина, как мы видели ранее, в том, что она не может быть оптимизирована, заключается в том, что структура может измениться. Но у Java уже есть механизм для того, чтобы сделать ссылки неизменяемыми: объявите их как final.
Теперь, просто объявив его
final int[][] arr = new int[10][10];
недостаточно хорош, потому что только arr, то есть final здесь: arr[3] все еще нет и может быть изменен, поэтому структура может по-прежнему меняться. Но если бы у нас был способ объявить вещи так, чтобы он был final повсюду, за исключением нижнего уровня, где хранятся значения int, тогда у нас будет целая неизменяемая структура, и все это можно было бы выделить как один блок и индексируется с помощью масштабирования и добавления.
Как бы это выглядело синтаксически, я не уверен (я не разработчик языка). Может быть,
final int[final][] arr = new int[10][10];
хотя, по общему признанию, это выглядит немного странно. Это означало бы: final в верхнем слое; final на следующем уровне; а не final в нижнем слое (иначе сами значения int были бы неизменными).
Конечность во всей полноте позволяла компилятору JIT оптимизировать это, чтобы дать производительность производительности для одномерного массива, который затем уберет искушение закодировать этот способ, чтобы обойти медленность многомерных массивов.
(Я слышал слух о том, что С# делает что-то подобное, хотя я также слышу еще один слух о том, что реализация CLR настолько плоха, что этого не стоит... возможно, это просто слухи...)
Вопрос
Итак, почему Java не реализует истинные многомерные массивы? Есть ли твердая техническая причина? Что мне здесь не хватает?
Update
Причудливая сторона примечания: разница в таймингах снижается до нескольких процентов, если вы используете int для текущей цели, а не для long. Почему была бы такая небольшая разница с int, и такая большая разница с a long?
Код бенчмаркинга
Код, который я использовал для бенчмаркинга, в случае, если кто-то хочет попытаться воспроизвести эти результаты:
public class Multidimensional {
public static long sumSingle(final int[] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
total+=arr[i];
return total;
}
public static long sumMulti(final int[][][] arr) {
long total = 0;
for (int i=0; i<arr.length; i++)
for (int j=0; j<arr[0].length; j++)
for (int k=0; k<arr[0][0].length; k++)
total+=arr[i][j][k];
return total;
}
public static void main(String[] args) {
final int iterations = 1000000;
Random r = new Random();
int[] arr = new int[1000000];
for (int i=0; i<arr.length; i++)
arr[i]=r.nextInt();
long total = 0;
System.out.println(sumSingle(arr));
long time = System.nanoTime();
for (int i=0; i<iterations; i++)
total = sumSingle(arr);
time = System.nanoTime()-time;
System.out.printf("Took %d ms for single dimension\n", time/1000000, total);
int[][][] arrMulti = new int[100][100][100];
for (int i=0; i<arrMulti.length; i++)
for (int j=0; j<arrMulti[i].length; j++)
for (int k=0; k<arrMulti[i][j].length; k++)
arrMulti[i][j][k]=r.nextInt();
System.out.println(sumMulti(arrMulti));
time = System.nanoTime();
for (int i=0; i<iterations; i++)
total = sumMulti(arrMulti);
time = System.nanoTime()-time;
System.out.printf("Took %d ms for multi dimension\n", time/1000000, total);
}
}
