java - 数组比 ArrayLists 更有效？

Question

我最近写了一段代码，这里是它的相关部分:

int n=100000;
int[] euler=new int[n+1],arr=new int[n+1],brr=new int[n+1]; 
ArrayList[] list = new ArrayList[n+1]; //reverse euler. list[4]=5,8,10,12.
use.makeEuler(euler); 
for(int i=7; i<=n; i++)
    brr[euler[i]]++;
for(int i=7; i<=n; i++)
{
    if (list[euler[i]] == null) 
        list[euler[i]] = new ArrayList<Integer>(brr[euler[i]].length);
    list[euler[i]].add(i);
}
for(int i=n; i>=6; i--)
{
    for(int j=euler[i]+2; j<i; j+=2)
    {
        if(list[j]==null) continue;
        for(int k=list[j].size()-1; k>=0 && (int)list[j].get(k)>i ; k--)
        {
            arr[i]+=1+arr[(int) list[j].get(k)]; arr[i]%=100000000;
        }
    }
}

并注意到一些非常奇怪的事情。显然，如果我用相等数组上的函数替换 ArrayList 上的函数，代码运行得更快(从 83 秒到 27 秒)。即:

Object[] x;
for(int i=n; i>=6; i--)
{
    for(int j=euler[i]+2; j<i; j+=2)
    {
        if(list[j]==null) continue;
        x=list[j].toArray();
        for(int k=x.length-1; k>=0 && (int)x[k]>i ; k--)
        {
            arr[i]+=1+arr[(int) x[k]]; arr[i]%=100000000;
        }
    }
}

一个。为什么会这样？B. 是否有可能使 Arraylists 工作得同样快？ (因为将 ArrayList 复制到数组本身需要很多时间)。

谢谢!

编辑:有一件事我不明白。为什么在我从数组列表中添加/删除数字后它会调整大小？

Edit2:我改进了代码，现在它根本不会调整大小。这将运行时间从 83 秒减少到 59 秒，但它仍然明显大于 27 秒(当我使用数组时)。为什么会这样，我该如何进一步改进它？

Answer 1

A. Why does that happen?

因为 ArrayList 在下面使用了一个数组。默认情况下，数组的大小为 10。当您尝试添加第 11 个元素时，必须创建一个新的更大的数组，并且必须将较小数组中的所有值复制到新数组。在您的情况下，由于您要添加 100000 个元素，因此这种情况会发生很多次，这是造成性能差异的原因。

B. Is it possible to make Arraylists work equally fast? (because copying ArrayList to arrays for itself takes much time).

是的，在创建ArrayList 实例时，使用允许提供ArrayList 初始容量的构造函数, 内径:

public ArrayList(int initialCapacity)

Constructs an empty list with the specified initial capacity.

Parameters: initialCapacity - the initial capacity of the list