巨大な配列のソートの計算量を減らす

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