0

私が走るとき（それぞれ）：

package containers;

import java.util.*;

    public static void main(String[] args) {

    List<Integer> arLst = new ArrayList<Integer>();
    List<Integer> lnLst = new LinkedList<Integer>();

    long start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        arLst.add(i);
    }

    System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

    start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        lnLst.add(i);
    }

    System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}

実行時間はほぼ同じです。LinkedListの場合、時間の追加が速くなるはずです。なぜだろうか..（私が覚えているように、リスト全体を調べなければならないLinkedListとは異なり、配列はO（1）で挿入先を知っているので、中間の挿入と最後の要素の両方で意味があります）。

4

5 に答える 5

4

どちらのリストもリストの終わりがどこにあるかを知っているので、挿入時間はほぼ同じです。LinkedList は、すべての要素に対してノードを作成し、より多くのメモリを使用するため、少し遅くなると予想していました。

私は得る

TIntArrayList - 141 ms
ArrayList<Integer> - 810 ms
LinkedList<Integer> - 5190 ms.

TIntArrayList は、キャッシュをより効率的に使用して各要素のオブジェクトを作成しません。

于 2012-08-22T13:41:11.493 に答える
4

あなたのリストはどちらもArrayLists です... それらのいずれかを に変更してもLinkedList、大きな違いに気付くことはありません。ArrayListあなたのやり方で構築すると、挿入ごとに O(1) の複雑さが償却されます。

于 2012-08-22T13:41:19.020 に答える
3

あなたのコードはあなたの説明とは異なります。しかし、あなたの質問に対する答えは次のとおりです。

ArrayList 対 LinkedList

于 2012-08-22T13:43:14.787 に答える
2

うーん....多分これ：

List<Integer> lnLst = new ArrayList<>();

次のようになります。

List<Integer> lnLst = new LinkedList<>();

そして、私はあなたが何を測定しようとしているのか理解できません。パフォーマンスを測定したいadd場合、コードは次のようになります。

    public static void main(String[] args) {

        List<Integer> arLst = new ArrayList<Integer>();
        List<Integer> lnLst = new LinkedList<Integer>();

        long start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            arLst.add(i);
        }

        System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

        start = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i++) {
            lnLst.add(i);
        }

        System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
    }
于 2012-08-22T13:40:19.070 に答える
0

...配列はO(1)でどこに挿入するかを知っているので、私が思い出したように、リスト全体を通過しなければならないLinkedListとは異なります)。

これは正しくありません。配列 (ArrayList ではない) には一定の挿入時間がありません。Java の ArrayList にも技術的にはありません (追加操作は、ArrayList の償却された一定の時間で実行されます)。

さらに、リンクされたリストに要素を挿入することは次のO(1)とおりです。

List インターフェイスの実装に加えて、LinkedList クラスは、リストの先頭と末尾にある要素を取得、削除、および挿入するための統一された名前のメソッドを提供します。

ソートされたリストに挿入する場合、複雑さは になりO(N)ます。

于 2012-08-22T13:52:16.080 に答える