[카테고리:] Java

작성일자

[Java] 우선순위 큐(Priority Queue) 활용 예제코드

자바에서 제공하는 컨테이너(Container) 중 어떤 데이터에 대해 우선순위 값을 부여하고, 이 우선순위를 기준으로 자동으로 정렬되어, 우선순위에 따라 데이터를 꺼내어 사용할 수 있는 우선순위 큐에 대한 예제 코드를 정리합니다.

먼저 우선순위 값을 갖는 데이터에 대한 타입 정의가 필요합니다. 아래처럼 Node라는 클래스를 추가해 타입을 정의합니다.

package tstPriorityQueue;

public class Node implements Comparable<Node> {
	private String UUID;
	private String parentUUID;
	private double G;
	private double H;
	
	public Node(String UUID, double G, double H) {
		this.UUID = UUID;
		this.parentUUID = null;
		this.G = G;
		this.H = H;
	}
	
	public double getF() { return G + H; }
	public double getG() { return G; }
	public double getH() { return H; }
	public String getNode() { return UUID; }
	public String getParentNode() { return parentUUID; }
	
	public void setG(double v) { G = v; }
	public void setH(double v) { H = v; }
	public void setParentNode(String v) { parentUUID = v; }
	
	@Override
	public int compareTo(Node target) {
	    if (this.getF() > target.getF()) {
            return 1;
        } else if (this.getF() < target.getF()) {
            return -1;
        }

	    return 0;
	}
	
	public String toString() {
		return UUID + '(' + getF() + ')';
	}
}

위의 클래스에서 중요한 부분은 우선순위값을 얻기 위한 getF() 함수입니다. 이 함수는 데이터의 상대적인 크기의 비교를 위한 인터페이스인 Comparable 구현할 때 사용되는 함수인데요. 바로 compareTo 라는 함수로써, 위의 경우에는 우선순위값이 작은 것을 먼저 꺼내어 사용하겠다는 정의입니다.

실제로, 위의 Node 클래스에 대한 타입으로 정의된 데이터를 컨테이너에 넣고, 사용하는 코드는 아래와 같습니다.

package tstPriorityQueue;

import java.util.PriorityQueue;

public class EntryMain {

	public static void main(String[] args) {
		// Create items
		Node node1 = new Node("423182c4-edb5-11e6-bc64-92361f002671", 1.0, 5.1);
		Node node2 = new Node("42318742-edb5-11e6-bc64-92361f002671", 1.0, 2.4);
		Node node3 = new Node("42318878-edb5-11e6-bc64-92361f002671", 1.0, 3.8);
		Node node4 = new Node("42318968-edb5-11e6-bc64-92361f002671", 1.0, 6.2);
		Node node5 = new Node("42318a3a-edb5-11e6-bc64-92361f002671", 1.0, 4.5);
		
		// Create priority queue
		PriorityQueue<Node> pQueue = new PriorityQueue<Node>();
		
		// Add items to queue
		pQueue.offer(node1); // same code as pQueue.add(node1)
		pQueue.offer(node2);
		pQueue.offer(node3);
		pQueue.offer(node4);
		pQueue.offer(node5);
		
		// Get items from queue
		while(!pQueue.isEmpty()) {
			Node node = pQueue.poll();
			System.out.println(node);
		}
	}

}

데이터를 5개 생성해서, 우선순위 큐 저장소에 저장하고 최종적으로 26번 코드를 통해 5개의 데이터를 우선순위에 따라 꺼내어 화면에 표시합니다. 그 결과는 아래와 같습니다.

42318742-edb5-11e6-bc64-92361f002671(3.4)
42318878-edb5-11e6-bc64-92361f002671(4.8)
42318a3a-edb5-11e6-bc64-92361f002671(5.5)
423182c4-edb5-11e6-bc64-92361f002671(6.1)
42318968-edb5-11e6-bc64-92361f002671(7.2)

작성일자

Java8, Stream에 대한 병렬처리

Java 8에서 제공하는 스트림(Streams)에 대한 기능에 대해 정리한 적이 있습니다. Java 8에서 스트림은 List 등과 같은 자료구조를 통해 생성할 수 있는 메모리 상의 또 다른 자료구조인데요. 이 스트림 자료구조를 통해 Filter, Sorted, map, forEach, anyMatch, allMatch, noneMatch, count, Reduce 맴버 함수를 호출할 수 있으며, 이러한 함수 호출에 대해 하나의 스레드만을 사용해 처리할 것인지, 아니면 멀티 스레드를 통해 병렬로 처리할 것인지 개발자가 매우 간단히 정할 수 있는 매커니즘을 제공합니다.

예를 들어서, 백만개의 UUID 문자열을 담고 있는 리스트가 있다고 합시다. 즉, 아래의 코드를 통해 메모리 상에 구성될 수 있습니다.

public static void main(String args[]) {
    int max = 1000000;
    List values = new ArrayList<>(max);
		
    for (int i=0; i

11번과 12번 코드가 각각 백만개의 문자열를 갖는 리스트를 정렬하는 방식을 하나의 스레드로 할 것인지, 멀티 스레드로 처리할 것인에 대한 함수 호출입니다. 먼저 sequential 함수를 살펴보면 아래와 같습니다.


public static void sequential(List v) {
    long t0 = System.nanoTime();
    /*long count = */ v.stream().sorted().count();
    long t1 = System.nanoTime();
		
    long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0);
    System.out.println(String.format("sequential sort took: %d ms", millis));
}



3번 코드가 스트림에서 제공하는 sorted 함수를 통해 직관적으로 정렬하는 것으로써 코드 한줄이지만 그 내부는 다소 복잡하고, 특히나 백만개에 대한 정렬이므로 상당한 CPU 리소스를 사용할 것입니다. 그리고 다음은 멀티 스레드를 통한 parallel 함수입니다.


public static void parallel(List v) {
    long t0 = System.nanoTime();
    /* long count = */ v.parallelStream().sorted().count();
    long t1 = System.nanoTime();
		
    long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0);
    System.out.println(String.format("parallel sort took: %d ms", millis));
}



sequential 함수와의 차이점이라고는 오직 스트림을 생성하기 위해 3번 코드의 stream() 대신 parallelStream() 호출입니다. 이제 실행해 보면 제 노트북에서는 다음과 같은 결과가 나옵니다.


sequential sort took: 708 ms
parallel sort took: 244 ms



제 노트북이 멀티 코어 CPU이므로 동일한 연산이지만 병렬로 정렬하는데 소요되는 시간이 훨씬 더 빠른 처리된 결과를 볼 수 있습니다. Java 8에서 제공하는 스트림을 통해 데이터의 덩어리를 매우 직관적이며 매우 쉽게 병렬로 처리할 수 있다는 것을 알 수 있습니다.


요즘 golang과 같은 최신의 언어에서도 그렇고... Java나 C++과 같은 언어에서 람다 지원을 통해 작성된 코드를 살펴봐도 그렇고.. OOP 보다는 함수 지향적인 코딩이 상당히 강조되는 것을 느낍니다. OOP 적인 사고방식 보다는 컴포지션(Composition)과 재귀적 호출을 통한 함수 작성 그리고 짧은 코드로 구성한 단위 함수들의 조합을 통한 프로그래밍 방식에 익숙해 지는 것이 필요할 듯 합니다.