サイズ変化に強いList、Map、Set
前にこんなのを書いた。
- http://d.hatena.ne.jp/hhelibex/20091027/1256641969
- java.util.HashMap のインスタンスを使いまわしてはいけない - HHeLiBeXの日記 正道編
で、ついでなので、仮に使いまわすとして、格納されるデータ数(つまりList、Set、Mapのサイズ)が大きく増減する場合に有利な実装はどれかということを計測してみる。
まず最初に。ここで示すのは、大量のオブジェクトを格納、すべて削除、という処理を繰り返した場合、「削除した後の時点でいかにヒープメモリ使用量が少ないかという観点のみに着目」した結果であり、パフォーマンスやそれぞれの実装を用いるメリット/デメリットは一切考慮していないことに注意。
実装としては、次のものを対象とする。
Listに関しては単純に同じオブジェクトを多数格納すればよいが、SetとMapに関しては、異なるオブジェクトを格納する必要があるため、それらのオブジェクトはあらかじめ生成しておく。これによって、単純に各List、Set、Mapが使用するヒープメモリサイズに近い値を割り出せるようにする。
検証コードは以下のような感じ。
import java.util.ArrayList; import java.util.Date; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashMap; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.RandomAccess; import java.util.Set; import java.util.TreeMap; import java.util.TreeSet; public class Main { // List、Set、Mapに格納する基本オブジェクト数の何倍まで格納数を増やすか private static int N = 8; // Set、Mapに格納するためのオブジェクトのキャッシュ private static Integer[] integers = new Integer[N * 1000000]; static { for (int i = 0; i < integers.length; ++i) { integers[i] = new Integer(i); } } /** * @param args */ public static void main(String[] args) { System.out.println("java.version = " + System.getProperty("java.version")); System.out.println("java.vendor = " + System.getProperty("java.vendor")); System.out.println("os.name = " + System.getProperty("os.name")); list(); map(); set(); } /** * メモリ使用量の変化計測 - List版 */ public static void list() { dump("initial", -1, null, ArrayList.class); list(new ArrayList<String>(1024)); dump("initial", -1, null, LinkedList.class); list(new LinkedList<String>()); } /** * メモリ使用量の変化計測 - Set版 */ public static void set() { dump("initial", -1, null, HashSet.class); set(new HashSet<Integer>(1024)); dump("initial", -1, null, LinkedHashSet.class); set(new LinkedHashSet<Integer>(1024)); dump("initial", -1, null, TreeSet.class); set(new TreeSet<Integer>()); } /** * メモリ使用量の変化計測 - Map版 */ public static void map() { dump("initial", -1, null, HashMap.class); map(new HashMap<Integer, String>(1024)); dump("initial", -1, null, LinkedHashMap.class); map(new LinkedHashMap<Integer, String>(1024)); dump("initial", -1, null, TreeMap.class); map(new TreeMap<Integer, String>()); } /** * */ public static void list(List<String> list) { Class<?> cls = null; dump("gen list", -1, list, cls); cls = list.getClass(); for (int ct = N; ct > 0; --ct) { for (int i = 0; i < 2500000 * ct; ++i) { list.add("hello world"); } dump("add many entry", ct, list, cls); list.clear(); dump("clear", ct, list, cls); for (int i = 0; i < 2500000 * ct; ++i) { list.add("hello world"); } dump("add many entry", ct, list, cls); if (list instanceof RandomAccess) { while (list.size() > 0) { list.remove(list.size() - 1); } } else { for (Iterator<String> it = list.iterator(); it.hasNext();) { it.next(); it.remove(); } } dump("remove all", ct, list, cls); } list = null; dump("set to null", -1, list, cls); } /** * */ public static void set(Set<Integer> set) { Class<?> cls = null; dump("gen set", -1, set, cls); cls = set.getClass(); for (int ct = N; ct > 0; --ct) { for (int i = 0; i < 500000 * ct; ++i) { set.add(integers[i]); } dump("add many entry", ct, set, cls); set.clear(); dump("clear", ct, set, cls); for (int i = 0; i < 500000 * ct; ++i) { set.add(integers[i]); } dump("add many entry", ct, set, cls); for (Iterator<Integer> it = set.iterator(); it.hasNext();) { it.next(); it.remove(); } dump("remove all", ct, set, cls); } set = null; dump("set to null", -1, set, cls); } /** * */ public static void map(Map<Integer, String> map) { Class<?> cls = map.getClass(); dump("gen map", -1, map, cls); for (int ct = N; ct > 0; --ct) { for (int i = 0; i < 1000000 * ct; ++i) { map.put(integers[i], "hello world"); } dump("add many entry", ct, map, cls); map.clear(); dump("clear", ct, map, cls); for (int i = 0; i < 1000000 * ct; ++i) { map.put(integers[i], "hello world"); } dump("add many entry", ct, map, cls); for (Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator(); it.hasNext();) { it.next(); it.remove(); } dump("remove all", ct, map, cls); } map = null; dump("set to null", -1, map, cls); } private static int size(Object bout) { if (bout instanceof List<?>) { return ((List<?>) bout).size(); } else if (bout instanceof Map<?,?>) { return ((Map<?,?>) bout).size(); } else if (bout instanceof Set<?>) { return ((Set<?>) bout).size(); } else { return -2; } } private static void dump(String label, int ct, Object bout, Class<?> cls) { int size = -1; if (bout != null) { size = size(bout); } System.gc(); System.gc(); Runtime rt = Runtime.getRuntime(); long total = rt.totalMemory(); long free = rt.freeMemory(); long used = total - free; System.out.printf("[%28s] %-32s: %-16s: [%2d] (%10d) (%10.6f)\n", new Date(), (bout != null ? bout.getClass().getName() : (cls != null ? cls.getName() : "(null)")) + ": ", label, ct, size, (used / 1024.0 / 1024)); } }
実行結果は最初の部分だけ示す。
java.version = 1.5.0_11
java.vendor = Sun Microsystems Inc.
os.name = Windows Vista
[Thu Oct 29 14:32:03 JST 2009] java.util.ArrayList: : initial : [-1] ( -1) (153.077240)
[Thu Oct 29 14:32:05 JST 2009] java.util.ArrayList: : gen list : [-1] ( 0) (152.874870)
[Thu Oct 29 14:32:11 JST 2009] java.util.ArrayList: : add many entry : [ 8] ( 20000000) (251.663979)
：この結果から、キャッシュしているオブジェクトを含めたヒープの使用量は約152MBであることが分かる。この152MBを基準に、ヒープ使用量がどの程度増減するのかを見ていく。
残りの結果はグラフで。
List実装の場合はどっちも微妙。ArrayListはいったん増えたら減らないがLinkedListに比べるとピーク時のヒープ使用量は小さい。一方、LinkedListは要素をすべて削除した場合には元の使用量まで戻るが、増え方がArrayListに比べて大きい。
Set実装とMap実装は、TreeSet/TreeMapがサイズの増減に対しては強い。HashXxx/LinkedHashXxxは内部で配列を持っており、いったん増えたら減らないため、使いまわした場合にはこの増えた分は増えっぱなし。
