Оптимизация доступа к массиву

Question

У меня есть массив 10х10 в Java, некоторые элементы в массиве которого не используются, и мне нужно пройти через все элементы как часть метода. Что было бы лучше сделать:

1. Просмотрите все элементы с помощью 2 для циклов и проверьте тип null, чтобы избежать ошибок, например,

   for(int y=0;y<10;y++){
       for(int x=0;x<10;x++){
          if(array[x][y]!=null)
               //perform task here
       }
   }
   

2. Или было бы лучше вести список всех использованных адресов ... Скажем, список точек?

3. Что-то другое, я не упомянул.

С нетерпением жду любых ответов :)

Answer 1

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

При этом можно попробовать несколько вещей, которые я использовал для успешной оптимизации моего Java-кода (, но не на Android JVM )

for(int y=0;y<10;y++){
    for(int x=0;x<10;x++){
       if(array[x][y]!=null)
            //perform task here
    }
}

в любом случае должен быть переработан в

for(int x=0;x<10;x++){
    for(int y=0;y<10;y++){
       if(array[x][y]!=null)
            //perform task here
    }
}

Часто вы получаете улучшение производительности от кэширования ссылки на строку. Пусть as предполагает, что массив имеет тип Foo[][]:

for(int x=0;x<10;x++){
    final Foo[] row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

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

Foo[] row;
for(int x=0;x<10;x++){
    row = array[x];
    for(int y=0;y<10;y++){
       if(row[y]!=null)
            //perform task here
    }
}

Если вам не нужно знать индексы элемента для выполнения задачи над ним, вы можете написать это как

for(final Foo[] row: array){
    for(final Foo elem: row
       if(elem!=null)
            //perform task here
    }
}

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

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

Другая проблема - нулевой тест. Сам нулевой тест не стоит дорого, но условный оператор, следующий за ним, стоит, так как вы получаете ветку в коде и теряете время на неправильных предсказаниях ветвления. То, что вы можете сделать, это использовать «нулевой объект», над которым можно будет выполнить задачу, но это будет неоперативный или что-то в равной степени благоприятное. В зависимости от задачи, которую вы хотите выполнить, она может работать, а может и не работать.

Надеюсь, это поможет.

Answer 2

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

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

for ( int x = 0; x < 10; ++x ) {
    for ( int y = 0; y < 10; ++y ) {
       if ( array[x][y] != null )
            //perform task here
    }
}

или

for ( Foo[] row : array ) {
    for ( Foo item : row ) {
       if ( item != null )
            //perform task here
    }
}

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

double sum = 0;

for ( Foo[] row : array ) {
    for ( Foo item : row ) {
       sum += item.value();
    }
}

Что касается того, что относится к Android, я не уверен; снова нужно протестировать и профилировать для любой оптимизации.

Answer 3

Вам лучше использовать List, чем массив, тем более что вы можете использовать не весь набор данных. Это имеет несколько преимуществ.

1. Вы не проверяете наличие нулей и не можете случайно попытаться использовать нулевой объект.
2. Более эффективное использование памяти, поскольку вы не выделяете память, которая может быть не использована.

Answer 4

Я согласен, что массив с нулевым тестом - лучший подход, если только вы не ожидаете малонаселенных массивов.

Причины этого:

1 - более эффективный объем памяти для плотных массивов (список должен хранить индекс)

2 - Более вычислительно эффективен для плотных массивов (вам нужно только сравнить значение, которое вы только что получили, с NULL, вместо того, чтобы также получать индекс из памяти).

Кроме того, небольшое предложение, но в Java особенно вам лучше подделать многомерный массив с одномерным массивом, где это возможно (квадратные / прямоугольные массивы в 2D). Проверка границ происходит только один раз за итерацию, а не дважды. Не уверен, что это все еще применяется в виртуальных машинах Android, но это традиционно было проблемой. Несмотря на это, вы можете игнорировать его, если цикл не является узким местом.

Answer 5

Зависит от того, насколько разреженной / плотной является ваша матрица.

Если она разреженная, лучше хранить список точек, если она плотная, используйте массив 2D.Если между ними, у вас может быть гибридное решение, хранящее список подматриц.

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

Я бы не рекомендовал вам использовать любое из этих решений без профилирования с вашим реальным приложением.

Answer 6

Удержание ArrayList точек было бы "излишним" из-за проблемы. У вас есть многомерный массив; лучший способ перебрать это с двумя вложенными циклами for. Если вы не можете изменить представление данных, это примерно так же эффективно, как и получается.

Просто убедитесь, что вы идете в порядке строк, а не в столбцах.