Самый быстрый способ чтения / хранения большого количества многомерных данных? (Джава)
У меня три вопроса о трех вложенных циклах:
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
}
}
}
И мне нужно хранить все вычисленные значения. Мой стандартный подход - использовать 3D-массив:
values[x][y][z] = 1; // test value
но это оказывается медленным: для завершения этого цикла требуется 192 мс, где одно int-присваивание
int value = 1; // test value
занимает всего 66 мс
1) Почему массив такой относительно медленный?
2) И почему это становится еще медленнее, когда я помещаю это во внутренний цикл:
values[z][y][x] = 1; // (notice x and z switched)
Это займет больше 4 секунд!
3) Самое главное: могу ли я использовать структуру данных, которая является такой же быстрой, как назначение одного целого числа, но может хранить столько же данных, сколько и трехмерный массив?
5 ответов
1) Почему массив такой относительно медленный?
Как указывали другие, вы сравниваете яблоки с апельсинами. Тройной массив медленный, потому что ему нужно разыменовать (по крайней мере, внутренне - да, "в Java нет указателей") три раза; но опять же, вы не можете ссылаться на одну целочисленную переменную...
2) И почему это становится еще медленнее, когда я помещаю это во внутренний цикл:
values[z][y][x] = 1; // (notice x and z switched)
Потому что вы уменьшили когерентность кэша. Наиболее быстро изменяющиеся индексы должны быть последними, чтобы большинство обращений к памяти происходило рядом друг с другом, в пределах одних и тех же блоков кэша, вместо того, чтобы заставлять процессор ждать, пока блоки будут считаны из основного ОЗУ.
3) Самое главное: могу ли я использовать структуру данных, которая является такой же быстрой, как назначение одного целого числа, но может хранить столько же данных, сколько и трехмерный массив?
Нет. Такой структуры нет, поскольку целочисленная переменная вписывается в машинный регистр (даже быстрее, чем кэш памяти процессора) и всегда может быть доступна быстрее, чем все, что вы упомянули. Скорости процессора намного, намного выше, чем скорости основной памяти. Если ваш "рабочий набор" (данные, с которыми вам нужно работать) не помещается в регистры или кэш, вам придется заплатить штраф за его извлечение из ОЗУ (или, что еще хуже, с диска).
При этом Java выполняет проверку границ при каждом доступе к массиву и, похоже, не слишком умен в оптимизации проверки границ. Следующее сравнение может представлять интерес:
public static long test1(int[][][] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[x][y][z] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static long test2(int [] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[z + y*400 + x*400*300] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static void main(String[] args) {
int[][][] a1 = new int[400][300][400];
int[] a2 = new int[400*300*400];
int n = 20;
System.err.println("test1");
for (int i=0; i<n; i++) {
System.err.print(test1(a1) + "ms ");
}
System.err.println();
System.err.println("test2");
for (int i=0; i<n; i++) {
System.err.print(test2(a2) + "ms ");
}
System.err.println();
}
Вывод в моей системе
test1
164ms 177ms 148ms 149ms 148ms 147ms 150ms 151ms 152ms 154ms 151ms 150ms 148ms 148ms 150ms 148ms 150ms 148ms 148ms 149ms
test2
141ms 153ms 130ms 130ms 130ms 133ms 130ms 130ms 130ms 132ms 129ms 131ms 130ms 131ms 131ms 130ms 131ms 130ms 130ms 130ms
Поэтому есть место для улучшения... но я действительно не думаю, что оно того стоит.
public static void main( String[] args ) {
int[][][] storage = new int[ 400 ][ 300 ][ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storage[x][y][z] = 5;
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
Побежал с -Xmx1g
Время было: 0,188 секунды.
Это кажется чертовски быстрым... вы смотрите на 48 МИЛЛИОНОВ элементов в самом внутреннем цикле.
Homerolling глупая маленькая структура данных..
public static void main( String[] args ) {
StorerGuy[] storerGuys = new StorerGuy[ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storerGuys[x] = new StorerGuy( x, y, z, 5 );
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
public static class StorerGuy {
public int x;
public int y;
public int z;
public int value;
StorerGuy( int x, int y, int z, int value ) {
this.x = x;
this.y = y;
this.z = z;
this.value = value;
}
}
Время было: 0,925 секунды.
Что быстрее, чем 4 секунды, которые у вас были в вашем примере смешанного заказа.
Я думаю, что мульти-массивы слишком много для проблемы. Вам лучше с более сложной структурой данных, так как все данные будут храниться в одной ячейке памяти (x, y, z, value).
Java является ОО-языком. В большинстве случаев вы должны использовать объекты, а не странные структуры данных, такие как int[][][]
Вы пробовали это:
Object[][][] store = new Object[ 400 ][300][400];
for (int x=0; x<400; x++)
{
Object[][] matrix = store[x];
for (int y=0; y<300; y++)
{
Object[] line = matrix[y];
for (int z=0; z<400; z++)
{
// compute and store value
line[z] = // result;
}
}
}
это может улучшить ваш кэш побеждает.
Я предполагаю, что это имеет отношение к кешированию и регистрам и принципу локальности памяти.
Java должна получить доступ к тысячам дополнительных байтов памяти при хранении в массиве. С помощью одной переменной она может просто сохранить это значение в кеше и просто обновлять его.
Кеш недостаточно велик, чтобы вместить весь многомерный массив, поэтому Java должна постоянно обновлять кеш в память и из памяти. Время доступа к кешу намного быстрее времени доступа к памяти.
Я даже не понимаю, почему вы бы сделали этот тест, хотя. Если вам нужно хранить много данных в многомерном массиве, использование одной переменной не поможет, даже если это быстрее.
Кроме того, причина, по которой параметры переключаются при доступе к массиву, заключается в том, что вы перепрыгиваете в памяти гораздо больше (намного больше пропускает кэш), чем когда вы просто выполняете итерацию другим способом.
Учитывая, что массив огромен, объем используемой памяти, необходимые косвенные ссылки (многомерный массив - это массивы ссылок на массивы...), это не кажется мне медленным. Когда вы переключаете x и z, вы, вероятно, уничтожаете кеш.
Для сравнения, вы можете хранить все в плоском массиве... Это улучшит скорость хранения... но тогда поиск будет более сложным и гораздо более медленным.
int k = 0;
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
arr[k++] = val;
}
}
}