在 Java 中增长数组的最有效内存方式？

Most memory efficient way to grow an array in Java?

提问by Hanno Fietz

I'm not too concerned about time efficiency (the operation will be rare), but rather about memory efficiency: Can I grow the array without temporarily having all the values twice?

我不太关心时间效率（该操作很少见），而是关心内存效率：我可以在不临时拥有两次所有值的情况下增长数组吗？

Is there a more efficient way to grow a large array than creating a new one and copying over all the values? Like, concatenating it with a new one?

有没有比创建一个新数组并复制所有值更有效的方法来增加一个大数组？比如，把它和一个新的连接起来？

What about having fixed-size arrays stored in another array and reallocate / copy that top-level one? Would that leave the actual values in place?

将固定大小的数组存储在另一个数组中并重新分配/复制该顶级数组怎么样？这会保留实际值吗？

I'm aware of ArrayList, but I need a lot of control about accessing the array and the access needs to be very fast. For instance, I think I prefer a[i]to al.get(i).

我知道 ArrayList，但我需要对访问数组进行大量控制，并且访问速度需要非常快。举例来说，我想我更喜欢a[i]到al.get(i)。

The main reason why I care about this is that the array in question (or a number of such arrays) might very well occupy a large enough portion of main memory that the usual strategy of creating a double sized copy before discarding the original might not work out. This may mean that I need to reconsider the overall strategy (or up my hardware recommendations).

我关心这个的主要原因是有问题的数组（或许多这样的数组）很可能占据了足够大的主内存部分，以至于在丢弃原始文件之前创建双倍大小副本的通常策略可能不起作用出去。这可能意味着我需要重新考虑整体策略（或提高我的硬件建议）。

采纳答案by Michael Borgwardt

Is there a more efficient way to grow a large array than creating a new one and copying over all the values? Like, concatenating it with a new one?

有没有比创建一个新数组并复制所有值更有效的方法来增加一个大数组？比如，把它和一个新的连接起来？

No. And probably there is no language, that guarantees growing an array will always take place without copying. Once you allocate the space for the array and do something else, you most likely have other objects in memory right after the end of the array. At that point, it's fundamentally impossible to grow the array without copying it.

不。而且可能没有语言可以保证数组的增长总是在不复制的情况下发生。一旦你为数组分配了空间并做其他事情，你很可能在数组结束之后在内存中还有其他对象。在这一点上，从根本上不可能在不复制数组的情况下扩展数组。

What about having fixed-size arrays stored in another array and reallocate / copy that top-level one? Would that leave the actual values in place?

将固定大小的数组存储在另一个数组中并重新分配/复制该顶级数组怎么样？这会保留实际值吗？

You mean have an array of arrays and treat it as one large array consisting of a concatenation of the underlying arrays? Yes, that would work (the "faking it by doing indirection" approach), as in Java, Object[][]is simply an array of pointers to Object[]instances.

您的意思是有一个数组数组并将其视为一个由底层数组串联组成的大数组？是的，这会起作用（“通过间接方式伪造”方法），就像在 Java 中一样，Object[][]只是一个指向Object[]实例的指针数组。

回答by kgiannakakis

Have a look at System.arraycopy.

看看System.arraycopy。

回答by Carlos Tasada

AFAIK the only way of growing or reducing an array is doing a 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);
    }    

回答by jjnguy

The best way to have a dynamically resizing 'array' or list of items is to use an ArrayList.

动态调整“数组”或项目列表大小的最佳方法是使用ArrayList.

Java has already built in very efficient resizing algorithms into that data structure.

Java 已经在该数据结构中内置了非常有效的调整大小算法。

But, if you must resize your own array, it is best to use System.arraycopy()or Arrays.copyOf().

但是，如果您必须调整自己的数组大小，最好使用System.arraycopy()or Arrays.copyOf()。

Arrays.copyOf()can most simply be used like so:

Arrays.copyOf()最简单地可以像这样使用：

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

This will give you a new array with the same elements as the old array, but now with room to spare.

这将为您提供一个与旧数组具有相同元素的新数组，但现在有剩余空间。

The Arraysclass in general has lots of great methods for dealing with arrays.

在Arrays一般类有许多用于处理数组伟大的方法。

Also

还

It is important to make sure that you aren't just growing your array by one element each time an element is added. It is best to implement some strategy where you only have to resize the array every once in a while. Resizing arrays is a costly operation.

重要的是要确保每次添加一个元素时，您的数组不只是增加一个元素。最好实施一些策略，您只需每隔一段时间调整一次数组的大小。 调整数组大小是一项代价高昂的操作。

回答by Tamas Czinege

Obviously, the important bit here is not if you concatenate the arrays or copy them over; what's more important is your array growing strategy. It's not hard to see that a very good way to grow an array is always doubling its size when it becomes full. This way, you will turn the cost of adding an element to O(1) as the actual growing stage will happen only relatively rarely.

显然，这里的重要一点不是连接数组或复制它们；更重要的是您的阵列增长策略。不难看出，增长数组的一个很好的方法是在它变满时总是将其大小加倍。通过这种方式，您将添加元素的成本变为 O(1)，因为实际的增长阶段只会相对很少发生。

回答by KLE

Arrays are constant-size, so there is no way to grow them. You can only copy them, using System.arrayCopyto be efficient.

数组是固定大小的，所以没有办法增加它们。您只能复制它们，使用System.arrayCopy是高效的。

---

---

ArrayListdoes exactly what you need. It's optimized much better than any of us could do, unless you devote a considerable time to it. It uses internally System.arrayCopy.

ArrayList正是您所需要的。它的优化比我们任何人做的都要好得多，除非您为此投入大量时间。它在内部使用 System.arrayCopy。

---

---

Even more, if you have some huge phaseswhere you need the list to grow/reduce, and others where it doesn't grow/reduce and you make thousands of read or write in it. Suppose also you have a huge performance need, that you prooved that ArrayList is too slow when read/writing. You could still use the ArrayList for one huge phase, and convert it to an array for the other. Note this would be effective only if your application phases are huge.

更重要的是，如果您有一些需要列表增长/减少的巨大阶段，以及其他不增长/减少并且您在其中进行数千次读取或写入的阶段。假设你也有巨大的性能需求，你证明 ArrayList 在读/写时太慢了。您仍然可以将 ArrayList 用于一个巨大的阶段，并将其转换为另一个的数组。请注意，这仅在您的应用程序阶段很大时才有效。

回答by Narayan

Heresa benchmark of time taken to add and remove elements from a collection/arraylist/vector

下面有所花费的时间基准，以添加和从一个集合/数组列表/载体删除元素

回答by Yannick Motton

Is the array itself large, or are you referencing large ReferenceTypes?

数组本身是否很大，或者您是否引用了大型 ReferenceType？

There is a difference between an array of a PrimitiveType with billions of elements, and an array with thousands of elements, but they refer to large class instances.

具有数十亿个元素的 PrimitiveType 数组与具有数千个元素的数组之间存在差异，但它们指的是大型类实例。

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

Edit:

编辑：

If you have performance considerations using ArrayList, I can assure you it will perform more or less exactly as Array indexing.

如果您有使用 ArrayList 的性能考虑，我可以向您保证，它的性能或多或少与 Array 索引完全相同。

And if the application has limited memory resources, you can try to play around with the initial size of the ArrayList (one of it's constructors).

如果应用程序的内存资源有限，您可以尝试使用 ArrayList（它的构造函数之一）的初始大小。

For optimal memory efficiency, you could create a container class with an ArrayList of Arrays.

为了获得最佳内存效率，您可以创建一个包含数组的 ArrayList 的容器类。

Something like:

就像是：

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

(my java is rusty, so please bear with me...)

（我的 java 生锈了，所以请多多包涵……）

回答by NomeN

How about a linked list coupled with an array that holds only references.

一个链表加上一个只保存引用的数组怎么样。

The linked list can grow without having to allocate new memory, the array would ensure you have easy access. And every time the array becomes to small, you can simply trash the entire array and build it up again from the linked list.

链表可以增长而无需分配新内存，数组将确保您可以轻松访问。每次数组变小时，您可以简单地将整个数组丢弃并从链表中重新构建它。

回答by Malaxeur

One way of doing this is having a linked list of array nodes. This is somewhat complex but the premise is this:

一种方法是使用数组节点的链表。这有点复杂，但前提是：

You have a linked list and each node within the list references an array. This way, your array can grow without ever copying. To grow you only need to add additional nodes at the end. Therefore the 'expensive' grow operation only occurs every M operations where M is the size of each node. Granted, this assumes that you always append to the end and you don't remove.

您有一个链表，列表中的每个节点都引用一个数组。这样，您的数组就可以增长而无需复制。要增长，您只需要在最后添加额外的节点。因此，“昂贵的”增长操作仅在每 M 次操作时发生，其中 M 是每个节点的大小。当然，这假设您始终附加到末尾并且不删除。

Insertion and removal in this structure is quite complicated, but if you can avoid them then that's perfect.

这种结构中的插入和移除非常复杂，但如果你能避免它们，那就完美了。

The only loss with this structure (ignoring insertion and deletion) is with the gets. The gets will be slightly longer; accessing the correct node requires accessing the correct node within the linked list and then fetching there. If there are a lot of accesses around the middle, this can be slow however there aretricks to speeding linked lists up.

这种结构的唯一损失（忽略插入和删除）是获取。get 会稍微长一些；访问正确的节点需要访问链表中的正确节点，然后在那里获取。如果中间有很多访问，这可能会很慢，但是有一些技巧可以加快链表的速度。