パフォーマンス

RandomAccessインターフェースへのJavaコレクション学習（2）ランダムアクセスとArrayListおよびLinkedListのトラバーサルパフォーマンスのリスト



List Java Collection Learning Random Access Randomaccess Interface



ArrayListクラスは、RandomAccessインターフェイスを実装します。 RandomAccessインターフェイスとSerializableインターフェイスには、ロゴのようなメソッドやフィールドはありません。

RandomAccessインターフェイスのドキュメントには次のように記載されています。リストの実装で使用されるマーカーインターフェイスは、高速（通常は一定時間）のランダムアクセスをサポートしていることを示します。 [（リスト継承テーブル名で使用されるマーカーインターフェイスは高速ランダムアクセスをサポートします）]



このインターフェイスは、Collectionsクラスで頻繁に使用され、RandomAccessインターフェイスのインスタンスであるかどうかを判断します（実際には、ポリモーフィックアプリケーションです）[list instanceof RandomAccess]インターフェイスが実装されているかどうかに応じて、さまざまな計算が選択されます。

ソースコードコメントの投稿+独自の翻訳：



/** * Marker interface used by List implementations to indicate that * they support fast (generally constant time) random access. The primary * purpose of this interface is to allow generic algorithms to alter their * behavior to provide good performance when applied to either random or * sequential access lists. * * Mark this interface to be used by List implementations to indicate that they support fast random access. The main purpose of this interface is to allow general algorithms to modify their * Behavior to provide better performance: when applied with random or sequential lists. * *

The best algorithms for manipulating random access lists (such as * ArrayList) can produce quadratic behavior when applied to * sequential access lists (such as LinkedList). Generic list * algorithms are encouraged to check whether the given list is an * instanceof this interface before applying an algorithm that would * provide poor performance if it were applied to a sequential access list, * and to alter their behavior if necessary to guarantee acceptable * performance. * * The best algorithm for manipulating lists of random access lists, such as ArrayList. When applied to sequential access lists such as LinkedList, secondary item behavior may occur * (Damn, what is the quadratic behavior! Teacher Han said that (a+b)^2 is expanded) * Before applying the algorithm, the general list algorithm encourages to check whether the list is an instance of the interface. If it is applied to the sequential access list, * Will provide poor performance, and warn them of behavior when necessary to ensure acceptable performance. * *

It is recognized that the distinction between random and sequential * access is often fuzzy. For example, some List implementations * provide asymptotically linear access times if they get huge, but constant * access times in practice. Such a List implementation * should generally implement this interface. As a rule of thumb, a * List implementation should implement this interface if, * for typical instances of the class, this loop: * 

 * for (int i=0, n=list.size() i < n i++) * list.get(i) *
* runs faster than this loop: * 
 * for (Iterator i=list.iterator() i.hasNext() ) * i.next() *
* * We realize that the difference between random access and sequential access is usually vague. For example, when the list is large, some list implementations provide * Progressive linear access time, but in practice the time is constant. Such a List should implement this interface, * As a rule of thumb, an interface should try to implement this interface, * For the implementation of this interface, use for loop pen and iterator loop faster * *

This interface is a member of the * * Java Collections Framework . * * @since 1.4 */

上記は、RandomAccessインターフェースの説明です。要約すると、ループを使用してリストをトラバースする場合、コレクションがRandomAccessのインスタンスであるかどうかを判断する必要があります。そうである場合は、forループを使用して操作し、そうでない場合は、イテレータを使用します。しかし、なぜあなたはこれをしたいのですか？データ構造の観点からです

まず、RandomAccessインターフェースを実装するArrayListのインターフェースを見てください。ほとんどの人は、ArrayListが配列であることを知っています。



次に、RandomAccessインターフェイスを実装していないLinkedListを確認します。名前が示すように、それはリンクリストです。

まず、リンクリストと配列の違いを見てください。

配列には、数字が並んでいる人がいるようです。あなたはその数に基づいて直接見つけるためのナンバーワンを見つけます。これは、添え字に基づくいわゆるクエリであるため、クエリは非常に高速ですが、挿入する場合は変更されます。非常に遅いため、挿入位置の後に他のユーザーの番号を再定義して、を削除する必要があります。同じように、効率は間違いなく遅いです。

リンクリストは、手をつないで並んでいる人のようなものです。最初のものを見つけたい場合は、1からnまで1つずつ数える必要がありますが、挿入するときに、人を直接分離して、もう一度手を握ることができます。番号を付ける必要はありません。同じものを削除してください。 。

したがって、forループを使用してトラバースする場合は、コードを投稿して次のことを確認してください。

/** * Collections test RandomAccess random access speed */ List l = new ArrayList() List _l = new LinkedList() for(int i=0i<100000i++){ l.add(String.valueOf(i)) _l.add(String.valueOf(i)) } long startTime = System.currentTimeMillis() for(int i=0i

びっくり！分析してみましょう！ ArrayListについて心配する必要はありません。すぐ下をチェックして、LinkedListが通常のforループで遅い理由を確認してください。

LinkedListのgetメソッドを見てください

Determine whether the index is in the front or the back of the whole, traverse from front to back at the front, and traverse from back to front at the back, traversing from the beginning every time, can it be slow, the algorithm complexity is n^2 Bar Node node(int index) { // assert isElementIndex(index) if (index > 1)) { Node x = first for (int i = 0 i index i--) x = x.prev return x } } 
|_+_|

次に、LinkedListのIteratorメソッドを見てください。なぜそんなに速いのですか？実装クラスを確認します。

詳細については、Javaコレクション学習のリストを参照してください（3）LinkedListを例として取り上げ、デバッグして、イテレータの実装を確認します。

イテレータを返し、次のノードがあるかどうかを判断します。ある場合は、ループを増やすことなく、現在のノードの次のノードを取得します。だから速度は間違いなく速いです。

-------------------------------------------------- -------------------------------------------------- -

前の私の質問は、このLinkedListのノードノードがどのように割り当てられるかです。今日、私はソースコードを詳しく調べて、それを見たときにそれをめちゃくちゃにしました。犯されたらノードにコピーされました!!必ず全部読んでください...またはデータ構造に慣れていない