阵列比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复制到数组本身需要很长时间).

谢谢!

编辑:有一件事我不明白.为什么在我添加/删除Arraylists中的数字后它会重新调整大小？

Edit2:我改进了代码,所以现在它根本没有调整大小.这样可以将运行时间从83秒减少到59秒,但仍然远远大于27秒(当我使用阵列时).为什么这样,我如何进一步改善它？

Answer 1

答:为什么会这样？

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

B.是否有可能使Arraylists同样快速地工作？(因为将ArrayList复制到数组本身需要很长时间).

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

public ArrayList(int initialCapacity)

构造具有指定初始容量的空列表.

参数:initialCapacity - 列表的初始容量