在Java中最有效的增长数组的方法?

有更有效的增长方式吗 比创建新数组大的数组 复制所有的值?像, 将它与新的连接起来?

不,而且可能没有任何语言可以保证在不进行复制的情况下始终增长数组。一旦为数组分配空间并执行其他操作,很可能在数组结束后内存中就有其他对象。在这一点上,不复制阵列就根本不可能增长阵列。

有固定大小的数组怎么样 存储在另一个数组中并重新分配 /复制顶层的那个?会吗 是否保留实际值?

你的意思是有一个数组,并把它当作一个由底层数组的串联组成的大数组?是的,这是可行的(如“间接做”的方法),就像在Java中一样。 Object[][] 只是指向 Object[] 实例。

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

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

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

CopyOffice() 最简单的用法如下:

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

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

这个 Arrays 类通常有许多处理数组的好方法。

阿尔索

重要的是要确保每次添加一个元素时不只是将数组增长一个元素。最好实施一些策略,在这种策略中,您只需要每隔一段时间调整数组的大小。 调整数组大小是一项昂贵的操作。

数组的大小是常量 所以没有办法种植它们。您只能复制它们,使用 系统.arraycopy 提高效率。

数组列表 做你所需要的。它的优化比我们任何人都要好得多,除非你花了相当长的时间。它使用内部System.ArrayCopy。

更重要的是,如果你有 巨相 在需要列表增长/减少的地方,以及其他不增长/减少的地方,您可以在其中进行数千次读或写。另外,假设您有一个巨大的性能需求,那就是您在读/写时希望arraylist太慢。您仍然可以将arraylist用于一个巨大的阶段,并将其转换为另一个阶段的数组。注意,只有当您的应用程序阶段很大时,这才是有效的。

一个链接列表加上一个只包含引用的数组怎么样?

链接列表可以在不需要分配新内存的情况下增长,数组将确保您可以轻松访问。每次数组变小时,您可以简单地将整个数组丢弃,然后从链接列表中重新构建它。

“我可以在没有 暂时拥有所有值 两次?”

即使你复制数组,你也只能得到所有的值一次。除非对值调用clone(),否则它们将通过引用传递到新数组中。

如果您的值已经存在于内存中,那么复制到新数组时唯一额外的内存开销就是分配新的对象[]数组,它根本不占用太多内存,因为它只是指向值对象的指针列表。

看一看 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),因为实际的增长阶段将很少发生。

实现这一点的一种方法是拥有数组节点的链接列表。这有点复杂,但前提是:

您有一个链接列表,列表中的每个节点都引用一个数组。这样,您的阵列就可以在不复制的情况下增长。为了增长,您只需要在末尾添加额外的节点。因此,“昂贵的”增长操作只发生在每m个操作中,其中m是每个节点的大小。当然,这假定您总是追加到末尾,并且不删除。

在这个结构中插入和删除是相当复杂的,但是如果您可以避免它们,那么这是完美的。

这种结构(忽略插入和删除)的唯一损失是使用GET。GET将稍长一点;访问正确的节点需要访问链接列表中的正确节点,然后在那里获取。如果中间有很多通道,那么速度会很慢。 是 加速链接列表的技巧。

你看过吗 GNU Trove 对于高效的Java集合?他们的集合直接存储主要活动,以便更好地使用内存。

数组本身是大的还是引用大的引用类型?

一个包含数十亿个元素的基元类型数组和一个包含数千个元素的数组之间存在差异,但它们指的是大型类实例。

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生锈了,所以请你容忍我……)

Heres 从集合/arraylist/vector添加和删除元素所用的时间基准