4

私は LinkedList と ArrayList を扱っていて、要素を ArrayList と LinkedList に追加する概念を知っていますが、挿入時間をチェックするコードを実行すると、LinkedList と ArrayList の両方で挿入時間が何度も異なります。

LinkedList の挿入時間が改善される場合もあれば、その逆の場合もあります。正確にどのように行われているのか、誰か教えてください。

import java.util.ArrayList;

public class Time
   {

   public static void main(String args[])

    {

       int n=100000;
       long milis = System.currentTimeMillis();
       ArrayList obj=new ArrayList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert arraylist takes "
            +(System.currentTimeMillis()-milis)+" ms");
}

  }

このプログラムの出力は

1) arraylist の挿入には 13 ミリ秒かかります 2) arraylist の挿入には 9 ミリ秒かかります

2番目のコードは

 import java.util.LinkedList;

  public class Time1 
  {

        public static void main(String args[])
{
      int n=100000;
      long milis = System.currentTimeMillis();
      LinkedList obj=new LinkedList();

    for(int k=0;k<=n;k++)
    {
        obj.add(k);



    }
    System.out.println("insert linklist takes "
           +(System.currentTimeMillis()-milis)+" ms");
}

 }

これの出力

1) リンクリストの挿入には 8 ミリ秒かかります

2) リンクリストの挿入には 17 ミリ秒かかります

4

3 に答える 3

1

一般的に言えば、リンクされたリストは、リストの末尾以外の要素を追加および削除する場合により効率的ですが、リスト内の任意のインデックスを検索する場合ははるかに遅くなります。任意の場所で要素を追加または削除するにLinkedListは、いくつかの参照を変更するだけで済みますが、ArrayListそのポイント以降のすべてを変更する必要があります。任意のインデックスを検索するという点では、ArrayListはメモリ内のその場所にジャンプするだけで、LinkedList各アイテムをそのポイントまでトラバースする必要があります。

それは些細な例です。上記が表示されない主な理由は 2 つあります。

  • 第一に、マイクロベンチマークは最高の状態ではうまく機能しませんが、特に Java のような言語では、「ウォームアップ」してプロセスのパフォーマンスを変更する JIT が存在します。実際のシナリオでベンチマークするか、実際のパフォーマンス メトリックに別れを告げることができます。

  • 第二に、ArrayList何年にもわたって多くの最適化を見てきましたが、古典的LinkedListに勝つことが期待されていた特定のケースでより高速に実行されることにさえ気づきました.

ArrayList個人的には、マイクロ ベンチマークではなく、実際に使用しているアプリケーションに固執し、パフォーマンスを測定します。パフォーマンスが許容できない場合は、実装をLinkedList(1 行の変更である必要があります) に切り替えてから、再度ベンチマークを実行して確認します。これらのチェックがなければ、シナリオで何がより良いパフォーマンスを発揮するかを言うことはほとんど不可能です.

于 2013-05-31T12:08:37.213 に答える
0

ホットスポットが for ループ全体を最適化するのを避けるために、何らかの方法で obj を使用する必要があります。

于 2013-05-31T14:28:02.977 に答える