java - List 的每个子项的 add 方法和 get 方法的速度有多快

Question

我正在开发我的 java 应用程序，我很关心性能速度，特别是因为我有很多数据结构，如列表、映射等。

我知道 LinkedList 的 add(Object obj) 方法的复杂度是 O(1) (使用 LinkedList 的主要原因)，ArrayList 的 get(int index) 方法的复杂度是 O(1) (主要原因使用ArrayList)。

我在互联网上找到了以下文章:

Try to follow these rules while optimizing ArrayList performance of your code:

Add elements to the end of the list
Remove elements from the end too
Avoid contains, indexOf and remove(Object) methods
Even more avoid removeAll and retainAll methods
Use subList(int, int).clear() idiom to quickly clean a part of the list

现在我需要知道的是，将元素添加到列表末尾意味着什么，因为就我而言，如果我们不使用索引作为 add 方法的参数，换句话说，如果我们使用 add( Object obj) 方法，然后元素总是添加到末尾。

我有下面这两种方法，我想知道当我们有 1000 个文件时这些方法的性能是否令人满意。如果没有，有什么办法可以提高性能

我已经使用像 jvm 这样的分析器来测量速度性能，但我仍然不确定这是否是我可以实现的最佳性能

public List<int[][]> AllSharesForFiles (int n , int k,List<File> file) {

    sharesHolder = new LinkedList<int[][]>();
    try{    

        for(int i=0;i<file.size();i++) {

            byte[]secret = f.readingTheFile(file.get(i));  // We call the method which read the file

            //method which evaluate the shares of each byte of the file   
            shar1= s.calculateThresholdScheme(secret, n,k,new    RndGeneratorAllAlgorithm(new RandomGeneratorSHA1()),two);

            sharesHolder.add(shar1);
        }

    } catch (IOException e) {

        e.printStackTrace();

    }   

    return sharesHolder;
}

/*Look for the possibilities to return a 2D array instead of one dimensional array
 * 
 */
public List<int[][]> AllSharesForEachFile (int n , int k,List<int [] []> f) {

    sharesHolder1 = new LinkedList<int[][]>();
    int s=f.size();
    int l=f.get(1)[0].length;     

    for (int i = 0; i < n; i++) {

        someValue=new int[s][l];

        for(int j=0;j<f.size(); j++){

            someValue[j]=f.get(j)[i];

        }
        sharesHolder1.add(someValue);
    }



    return sharesHolder1;
}

Answer 1

对于绝大多数用例，

ArrayList 优于 LinkedList。看看this Q&A讨论它们的性能差异。

简而言之，ArrayList 对于 add(Object o) 的摊销复杂度为 O(1)。它们的优点还在于拥有更好的缓存局部性，因为所有项目都分配在单个内存块中，而不是分散在整个堆中，后者的成本相当高，因为它需要额外的间接寻址。

也就是说，您担心性能是件好事，但如果您需要处理的只是一个包含 1000 个项目的列表，您可能会发现两种实现之间存在一些差异。您的列表并没有那么大，而且您还将列表上的操作与 I/O 操作混合在一起，这肯定会主导应用程序的执行时间。