heap vs TreeMap<key, list>

treemap<String, ArrayList<String>());
vs
PriorityQueue<Node>
Node(String, String);

 

과연 어느게 더 메모리를 적게 먹고, 시간을 적게 소요할까요?

 

코드를 작성하는 와중에 단순 PriorityQueue에 데이터를 넣다보면, java heap memory error가 발생할 거 같다는 생각을 하게 되었습니다.

 

간단한 이유로는

하나의 바구니에 데이터를 모두 담는가 vs 여러 바구니에 나눠서 담는가 에 대하여 생각해보면 당연 후자가 더 효율적이라고 생각했기 때문입니다.

 

이를 증명하기 위하여 하나의 테스트과정을 거치게 되었습니다.

 

Map의 소스는 이러합니다.

Map<String, ArrayList<String>> map = new TreeMap<>();
for(int i = 0; i < 1000; i++) {
	map.put(String.valueOf(i), new ArrayList<>());
	for(int j = 0; j < 10000; j++) {
		map.get(String.valueOf(i)).add(String.valueOf(j));
	}
}

 

PriorityQueue의 소스는 이러합니다.

PriorityQueue<Node> pq = new PriorityQueue<>();
		
for(int i = 0; i < 1000; i++) {
	for(int j = 0; j < 10000; j++) {
		pq.add(new Node(String.valueOf(i), String.valueOf(j)));
	}
}


class Node implements Comparable<Node>{
	String time, name;
	
	public Node(String time, String name) {
		this.time = time;
		this.name = name;
	}

	@Override
	public int compareTo(Node o) {
		return this.time.compareTo(o.time);
	}
}

 

이 둘의 시간과 메모리를 측정하면 이렇습니다.

	TreeMap<String, ArrayList<String>()>:	PriorityQueue<Node>
시간	634ms	789ms
메모리	691,384	690,264

 

 

처음 예상과는 다르게 차이가 메모리적인 차이는 별로 없다고 결과가 나오게 되었습니다.

그러나 시간적으로는 TreeMap이 조금 더 빠릅니다.

 

원래는 1,000 x 100,000 만큼 데이터를 늘려서 테스트하고자 하였으나, PriorityQueue에서 java heap space error가 발생하여 테스트해보지 못하였습니다.

 

추후에 해당 방식으로 구현을 해야한다면, TreeMap으로 구현할 거 같습니다.