50000 個以上の文字列を保存したいのですが、特定の文字列の取得、特定の文字列の削除など、いくつかの操作を実行する必要があります。選択できるオプションは 2 つしかありません。これらは配列リストとそれらを保存する配列です。 . パフォーマンスの観点から、どちらが優れていますか?
7 に答える
ない。特定の文字列の取得 (例: 文字列 "Foo" の取得) と特定の文字列の削除 (例: "Foo" の削除) が必要な場合は、Set
.
配列リストまたは配列は、O(N) の取得を提供します (並べ替えを行わない限り)。ASet
は通常、特定のアイテムを見つけるのに少なくとも O(lg N) の時間を与えます。
ArrayList
配列に支えられているため、パフォーマンスに関しては違いはありません。
要件にエラーがなく、実際に arraylist と raw 配列の中から選択する必要がある場合は、raw 用に自分で作成する必要がある利用可能なデータを操作するためのすべての API があるため、arraylist をお勧めします。の配列String
。
配列は配列リストよりも効率的なパフォーマンスですが、配列に配置する要素の数がわからない場合は、配列リストのサイズが必要に応じて大きくなる可能性があるのに対し、静的配列ではできないため、配列リストの方が適しています。
配列は常にArrayList
. 部分的には、配列を使用する場合、その要素を型キャストするための追加コストを支払う必要がないためです (ジェネリックを使用しても、型キャストが消えるわけではなく、単純なビューから隠されるだけです)。
つまり、Troveとfastutilは、非常に高速な Java コレクション ライブラリの 2 つであり、タイプ固有のコレクションを提供するという事実に依存しており、オブジェクト ベースの実装のようにArrayList
は機能していません。
また、get()
要素にアクセスするためのメソッドを使用するためのコスト (わずかではありますが) と、サイズ変更操作のためのコストがかかります。これはArrayLists
、多くの挿入と削除を伴う非常に重要になる可能性があります。もちろん、これは配列では起こりません。その性質上、サイズが固定されているためです。これは利点と欠点の両方です。
質問への回答: 必要な要素の数が事前にわかっていて、それらの要素があまり変更されない場合 (挿入、削除)、最善の策は配列を使用することです。いくつかの変更操作が必要で、パフォーマンスが最も重要な場合は、Trove または fastutil を使用してみてください。
ArrayList のソース コードを見ると、次のように表示されます。
107 /**
108 * The array buffer into which the elements of the ArrayList are stored.
109 * The capacity of the ArrayList is the length of this array buffer.
110 */
111 private transient Object[] elementData;
内部で配列を使用しています。
したがって、ArrayList は、配列を使用するよりも高速になることはありません。
特定の文字列の取得、特定の文字列の削除... ArrayList は最善の解決策ではないと思います。HashSet または LinkedHashSet を見てください。
最初に ArrayList のサイズを正しく設定していれば、主な違いは、配列で取り除くことができる範囲チェックを行う追加によるものです。しかし、ここでは数 CPU サイクルについて話しています。
それ以外は、目立った違いはないはずです。たとえば、indexOf
ArrayList のメソッドは次のようになります。
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}