要件: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 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