巨大なLinkedListのトラバーサル

Question

プロジェクトでは、5百万のランダムな整数が埋め込まれたLinkedListのトラバーサルに、listIteratorを使用し、次にLinkedListのget（index）メソッドを使用するメソッドを記述する必要があります。

私はlistIteratorでトラバースしても問題はありませんでしたが、約75msで完了しました。しかし、getメソッドのトラバーサルを5百万の整数で試行した後、私はちょうど約1.5時間で実行を停止しました。

私が使用したgetTraverseメソッドは、以下のコードのようなものです（ただし、私のクラスはクラス内の他のメソッドとグループ化されていて静的ではありませんでしたが、同じ方法で動作します）。

public static long getTraverse(LinkedList<Integer> list) { 
    long start = System.currentTimeMillis(); 
    for (int i = 0; i < linkedList.size(); i++) { 
     linkedList.get(i); 
    } 
    long stop = System.currentTimeMillis(); 
    return stop - start; 
} 

は、これはサイズ50、500、5000、50000の整数のLinkedListsのために完璧にうまくいきました、とかなり時間がかかりましたが、私の教授は非常に命令とに非常に曖昧になりがち500000

のために完了します質問に近づくと役に立たない。だから、私のコードが壊れているのか、彼がガイドラインのIntegersで逃げ出したのか分かりません。すべての入力をいただければ幸いです。

Answer 1

ノードのチェーンとしてLinkedListがどのように実装されているかを考えてみましょう。特定のノードに移動するには、先頭から開始してそのノードを横断する必要があります。

あなたはそれがそのインデックスに達するまで、リストをトラバース必要とする、LinkedListのn倍に.get()を呼んでいます。これは、各要素について、リストを横断する必要があるため、getTraverse()メソッドがO（n^2）（または2次）時間を要することを意味します。

Elliott Frischは、インストラクターがあなたが発見したかったものを正確に発見していると考えています。原理的に同じものであっても、異なるアルゴリズムではランタイムが大幅に異なることがあります。

Answer 2

LinkedListは、挿入のために最適化されています。これは一定時間動作です。

LinkedListを検索するには、必要な要素を見つけるために各要素を繰り返し処理する必要があります。 getメソッドにインデックスを提供しますが、カバーの下ではそのインデックスにリストをトラバースしています。

いくつかのprintステートメントを追加すると、最初のX要素がかなり高速に取得され、時間の経過とともにリストの下位に要素をインデックスすると、速度が低下することがあります。

ArrayList（配列に裏打ちされています）は、検索のために最適化され、一定の時間内に目的の要素にインデックスを付けることができます。コードを変更してArrayListを使用して、どのくらい高速にgetが実行されるかを確認してください。