Большая часть памяти эффективный способ вырастить массив в Java?

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

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

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

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

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

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

Класс Arrays обычно имеет много замечательных методов работы с массивами.

Также

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

Массивы имеют постоянный размер , поэтому нет возможности их увеличивать. Вы можете только скопировать их, используя System.arrayCopy для повышения эффективности.

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

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

"Могу ли я увеличить массив без временно имея все значения дважды? "

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

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

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

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

Взгляните на System.arraycopy .

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);
    }    

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

Просматривали ли вы GNU Trove в поисках высокоэффективных коллекций Java? Их коллекции хранят примитивы напрямую для лучшего использования памяти.

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

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

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

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

Большой ли сам массив или вы ссылаетесь на большие ReferenceTypes?

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

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

Редактировать:

Если у вас есть соображения производительности при использовании 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];
    }
}

(моя java заржавела, так что терпите меня ...)

Вот эталон времени, затрачиваемого на добавление и удаление элементов из коллекции / arraylist / vector