Что быстрее: список массивов или перебор всех комбинаций данных?

Я программирую что-то на Java, для контекста см. этот вопрос: Процесс принятия решения Марковской модели в Java

У меня есть два варианта:

byte[MAX][4] mypatterns;

или ArrayList мои шаблоны

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

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

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

Основываясь на теории и на том, что я слышал, динамические массивы очень неэффективны.

Мой вопрос: будет ли перебор массива, скажем, из 200 элементов, быстрее, чем добавление объекта в динамический массив?

Изменить>>>

Дополнительная информация:

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

java performance dynamic-arrays dynamic-memory-allocation memory-pool
person bigcodeszzer    schedule 21.12.2015    source источник
comment
Под динамическим массивом вы имеете в виду List, например ArrayList? Какую теорию и где вы слышали, что ArrayList очень неэффективен по сравнению с простым массивом? Нет, это не так.   -  person Andreas    schedule 21.12.2015
comment
Да и я как раз редактировал.   -  person bigcodeszzer    schedule 21.12.2015
comment
Я полагаю, ArrayList не может быть неэффективным, но я слышал, что статические массивы во много раз быстрее. Не уверен, что это правда, но я так понимаю.   -  person bigcodeszzer    schedule 21.12.2015
comment
Хотя обычно ArrayList неизбежен, в этом случае я действительно мог выбирать, поэтому я задаю вопрос.   -  person bigcodeszzer    schedule 21.12.2015
comment
Мне кажется, что вы держите рабочее окно для вычисления временного ряда или чего-то подобного. Если это так, я рекомендую круговой буфер.   -  person Alex Suo    schedule 21.12.2015
comment
Маловероятно, что любые проблемы с производительностью, которые у вас могут возникнуть, вызваны использованием ArrayList вместо простого массива. Не усложняйте свой код для этого, если только профилировщик не покажет вам, что ArrayList вызывает снижение производительности.   -  person Andreas    schedule 21.12.2015
comment
Если @AlexSuo прав и вы используете круговой буфер, вам следует использовать ArrayDeque. Это очень эффективно для этой цели.   -  person Andreas    schedule 21.12.2015
comment
@AlexSuo По сути да, но меня больше беспокоит, как сохранить результаты. Что касается самого окна, я просто собирался использовать стек.   -  person bigcodeszzer    schedule 21.12.2015
comment
Статический стек.   -  person bigcodeszzer    schedule 21.12.2015
comment
@Andreas Андреас Вы действительно правы, я должен сначала использовать профилировщик, но мне также просто любопытен вопрос «теоретически»   -  person bigcodeszzer    schedule 21.12.2015
comment
На самом деле, если вы посмотрите на API для Stack, он говорит: Более полный и согласованный набор операций стека LIFO предоставляется интерфейсом Deque и его реализациями, которые следует использовать вместо этого класса.   -  person azurefrog    schedule 21.12.2015
comment
@azurefrog Еще не добрался.   -  person bigcodeszzer    schedule 21.12.2015
comment
@azurefrog Эти классы выглядят так, как будто они предназначены для динамических стеков, у меня статическая длина   -  person bigcodeszzer    schedule 21.12.2015

Ответы (3)


arrow_upward
1
arrow_downward

Вы правы, я должен сначала использовать профилировщик, но мне также просто любопытен вопрос «теоретически».

«Теория» слишком сложна. Существует слишком много альтернатив (разных способов реализации этого), чтобы их анализировать. Кроме того, фактическая производительность для каждой альтернативы будет зависеть от аппаратного обеспечения, JIT-компилятора, размеров структуры данных и шаблонов доступа и обновления в вашем (реальном) приложении на (реальных) входных данных.

И есть вероятность, что это действительно не имеет значения.

Короче говоря, никто не может дать вам хорошо обоснованный теоретический ответ. Лучшее, что мы можем дать, — это рекомендации, основанные на интуитивных представлениях о производительности и/или основанные на здравом смысле разработки программного обеспечения:

  • более простой код легче писать и поддерживать,

  • компилятор является более последовательным оптимизатором1, чем человек,

  • время, потраченное на оптимизацию кода, который не нуждается в оптимизации, потрачено впустую.

1 — Конечно, из-за большой кодовой базы. При наличии достаточного количества времени и терпения человек может лучше справиться с некоторыми проблемами, но это не является устойчивым для большой базы кода и не принимает во внимание тот факт, что 1) компиляторы постоянно совершенствуются, 2) оптимальный код может зависеть от вещей, которые человек не может учесть, и 3) компилятор не устает и не делает ошибок.

person Stephen C    schedule 21.12.2015

arrow_upward
1
arrow_downward

Самый быстрый способ перебирать байты - это отдельные массивы. Более быстрый способ обработки - это типы int или long, так как обработка 4-8 байтов за раз быстрее, чем обработка по одному байту за раз, однако это скорее зависит от того, что вы делаете. Примечание: byte[4] на самом деле составляет 24 байта на 64-битной JVM, что означает, что вы неэффективно используете кеш ЦП. Если вы не знаете точный размер, который вам нужен, возможно, вам лучше создать буфер большего размера, чем вам нужно, даже если вы не используете весь буфер. то есть в случае байта [][] вы используете в 6 раз больше памяти, которая вам действительно нужна.

person Peter Lawrey    schedule 21.12.2015
comment
Вы имеете в виду размер байта или количество байтов? Я думал, что в Java выравнивание памяти кратно 8? - person bigcodeszzer; 21.12.2015
comment
@bigcodeszzer Выравнивание памяти по умолчанию для объектов составляет 8 байтов. Однако, если вам нужна компактная и эффективная структура данных, вам нужен байт [] или аналогичный для всех данных, чтобы каждый байт использовал только байт. - person Peter Lawrey; 22.12.2015
comment
О, я вижу, я думаю, я мог бы сделать это и выполнить цикл с i+=4 или что-то в этом роде. - person bigcodeszzer; 23.12.2015

arrow_upward
1
arrow_downward

Никакой разницы в производительности не будет видно, если вы установите initialCapacity на ArrayList. Вы говорите, что размер вашей коллекции никогда не может измениться, но что, если эта логика изменится? Используя ArrayList, вы получаете доступ ко множеству методов, таких как contains.

Как уже говорили другие люди, используйте ArrayList, если тесты производительности не говорят, что это узкое место.

person m.aibin    schedule 21.12.2015