1

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

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

A. 为什么会这样？B. 是否可以让 Arraylists 以同样快的速度工作？（因为将 ArrayList 复制到数组本身需要很多时间）。

谢谢！

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

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

4

1 回答 1

5

A. Why does that happen?

Because ArrayList is using an array underneath. By default the size of the array is 10. When you try to add the 11th element a new bigger array has to be created and all the values from the smaller array has to be copied to the new array. In your case, since you are adding 100000 elements this happens numerous times and it is the cause of the difference in performance.

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

Yes, when creating ArrayList instances, use the constructor that allows to provide the initial capacity of the ArrayList, i.d.:

public ArrayList(int initialCapacity)

Constructs an empty list with the specified initial capacity.

Parameters: initialCapacity - the initial capacity of the list

于 2013-11-06T13:23:08.957 回答