序文
この記事を通して、リストの5つのトラバーサル方法、それぞれのパフォーマンス、およびforeachとイテレーターの実装を理解し、ArrayListとLinkedListの実装の理解を深めることができます。以下を見てみましょう。
1.リストを通過する5つの方法
1。各ループに対して
List <Integer> list = new ArrayList <Integer>（）;
2。コールコレクションのイテレーターを表示します
List <Integer> list = new ArrayList <Integer>（）; for（iterator <integer> iterator = list.iterator（）; iterator.hasnext（）;）{iterator.next（）;}または
list <integer> list = new arraylist <integer>（）; iterator <integer> iterator = list.iterator（）; while（iterator.hasnext（））{iterator.next（）;}3。添え字の増分ループ、終端条件は、サイズ（）関数が呼び出されるたびに比較および判断することです
List <Integer> list = new ArrayList <Integer>（）; for（int j = 0; j <list.size（）; j ++）{list.get（j）;}4。終端条件がsize（）に等しい合計である一時的変数のサブスクリプトの増分サイクル、比較、および判断
list <integer> list = new arraylist <integer>（）; int size = list.size（）; for（int j = 0; j <size; j ++）{list.get（j）;}5。サブスクリプトの減少サイクル
list <integer> list = new ArrayList <Integer>（）;
リストの5つのトラバーサル方法のパフォーマンステストと比較
以下はパフォーマンステストコードで、さまざまな桁のアレイリストとLinkedListのさまざまなトラバーサル方法に費やされる時間を出力します。
パッケージcn.trinea.java.test; import java.text.decimalformat; import java.util.arraylist; import java.util.calendar; Import java.util.iterator; Import java.util.linkedlist; import Java.util.list; 2013-10-28 */public class javalooptest {public static void main（string [] args）{system.out.print（ "Arraylistのループパフォーマンスを比較する"）; looplistcompare（getArrayLists（10000、100000、100000、9000000））; System.out.print（ "/r/n/r/ncompare loop performance of linkedlist"）; looplistcompare（getLinkedLists（100、1000、10000、10000））; } public static list <integer> [] getArrayLists（int ... sizearray）{list <integer> [] listArray = new ArrayList [sizearray.length]; for（int i = 0; i <listArray.length; i ++）{int size = sizearray [i]; List <Integer> list = new ArrayList <Integer>（）; for（int j = 0; j <size; j ++）{list.add（j）; } listArray [i] = list; } return listArray; } public static list <integer> [] getLinkedLists（int ... sizearray）{list <integer> [] listArray = new linkedlist [sizearray.length]; for（int i = 0; i <listArray.length; i ++）{int size = sizearray [i]; List <Integer> list = new LinkedList <Integer>（）; for（int j = 0; j <size; j ++）{list.add（j）; } listArray [i] = list; } return listArray; } public static void looplistcompare（list <integer> ... listArray）{printheader（listArray）;長い早い時期、終了時間。 //（int i = 0; i <listArray.length; i ++）{list <integer> list = listArray [i]; starttime = calendar.getInstance（）。getTimeInmillis（）; for（integer j：list）{// use j} endtime = calendar.getInstance（）。getTimeInmillis（）; printCostTime（i、listArray.length、 "for for for"、endtime -starttime）; } // type 2 for（int i = 0; i <listArray.length; i ++）{list <integer> list = listArray [i]; starttime = calendar.getInstance（）。getTimeInmillis（）; // iterator <integer> iterator = list.iterator（）; // while（iterator.hasnext（））{// iterator.next（）; //} for（iterator <integer> iterator = list.iterator（）; iterator.hasnext（）;）{iterator.next（）; } endtime = calendar.getInstance（）。getTimeInmillis（）; printCostTime（i、listArray.length、 "for iterator"、endtime -starttime）; } // type 3 for（int i = 0; i <listArray.length; i ++）{list <integer> list = listArray [i]; starttime = calendar.getInstance（）。getTimeInmillis（）; for（int j = 0; j <list.size（）; j ++）{list.get（j）; } endtime = calendar.getInstance（）。getTimeInmillis（）; printCostTime（i、listArray.length、 "for list.size（）"、endtime -starttime）; } //（int i = 0; i <listArray.length; i ++）{list <integer> list = listArray [i]; starttime = calendar.getInstance（）。getTimeInmillis（）; int size = list.size（）; for（int j = 0; j <size; j ++）{list.get（j）; } endtime = calendar.getInstance（）。getTimeInmillis（）; printCostTime（i、listArray.length、 "for size = list.size（）"、endtime -starttime）; } //タイプ5 for（int i = 0; i <listArray.length; i ++）{list <integer> list = listArray [i]; starttime = calendar.getInstance（）。getTimeInmillis（）; for（int j = list.size（） - 1; j> = 0; j-）{list.get（j）; } endtime = calendar.getInstance（）。getTimeInmillis（）; printCostTime（i、listArray.length、 "for j-"、endtime-starttime）; }} static int first_column_length = 23、other_column_length = 12、total_column_length = 71; static final decimalformat comma_format = new decimalformat（ "＃、###"）; public static void printheader（list <integer> ... listArray）{printrowdivider（）; for（int i = 0; i <listArray.length; i ++）{if（i == 0）{stringbuilder sb = new StringBuilder（）。 while（sb.length（）<first_column_length）{sb.append（ "）;} system.out.print（sb）;} stringbuilder sb = new stringbuilder（）。 sb.append（ "）; （sb.length（）<total_column_length）{sb.append（ " - "）; first_column_length）{sb.append（ ""）; system.out.print（sb）; }}} PS：実行がin thread “main” java.lang.OutOfMemoryError: Java heap space例外をレポートする場合、 main関数のlist sizeのサイズを小さくしてください。
getArrayLists関数は、さまざまなsizeのアレイリストを返し、 getLinkedLists関数は異なるsizeのLinkedListを返します。
loopListCompare関数は、上記のトラバーサル法1-5を使用して、各リスト配列（異なるサイズのリストを含む）のリストをトラバースします。
printから始まる関数は、出力ヘルパー機能です。
テスト環境はWindows 7 32ビットシステム3.2GデュアルコアCPU 4Gメモリ、Java 7、Eclipse -XMS512M -XMX512Mです
最終的なテスト結果は次のとおりです。
ArrayListのループパフォーマンスを比較します----------------------------------------------------------------------------------------------------------------------- 10,000 | 100,000 | 1,000,000 | 10,000,000 -------------------------------------------------------------------それぞれ| 1 ms | 3 ms | 14 ms | 152 MS ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 ms | 1 ms | 12 ms | 114 ms -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 1 ms | 1 ms | 13 ms | 128 MS ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------） 0 ms | 0 ms | 6 ms | 62 ms ------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 ms | 1 ms | 6 ms | 63 ms ----------------------------------------------------------------------- compare loop performance of LinkedList-----------------------------------------------------------------------list size | 100 | 1,000 | 10,000 | 100,000 --------------------------------------------------------------------それぞれ| 0 ms | 1 ms | 1 ms | 2 ms -------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 ms | 0 ms | 0 ms | 2 ms ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 ms | 1 ms | 73 ms | 7972 MS ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0 ms | 0 ms | 67ミリ秒| 8216 MS -------------------------------------------------------------------------------------------- | 0 ms | 1 ms | 67ミリ秒| 8277 ms ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最初のテーブルは、ArrayListの比較結果であり、2番目のテーブルはLinkedListの比較結果です。
テーブルの水平方向は、同じトラバーサル法のさまざまなサイズのリストのトラバーサルの時間消費であり、垂直方向は、同じリストの異なるトラバーサル方法のトラバーサルの時間消費です。
PS：リストの最初のトラバーサルにはもう少し時間がかかるため、 for eachの結果はわずかに逸脱しています。テストコードでいくつかのタイプを交換すると、 for each for iteratorのそれに近いことがわかります。
横方向の方法のパフォーマンステスト結果の分析
1
Foreachは、Java SE5.0によって導入された非常に強力なループ構造です。 for (Integer j : list) for each int in list読み取る必要があります。
for (Integer j : list)実装はほぼ同等です
iterator <integer> iterator = list.iterator（）; while（iterator.hasnext（））{integer j = iterator.next（）;}Foreachコードは簡単に書くことができ、初期値、終了値、および国境を気にする必要はないため、間違いを犯すのは簡単ではありません。
2。アレイリストトラバーサル法の結果の分析
a。アレイリストのサイズが100,000になる前に、5つのトラバーサル方法の時間消費量はほぼ同じでした
b。 100,000以降、4番目と5番目のトラバーサル方法は最初の3つよりも高速です。GETメソッドはIteratorメソッドよりも優れています。
int size = list.size（）; for（int j = 0; j <size; j ++）{list.get（j）;} list.size()一時変数のサイズに置き換えると、パフォーマンスが向上します。 Iteratorの実装を見て、ArrayListでメソッドgetましょう
プライベートクラスITRはIterator <e> {int cursor; // int lastret = -1を返す次の要素のインデックス; //最後の要素のインデックスが返されました。 -1そのようなint expectModCount = modCountがない場合; public boolean hasnext（）{return cursor！= size; } @suppresswarnings（ "unchecked"）public e next（）{checkforcomodification（）; int i = cursor; if（i> = size）new nosuchelementexception（）; object [] elementData = arrayList.this.ElementData; if（i> = elementData.length）を新しいconcurrentModificationException（）; cursor = i + 1; return（e）elementData [lastret = i]; }…} public e get（int index）{rangecheck（index）; return elementdata（index）;}これから、 getとIteratorのnext機能は、データを直接配置することで要素も取得することがわかりますが、さらに判断はあまりありません。
c。上記から、数千万人のアレイリストでさえ、いくつかのトラバーサル方法の違いは約50msであり、時間は約100,000に等しいことがわかります。 foreachの利点を考慮すると、トラバーサルのためにforeach foreachの単純な方法を使用することを選択できます。
3。LinkedListトラバーサル法の結果の分析
a。 LinkedListのサイズが10,000に近い場合、 getメソッドとIterator方法はすでに約2桁異なります。 100,000の場合、 IteratorメソッドのパフォーマンスはGETメソッドよりもはるかに優れています。
Iteratorsの実装を見て、LinkedListでメソッドgetましょう
プライベートクラスのLISTITRはListIterator <e> {private node <e> lastreturned = null;プライベートノード<e> next; private int nextindex; private int hecdestmodcount = modcount; listitr（int index）{// assert ispositionindex（index）; next =（index == size）？ null：node（index）; nextindex = index; } public boolean hasnext（）{return nextindex <size; } public e next（）{checkforcomodification（）; if（！hasnext（））は新しいnosuchelementexception（）をスローします。 Lastreturned = next; next = next.next; nextindex ++; latreturned.itemを返します。 }…} public e get（int index）{checkelementIndex（index）; return node（index）.item;} /***指定された要素インデックスで（非ヌル）ノードを返します。 */node <e> node（int index）{// assert iselementindex（index）; if（index <（size >> 1））{node <e> x = first; for（int i = 0; i <index; i ++）x = x.next; xを返します。 } else {node <e> x = last; for（int i = size -1; i> index; i-）x = x.prev; xを返します。 }}上記のコードから、LinkedList Iteratorのnext関数が次のポインターを通じて次の要素をすぐに取得して戻ることがわかります。 GETメソッドは、最初からインデックスサブスクリプトまで通過し、O（n）の時間複雑さを持つ要素を見つけ、トラバーサルの時間の複雑さはO（n2）に達します。
したがって、 get使用を避けるために、LinkedListのトラバーサルにForeachを使用することをお勧めします。
4。アレイリストの結果の比較分析とLinkedListトラバーサル方法
上記の大きさから、それはまた、foreachループトラバーサルであり、ArrayListとLinkedListの時間は似ています。この例をわずかに変更してlist size 2つが基本的に同じ桁になっていることがわかります。
ただし、 ArrayList get関数の時間の複雑さはO（1）であり、LinkedList Get関数の時間の複雑さはO（n）です。
スペース消費を検討する場合は、最初にArrayListを選択することをお勧めします。個別の挿入と削除には、LinkedListを使用できます。
結論の概要
上記の分析により、基本的に要約できます。
要約します
上記は、この記事のコンテンツ全体です。この記事の内容が、Javaを学んだり使用したりするときに、誰にとっても役立つことを願っています。ご質問がある場合は、メッセージを残してコミュニケーションをとることができます。