最初のオプションはより高速である必要があります。セットを使用する前にサイズを変更することで、さらに高速化できる可能性があります。通常、少数の重複が予想される場合:
Set<String> undefined = new HashSet<String>(pairs.size(), 1);
サイズ変更を防ぐために、負荷係数に 1 を使用したことに注意してください。
好奇心からテストを実行しました(以下のコード)-結果は(コンパイル後)です:
テスト 1 (注: ウォームアップに数分かかります)
元のリストのサイズ = 3,000、重複なし:
set: 8
arraylist: 668
linkedlist: 1166
テスト 2
元のリストのサイズ = 30,000 - すべての文字列が同一:
set: 25
arraylist: 11
linkelist: 13
そのようなことは理にかなっています:
- 多くの重複がある場合
List#contains
、重複がより迅速に検出され、大きなセットを割り当てるコスト + ハッシュ アルゴリズムが不利になるため、かなり高速に実行されます。
- 重複がないか、ほとんどない場合、セットは大差で勝ちます。
public class TestPerf {
private static int NUM_RUN;
private static Random r = new Random(System.currentTimeMillis());
private static boolean random = false; //toggle to false for no duplicates in original list
public static void main(String[] args) {
List<String> list = new ArrayList<>();
for (int i = 0; i < 30_000; i++) {
list.add(getRandomString());
}
//warm up
for (int i = 0; i < 10_000; i++) {
method1(list);
method2(list);
method3(list);
}
NUM_RUN = 100;
long sum = 0;
long start = System.nanoTime();
for (int i = 0; i < NUM_RUN; i++) {
sum += method1(list);
}
long end = System.nanoTime();
System.out.println("set: " + (end - start) / 1000000);
sum = 0;
start = System.nanoTime();
for (int i = 0; i < NUM_RUN; i++) {
sum += method2(list);
}
end = System.nanoTime();
System.out.println("arraylist: " + (end - start) / 1000000);
sum = 0;
start = System.nanoTime();
for (int i = 0; i < NUM_RUN; i++) {
sum += method3(list);
}
end = System.nanoTime();
System.out.println("linkelist: " + (end - start) / 1000000);
System.out.println(sum);
}
private static int method1(final List<String> list) {
Set<String> set = new HashSet<>(list.size(), 1);
for (String s : list) {
set.add(s);
}
return set.size();
}
private static int method2(final List<String> list) {
List<String> undefined = new ArrayList<>();
for (String s : list) {
if (!undefined.contains(s)) {
undefined.add(s);
}
}
return undefined.size();
}
private static int method3(final List<String> list) {
List<String> undefined = new LinkedList<>();
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String value = it.next();
if (!undefined.contains(value)) {
undefined.add(value);
}
}
return undefined.size();
}
private static String getRandomString() {
if (!random) {
return "skdjhflkjrglajhsdkhkjqwhkdjahkshd";
}
int size = r.nextInt(100);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
char c = (char) ('a' + r.nextInt(27));
sb.append(c);
}
System.out.println(sb);
return sb.toString();
}
}