要件:100万レコードからなる{ID,SCORE}の中からTOP N件をSCORE降順で得たい。
普通にやる
HashMap<String, Double> items = new HashMap<>(); for (int i = 0; i < 1000000; i++) { items.put(String.valueOf(i), r.nextDouble()); } List<Entry<String, Double>> entries = new ArrayList<>(items.entrySet()); long t10 = System.currentTimeMillis(); Collections.sort(entries, new Comparator<Entry<String, Double>>() { //比較関数 @Override public int compare(Entry<String, Double> o1, Entry<String, Double> o2) { //return o1.getValue().compareTo(o2.getValue()); //昇順 return o2.getValue().compareTo(o1.getValue()); //降順 } }); long t11 = System.currentTimeMillis(); System.out.println((t11 - t10) + "ms");
TOP Nだけを常時監視する
System.out.println("#### sort only for top N"); int TOP_N = 1000000; double[] items2 = new double[TOP_N]; long t20 = System.currentTimeMillis(); for (int i = 0; i < TOP_N; i++) { items2[i] = r.nextDouble(); } List<Integer> topIndexes = sortedTopNIndex(items2, 1000); long t21 = System.currentTimeMillis(); System.out.println((t21 - t20) + "ms"); public static List<Integer> sortedTopNIndex(double[] arr, int n) { List<Integer> indexes = new ArrayList<>(); double minInTopN = -1.0; int len = arr.length; loop1: for(int i=0; i<len; i++){ double val = arr[i]; if (val > minInTopN){ int indexesLen = indexes.size(); for (int j=0; j<n && j<indexesLen; j++){ int index = indexes.get(j); double topVal = arr[index]; if (val < topVal){ indexes.add(j, i); if (indexes.size() > n){ indexes.remove(0); } minInTopN = arr[indexes.get(0)]; continue loop1; } } indexes.add(i); if (indexes.size() > n){ indexes.remove(0); } minInTopN = arr[indexes.get(0)]; continue loop1; } } return indexes; }
結果
普通にやる:1301ms
TOP Nだけを常時監視する:94ms