Возможные улучшения Java ArrayList / Scala ArrayBuffer?

Question

В настоящее время алгоритм «растущего» вычисляет, что Array, поддерживающий ArrayList / ArrayBuffer, слишком мал для запрашиваемой операции, и копирует содержимое в начало большего массива.

jsuereth очень хорошо объясняет это в комментариях этой темы :

ArrayBuffer отлично подходит для добавления, но не так хорош для подготовки. в Java ArrayList на самом деле попытается амортизировать затраты, чтобы подготовиться, сделать это немного лучше в моем мнение. Да ArrayBuffer это наверное достаточно хорошо, если вы просто добавляете на список и элементы индексации.

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

I. e.:

• , если append требуется больший массив, скопируйте существующее содержимое в начало нового массива:

  [x|x|x|x|x|x] 
         |
         v
  [x|x|x|x|x|x| | | | | ]
  

• , если prepend требуется больший массив, скопируйте существующее содержимое в конец нового массива:

  [x|x|x|x|x|x] 
         |
         v
  [ | | | | |x|x|x|x|x|x]
  

Решит ли это проблемы с производительностью для prepend, и в целом сделает алгоритм немного более адаптивным к шаблонам использования? (В худшем случае было бы добавление / добавление большого количества материала ...)

Существуют ли какие-либо другие структуры данных, которые уже учитывают последнюю операцию при расширении базовой структуры?

Answer 1

Возможно, вам нужен ArrayDeque. У этого есть операция O (1) для добавления и добавления (если емкость не изменена)

У него есть массив, в котором он имеет индекс для head и tail, который позволяет ему записывать начальную или конечную позицию без необходимости перетасовывать все записи вниз / вверх.

Answer 2

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

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

Answer 3

Если вы не собираетесь делать много поисков, а просто будете выполнять линейные обходы, то перейдите к UnrolledBuffer - реализации развернутого связанного списка. В противном случае Vector и его +: должны быть эффективным выбором.

Answer 4

Вы можете использовать ArrayDeque для структуры данных на основе массива с быстрым предопределением.