私は、コレクションやコレクションのコレクションなどを検索するさまざまな方法をいじくり回してきました。私の理解を確認するために、愚かな小さなテストをたくさん行っています。これが私を困惑させるものです（ソースコードはさらに下にあります）。
つまり、N個のランダムな整数を生成し、それらをリストに追加しています。リストはソートされていません。次に、を使用Collections.contains()してリスト内の値を検索します。リストスペース全体がプローブされるようにしたいので、意図的にそこにないことがわかっている値を探します。私はこの検索の時間を計ります。
次に、別の線形検索を手動で実行し、リストの各要素を繰り返し処理して、ターゲットと一致するかどうかを確認します。私もこの検索の時間を計ります。
平均して、2回目の検索は最初の検索より33％長くかかります。私の論理では、リストはソートされていないため、最初の検索も線形である必要があります。私が考えることができる唯一の可能性（私はすぐに破棄します）は、Javaが検索のためだけにリストのソートされたコピーを作成しているということですが、（1）メモリスペースの使用を許可していませんでした。このような大きなNを使用すると、大幅な時間の節約になります。
したがって、両方の検索が線形である場合、両方とも同じ時間がかかるはずです。どういうわけか、Collectionsクラスはこの検索を最適化しましたが、その方法がわかりません。だから...私は何が欠けていますか？
import java.util.*;
public class ListSearch {
public static void main(String[] args) {
int N = 10000000; // number of ints to add to the list
int high = 100; // upper limit for random int generation
List<Integer> ints;
int target = -1; // target will not be found, forces search of entire list space
long start;
long end;
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 1)... ");
if (ints.contains(target)) {
// nothing
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
System.out.println();
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 2)... ");
for (Integer i : ints) {
// nothing
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
}
}
編集：以下はこのコードの新しいバージョンです。興味深いのは、手動の線形ループがメソッドよりも16％高速に実行されるcontainsことです（注：どちらも意図的にリストスペース全体を検索するように設計されているため、反復回数が等しいことがわかります）。私はこの16％の利益を説明することはできません...もっと混乱します。
import java.util.*;
public class ListSearch {
public static void main(String[] args) {
int N = 10000000; // number of ints to add to the list
int high = 100; // upper limit for random int generation
List<Integer> ints;
int target = -1; // target will not be found, forces search of entire list space
long start;
long end;
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 1)... ");
if (ints.contains(target)) {
System.out.println("hit");
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
System.out.println();
ints = new ArrayList<Integer>();
start = System.currentTimeMillis();
System.out.print("Generating new list... ");
for (int i = 0; i < N; i++) {
ints.add(((int) (Math.random() * high)) + 1);
}
end = System.currentTimeMillis();
System.out.println("took " + (end-start) + "ms.");
start = System.currentTimeMillis();
System.out.print("Searching list for target (method 2)... ");
for (int i = 0; i < N; i++) {
if (ints.get(i) == target) {
System.out.println("hit");
}
}
end = System.currentTimeMillis();
System.out.println(" Took " + (end-start) + "ms.");
}
}