LinkedListの探索
LinkedListについて
基本的なことですが、以下の問題を解いていたときにうっかりやってしまっていた事項です、、
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_C&lang=jp
LinkedListに入っている先頭から末尾までのすべての要素を順番に標準出力したいと言うときに、 理由がわからずなぜか遅いということがありました。
後々気づいたのですが、LinkedListは双方向リストのため、番目のある要素を取得する時は
get(i)
で要素を取得すると、リストの先端または終端のうち、指定した 番目のインデックスに近い方からリストをトラバースします。 つまり要素数に応じた時間がかかります。
すべての要素を取得するのであれば、
poll()
で要素を一つずつ取得し、削除するのが正しい実装になります。
以下、 万件のLinkedListの各要素を先頭から末尾まで出力するのにかかる時間を測定しました。自明ですが、圧倒的な差があります。
import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.util.LinkedList; public class LinkedListSample { public static void main(String[] args) throws IOException { LinkedList<Integer> list = new LinkedList<>(); for (int i = 0; i < 100000; i++) { list.addFirst(i); } long start1 = System.currentTimeMillis(); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter( System.out)); StringBuffer sb = new StringBuffer(); sb.append(list.get(0)); for (int i = 1; i < list.size(); i++) { sb.append(" "); sb.append(list.get(i)); } sb.append("\n"); long end1 = System.currentTimeMillis(); System.out.println("time[get(i)]:"+(end1-start1)+"ms"); long start2 = System.currentTimeMillis(); BufferedWriter bw2 = new BufferedWriter(new OutputStreamWriter( System.out)); StringBuilder sb2 = new StringBuilder(); sb2.append(list.poll()); for (Integer s : list) { sb2.append(" "); sb2.append(s); } long end2 = System.currentTimeMillis(); System.out.println("time[poll()]:"+(end2-start2)+"ms"); bw.close(); bw2.close(); } }
time[get(i)]:3666ms time[poll()]:11ms