PriorityQueue vs Collections.sort: 왜 sort가 더 효율적일까?

이전에 어떤 분이 이야기를 해줬던 내용에 대하여 정리하고자 한다.

질문 내용

import java.util.*;

class Main {
    // SORT 방식
    static List<String> solveArr(Map<String, List<String>> map) {
        List<Node> arr = new ArrayList<>();

        for (String key : map.keySet()) {
            arr.add(new Node(key, map.get(key).size()));
        }

        Collections.sort(arr);

        List<String> result = new ArrayList<>();
        for (Node n : arr) {
            result.add(n.key);
        }

        return result;
    }

    // PQ 방식
    static List<String> solvePQ(Map<String, List<String>> map) {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (String key : map.keySet()) {
            pq.add(new Node(key, map.get(key).size()));
        }

        List<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll().key);
        }

        return result;
    }
}

class Node implements Comparable<Node> {
    String key;
    int len;

    Node(String key, int len) {
        this.key = key;
        this.len = len;
    }

    @Override
    public int compareTo(Node o) {
        if (this.len == o.len) {
            return this.key.compareTo(o.key);
        }
        return o.len - this.len;
    }
}

solvePQ방식과 solveArr 방식 중에 어느 방식이 더 효율적일까??

 

solvePQ의 방식은 다음과 같다.

1. Map에 있는 데이터를 PQ에 넣는다.
2. 반환할 자료구조인 List에 Pq의 데이터를 poll()을 통해 넣는다.
3. List를 반환한다.

solveArr의 방식은 다음과 같다.

1. Map에 있는 데이터를 ArrayList에 넣는다.
2. ArrayList를 Collections로 정렬한다.
3. 정렬한 데이터를 반환할 자료구조인 List에 넣는다.
4. List를 반환한다.

저는 당연히, PQ방식으로 poll()을 통해 메모리를 좀 더 효율적으로 처리할 수 있다고 생각하였습니다.

테스트

import java.util.*;

class Main {
    static final int N = 500_000;
    static final int LOOP = 5;

    public static void main(String[] args) {
        Map<String, List<String>> map = generateRandomData(N);

        // 워밍업 (JIT 최적화)
        for (int i = 0; i < 3; i++) {
            solveArr(map);
            solvePQ(map);
        }

        // PQ 측정
        long pqTime = 0;
        long pqMem = 0;

        for (int i = 0; i < LOOP; i++) {
            System.gc();

            long beforeMem = getUsedMemory();
            long start = System.nanoTime();

            List<String> result = solvePQ(map);

            long end = System.nanoTime();
            long afterMem = getUsedMemory();

            pqTime += (end - start);
            pqMem += (afterMem - beforeMem);

            result = null;
        }

        // SORT 측정
        long sortTime = 0;
        long sortMem = 0;

        for (int i = 0; i < LOOP; i++) {
            System.gc();

            long beforeMem = getUsedMemory();
            long start = System.nanoTime();

            List<String> result = solveArr(map);

            long end = System.nanoTime();
            long afterMem = getUsedMemory();

            sortTime += (end - start);
            sortMem += (afterMem - beforeMem);

            result = null;
        }

        // 결과 출력
        System.out.println("===== 결과 =====");

        System.out.println("SORT 평균 시간(ms): " + (sortTime / LOOP) / 1_000_000.0);
        System.out.println("PQ 평균 시간(ms):   " + (pqTime / LOOP) / 1_000_000.0);

        System.out.println("SORT 평균 메모리(MB): " + (sortMem / LOOP) / (1024.0 * 1024.0));
        System.out.println("PQ 평균 메모리(MB):   " + (pqMem / LOOP) / (1024.0 * 1024.0));
    }

    // SORT 방식
    static List<String> solveArr(Map<String, List<String>> map) {
        List<Node> arr = new ArrayList<>();

        for (String key : map.keySet()) {
            arr.add(new Node(key, map.get(key).size()));
        }

        Collections.sort(arr);

        List<String> result = new ArrayList<>();
        for (Node n : arr) {
            result.add(n.key);
        }

        return result;
    }

    // PQ 방식
    static List<String> solvePQ(Map<String, List<String>> map) {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        for (String key : map.keySet()) {
            pq.add(new Node(key, map.get(key).size()));
        }

        List<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll().key);
        }

        return result;
    }

    // 데이터 생성
    static Map<String, List<String>> generateRandomData(int n) {
        Random rand = new Random();
        Map<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            String key = "key_" + i;

            int size = rand.nextInt(50) + 1;
            List<String> list = new ArrayList<>();

            for (int j = 0; j < size; j++) {
                list.add("a"); // 노이즈 줄이기
            }

            map.put(key, list);
        }

        return map;
    }

    // 메모리 측정
    static long getUsedMemory() {
        Runtime r = Runtime.getRuntime();
        return r.totalMemory() - r.freeMemory();
    }
}

class Node implements Comparable<Node> {
    String key;
    int len;

    Node(String key, int len) {
        this.key = key;
        this.len = len;
    }

    @Override
    public int compareTo(Node o) {
        if (this.len == o.len) {
            return this.key.compareTo(o.key);
        }
        return o.len - this.len;
    }
}

해당 코드로 확인해본 결과는 다음과 같다.

===== 결과 =====
SORT 평균 시간(ms): 613.496013
PQ 평균 시간(ms):   1305.291275
SORT 평균 메모리(MB): 31.42371368408203
PQ 평균 메모리(MB):   26.75941276550293

PQ의 시간이 Arr 방식의 2배정도 걸리고, 평균 메모리 차이는 그렇게 크지 않았다.

PQ가 메모리가 더 효율적으로 나온 이유

PQ에 넣었던 데이터들 중 일부는 가장 먼저 GC의 대상이 되기 때문에 메모리를 Arr방식보다 좀 더 적게 사용된다.

Arr이 속도가 더 효율적으로 나온 이유

static List<String> solveArr(Map<String, List<String>> map) {
    List<Node> arr = new ArrayList<>();

    for (String key : map.keySet()) {
        arr.add(new Node(key, map.get(key).size())); // O(1)
    } // O(n)

    Collections.sort(arr); // O(n log n)

    List<String> result = new ArrayList<>();
    for (Node n : arr) {
        result.add(n.key); // O(1)
    } // O(n)

    return result;
}
// 전체 : O(n log n)

static List<String> solvePQ(Map<String, List<String>> map) {
    PriorityQueue<Node> pq = new PriorityQueue<>();

    for (String key : map.keySet()) {
        pq.add(new Node(key, map.get(key).size())); // O(log n)
    }// O(n log n)

    List<String> result = new ArrayList<>();
    while (!pq.isEmpty()) {
        result.add(pq.poll().key); // O(log n)
    } // O(n log n)

    return result;
}
// 전체 : O(2n log n)

그 코드의 시간복잡도 차이는 Arr는 O(n log n), PQ는 O(2n log n) 으로 걸려 Arr의 방식으 PQ의 방식보다 2배 빠르게 진행되는 것이다.

 

해당 내용은 시간 복잡도를 기준으로 설명한다면, 쉽게 설명이 가능하다.