Sorted Collection

Sorted Collection が使いたいケースがあったので、APIの性能を比較した。

    static class User implements Comparable<User>{
        long time;
        String userId = "01234567";
        public User(long time) {
            this.time = time;
        }
        @Override
        public int compareTo(User o) {
            if (this.time < o.time) {
                return -1;
            }else if (this.time == o.time) {
                return 0;
            }else {
                return 1;
            }
        }
    }
    
    public static void main(String[] args) {
        final int CNT = 1000000;
        
        MemoryMeter meter = MemoryMeter.builder().build();

        // 重複のない乱数群を用意
        Random r = new Random();
        HashMap<Integer, Object> nums = new HashMap<>(CNT);
        for (int i = 0 ; i < CNT ; ++i) {
            int j = r.nextInt();
            if (nums.containsKey(j)) {
                --i;
                continue;
            }
            nums.put(j, null);
        }
        
        PriorityQueue<User> q = new PriorityQueue<>();
        long start = System.currentTimeMillis();
        Iterator<Integer> itor = nums.keySet().iterator();
        for (int i = 0 ; i < CNT ; ++i) {
            q.offer(new User(itor.next()));
        }
        Log.d("offer spent " + (System.currentTimeMillis() - start));
        Log.d("added " + q.size());
        long bytes = meter.measureDeep(q);
        Log.d("PriorityQueue = " + bytes + " bytes, " + bytes / CNT + " for one entry");
        start = System.currentTimeMillis();
        while(true){
            User u = q.peek();
            if (u == null) {
                break;
            }
            if (u.time > 500000) {
                break;
            }
            q.poll();
        }
        Log.d("remove spent " + (System.currentTimeMillis() - start));
        Log.d("PriorityQueue.size = " + q.size());
        
        Log.d("");
        
        TreeMap<User,Object> m = new TreeMap<>();
        r = new Random(0);
        start = System.currentTimeMillis();
        itor = nums.keySet().iterator();
        for (int i = 0 ; i < CNT ; ++i) {
            m.put(new User(itor.next()), null);
        }
        Log.d("put spent " + (System.currentTimeMillis() - start));
        Log.d("puted " + m.size());
        bytes = meter.measureDeep(m);
        Log.d("TreeMap       = " + bytes + " bytes, " + bytes / CNT + " for one entry");
        start = System.currentTimeMillis();
        NavigableMap<User, Object> hm = m.headMap(new User(500000), true);
        hm.clear();
        Log.d("remove spent " + (System.currentTimeMillis() - start));
        Log.d("TreeMap.size       = " + m.size());
    }

offer spent 154
added 1000000
PriorityQueue = 28554640 bytes, 28 for one entry
remove spent 324
PriorityQueue.size = 498783

put spent 843
puted 1000000
TreeMap       = 64000096 bytes, 64 for one entry
remove spent 60
TreeMap.size       = 498783