Javaコンテナ——ArrayList VS LinkedList(Java 8)性能比較
ArrayListとLinkedListはいずれもListから継承されており,内在的な実装メカニズムが異なり,区別についてはすでに多くの優れた文章が紹介されている.本稿では,実際の観点から,異なる操作における2つのListの性能を比較し,読者が特定のシーンで選択型を参照するのに便利である.コンピューターの配置により、JDKバージョン、IDEなどのテスト結果が出入りしたり、結論が一致しない結果が出たりするため、本稿のテスト結果は一定の参考価値しか備えていない.
データの挿入
同じように2つのリストにデータを挿入し、まず単純タイプのデータを挿入し、ここでは単純文字列を挿入する.表のデータはミリ秒単位で、1ミリ秒未満の近似は1ミリ秒です.
表1 2種類のList挿入性能比較
操作バー数
ArrayList
LinkedList
1000
6
1
10000
13
1
100000
10
19
1000000
24
45
1000000
347
939
テーブルのデータ時間単位はミリ秒です.数が少ない場合,LinkedListは絶対的な速度優位性があり,100000以上を超えるとArrayListが顕著な優位性を占めていることが明らかになった.
二Listデータの読み出し
データの検索はコンテナの重要な操作であり、通常はデータの取得と変更よりも頻繁に行われます.遍歴リストでは、両者の比較はどうでしょうか.ここでは,順序読み出しとランダム選択の2つの読み出し方式を採用する.
表2の2種類のListシーケンス遍歴性能比較
操作バー数
ArrayList
LinkedList
1000
1
2
10000
1
34
100000
2
5435
表3 2種類のListランダム遍歴性能比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
3
40
100000
6
6420
Listの順序遍歴は多重方式があり,両者は一括して押下して増分遍歴する方式で行った.ランダム読み出しの回数はリストの長さと同じであり,テスト時間にランダム数を生成する時間を加える必要がある.両者の10万件のデータの差が大きいことを考慮して、テストを続けません.
三リストデータの削除
リストの削除操作は異常が発生しやすい場所であり,日常的な操作には特に注意が必要である.ここでは、リストの既存の要素をランダムに削除します.削除された数は、リストの長さの10分の1です.
表4の2種類のList削除性能比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
2
8
100000
45
893
1000000
6261
73234
リストの削除は,挿入,照会に比べて最も時間のかかる操作であり,最も問題が発生しやすいことが分かる.
四リストデータクリア
確立があれば破棄があり,リストを破棄して上から削除する方式を採用すれば,この時間的代価は受け入れられない.システムが採用するリストをクリアする方法は簡単で迅速で、ここではシステムコードを貼らず、直接時間の対比を見ます.
表5 2種類のList破棄比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
1
1
100000
1
3
1000000
3
6
1000000
11
42
まとめ
データをテストすることで、ほとんどのシーンでArrayListはLinkedListより優れており、少量のデータ挿入時にのみLinkedListが一定の優位性を持っている.
本稿では,Listの重要な操作性能を比較し,Listインタフェースには多くの実現方法があり,興味があれば自分で実践できる.
理論は実際と結びつけ,実践から理論を総括しなければならない.テスト結果の原因は多岐にわたっており,インタフェースの実装に依存するだけでなく,パラメータタイプ,オペレーティングシステム,仮想マシンにも関係する可能性があり,後でソースコードの観点からテスト結果を解読する.
データの挿入
同じように2つのリストにデータを挿入し、まず単純タイプのデータを挿入し、ここでは単純文字列を挿入する.表のデータはミリ秒単位で、1ミリ秒未満の近似は1ミリ秒です.
/**
* add element for List
* @param sourceArray source element array
* @param list list to add element
*/
public void setEleForList(Object[] sourceArray, List list){
int len = sourceArray.length;
for (int i = 0; i < len; i++){
list.add(sourceArray[i]);
}
}
表1 2種類のList挿入性能比較
操作バー数
ArrayList
LinkedList
1000
6
1
10000
13
1
100000
10
19
1000000
24
45
1000000
347
939
テーブルのデータ時間単位はミリ秒です.数が少ない場合,LinkedListは絶対的な速度優位性があり,100000以上を超えるとArrayListが顕著な優位性を占めていることが明らかになった.
二Listデータの読み出し
データの検索はコンテナの重要な操作であり、通常はデータの取得と変更よりも頻繁に行われます.遍歴リストでは、両者の比較はどうでしょうか.ここでは,順序読み出しとランダム選択の2つの読み出し方式を採用する.
/**
* iterate through list
*
* @param list list to iterate through
*/
public void getAllEleFromList(List list){
int size = list.size();
for (int i = 0; i < size; i++){
Object object = list.get(i);
}
}
表2の2種類のListシーケンス遍歴性能比較
操作バー数
ArrayList
LinkedList
1000
1
2
10000
1
34
100000
2
5435
/**
* get random elements form list
*
* @param list list to get from
* @param num number of elements to get
*/
public void getRandomEleFromList(List list,int num){
int size = list.size();
Random random = new Random();
for (int i = 0; i < num; i++){
Object object = list.get(random.nextInt(size - 1));
}
}
表3 2種類のListランダム遍歴性能比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
3
40
100000
6
6420
Listの順序遍歴は多重方式があり,両者は一括して押下して増分遍歴する方式で行った.ランダム読み出しの回数はリストの長さと同じであり,テスト時間にランダム数を生成する時間を加える必要がある.両者の10万件のデータの差が大きいことを考慮して、テストを続けません.
三リストデータの削除
リストの削除操作は異常が発生しやすい場所であり,日常的な操作には特に注意が必要である.ここでは、リストの既存の要素をランダムに削除します.削除された数は、リストの長さの10分の1です.
/**
* remove random number elements form list
*
* @param list list to remove
* @param num number to remove
*/
public void removeEleFromList(List list, int num){
int size = list.size();
Random random = new Random();
for (int i = 0; i < num; i++){
Object object = list.remove(random.nextInt(size - 1 - i));
}
}
表4の2種類のList削除性能比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
2
8
100000
45
893
1000000
6261
73234
リストの削除は,挿入,照会に比べて最も時間のかかる操作であり,最も問題が発生しやすいことが分かる.
四リストデータクリア
確立があれば破棄があり,リストを破棄して上から削除する方式を採用すれば,この時間的代価は受け入れられない.システムが採用するリストをクリアする方法は簡単で迅速で、ここではシステムコードを貼らず、直接時間の対比を見ます.
表5 2種類のList破棄比較
操作バー数
ArrayList
LinkedList
1000
1
1
10000
1
1
100000
1
3
1000000
3
6
1000000
11
42
まとめ
データをテストすることで、ほとんどのシーンでArrayListはLinkedListより優れており、少量のデータ挿入時にのみLinkedListが一定の優位性を持っている.
本稿では,Listの重要な操作性能を比較し,Listインタフェースには多くの実現方法があり,興味があれば自分で実践できる.
理論は実際と結びつけ,実践から理論を総括しなければならない.テスト結果の原因は多岐にわたっており,インタフェースの実装に依存するだけでなく,パラメータタイプ,オペレーティングシステム,仮想マシンにも関係する可能性があり,後でソースコードの観点からテスト結果を解読する.