Самый эффективный способ хранения массива в Java?

Question

Я не слишком озабочен эффективностью времени (операция будет редка), а скорее об эффективности памяти: Могу ли я вырастить массив без временного использования всех значений дважды?

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

А как насчет того, что массивы фиксированного размера хранятся в другом массиве и перераспределяют/копируют этот верхний уровень? Оставит ли это фактические значения на месте?

Я знаю ArrayList, но мне нужно много контролировать доступ к массиву, и доступ должен быть очень быстрым. Например, я думаю, что предпочитаю a[i] - al.get(i).

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

Answer 1

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

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

Что о том, массивы фиксированного размера хранится в другом массиве и перераспределить /скопировать этот верхний уровень одного? Будет ли это оставить фактические значения на месте?

Вы имеете в виду массив массивов и рассматривать его как один большой массив, состоящий из конкатенации базовых массивов? Да, это сработало бы (подход «поддельный, сделав косвенный подход»), как и в Java, Object[][] - это просто массив указателей на Object[] экземпляров.

Answer 2

Посмотрите на System.arraycopy.

Answer 3

AFAIK единственный путь роста или уменьшения массива делает System.arraycopy

/** 
    * Removes the element at the specified position in this list. 
    * Shifts any subsequent elements to the left (subtracts one from their 
    * indices). 
    * 
    * @param index the index of the element to removed. 
    * @return the element that was removed from the list. 
    * @throws IndexOutOfBoundsException if index out of range <tt>(index 
    *  &lt; 0 || index &gt;= length)</tt>. 
    */ 
    public static <T> T[] removeArrayIndex(T[] src, int index) { 
     Object[] tmp = src.clone(); 

     int size = tmp.length; 
     if ((index < 0) && (index >= size)) { 
      throw new ArrayIndexOutOfBoundsException(index); 
     } 

     int numMoved = size - index - 1; 
     if (numMoved > 0) { 
      System.arraycopy(tmp, index + 1, tmp, index, numMoved); 
     } 
     tmp[--size] = null; // Let gc do its work 

     return (T[]) Arrays.copyOf(tmp, size - 1); 
    } 

    /** 
    * Inserts the element at the specified position in this list. 
    * Shifts any subsequent elements to the rigth (adds one to their indices). 
    * 
    * @param index the index of the element to inserted. 
    * @return the element that is inserted in the list. 
    * @throws IndexOutOfBoundsException if index out of range <tt>(index 
    *  &lt; 0 || index &gt;= length)</tt>. 
    */ 
    public static <T> T[] insertArrayIndex(T[] src, Object newData, int index) { 
     Object[] tmp = null; 
     if (src == null) { 
      tmp = new Object[index+1]; 
     } else { 
      tmp = new Object[src.length+1]; 

      int size = tmp.length; 
      if ((index < 0) && (index >= size)) { 
       throw new ArrayIndexOutOfBoundsException(index); 
      } 

      System.arraycopy(src, 0, tmp, 0, index); 
      System.arraycopy(src, index, tmp, index+1, src.length-index); 
     } 

     tmp[index] = newData; 

     return (T[]) Arrays.copyOf(tmp, tmp.length); 
    }  

Answer 4

Лучший способ иметь динамически изменение размеров «массива» или список элементов является использование ArrayList.

Java уже построила в этой структуре данных очень эффективные алгоритмы изменения размера.

Но, если вы должны изменить размер собственного массива, лучше всего использовать System.arraycopy() или Arrays.copyOf().

Arrays.copyOf() может быть проще всего использовать как так:

int[] oldArr; 
int newArr = Arrays.copyOf(oldArr, oldArr.length * 2); 

Это даст вам новый массив с теми же элементами, что и старый массив, но теперь с запасом.

Класс Arrays класс в целом имеет множество отличных методов для работы с массивами.

Также

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

Answer 5

Очевидно, что важный бит здесь не в том случае, если вы объедините массивы или скопируете их; что более важно, это стратегия роста вашего массива. Нетрудно видеть, что очень хороший способ выращивания массива всегда удваивает свой размер, когда он становится полным. Таким образом, вы увеличите стоимость добавления элемента к O (1), поскольку фактический этап роста будет происходить только относительно редко.

Answer 6

Массивы постоянного размера, так что нет возможности их выращивать.Их можно скопировать, используя System.arrayCopy, чтобы быть эффективными.

---

ArrayList делает именно то, что вам нужно. Он оптимизирован намного лучше, чем любой из нас мог бы сделать, если вы не посвятили ему значительное время. Он использует внутренне System.arrayCopy.

---

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

Answer 7

Heres эталон времени, затраченный для добавления и удаления элементов из коллекции/ArrayList/вектора

Answer 8

Действительно ли массив массивный или вы ссылаетесь на большие ссылочные типы?

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

int[] largeArrayWithSmallElements = new int[1000000000000]; 
myClass[] smallArrayWithLargeElements = new myClass[10000]; 

Edit:

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

И если приложение имеет ограниченные ресурсы памяти, вы можете попробовать поиграть с начальным размером ArrayList (одного из его конструкторов).

Для оптимальной эффективности памяти вы можете создать контейнерный класс с массивом ArrayList.

Что-то вроде:

class DynamicList 
{ 
    public long BufferSize; 
    public long CurrentIndex; 

    ArrayList al = new ArrayList(); 

    public DynamicList(long bufferSize) 
    { 
     BufferSize = bufferSize; 

     al.add(new long[BufferSize]); 
    } 

    public void add(long val) 
    { 
     long[] array; 

     int arrayIndex = (int)(CurrentIndex/BufferSize); 

     if (arrayIndex > al.size() - 1) 
     { 
      array = new long[BufferSize]; 
      al.add(array); 
     } 
     else 
     { 
      array = (long[])al.get(arrayIndex); 
     } 

     array[CurrentIndex % BufferSize] = val; 
    } 

    public void removeLast() 
    { 
     CurrentIndex--; 
    } 

    public long get(long index) 
    { 
     long[] array; 

     int arrayIndex = (int)(index/BufferSize); 

     if (arrayIndex < al.size()) 
     { 
      array = (long[])al.get(arrayIndex); 
     } 
     else 
     { 
      // throw Exception 
     } 

     return array[index % BufferSize]; 
    } 
} 

(мой Явы ржавый, поэтому, пожалуйста, медведь со мной ...)

Answer 9

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

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

Answer 10

Один из способов сделать это, имеющий связанный список узлов массива. Это несколько сложно, но предпосылка такова:

У вас есть связанный список, и каждый узел в списке ссылается на массив. Таким образом, ваш массив может расти без копирования. Чтобы расти, вам нужно только добавить дополнительные узлы в конце. Поэтому операция «дорогого» роста происходит только при каждом M-операциях, где M - размер каждого узла. Конечно, это предполагает, что вы всегда добавляете конец и не удаляете.

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

Единственная потеря с этой структурой (без учета вставки и удаления) - с помощью gets. Получатели будут немного длиннее; для доступа к правильному узлу требуется доступ к правильному узлу в связанном списке, а затем выборка. Если есть много посещений по середине, это может быть медленным, однако - трюки для ускорения связанных списков.

Answer 11

Вы искали GNU Trove для высокоэффективных коллекций java? Их коллекции хранят примитивы непосредственно для гораздо более эффективного использования памяти.

Answer 12

«Могу ли я вырастить массив без временно, имеющие все значения дважды?»

Даже если вы скопируете массивы, вы будете иметь все значения один раз. Если вы не вызываете clone() в своих значениях, они передаются по ссылке в новый массив.

Если у вас уже есть ваши значения в памяти, то только при использовании дополнительного массива памяти при копировании в новый массив выделяется новый массив Object [], который не занимает много памяти, поскольку это всего лишь список указателей для оценки объектов.