[카테고리:] 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)과 재귀적 호출을 통한 함수 작성 그리고 짧은 코드로 구성한 단위 함수들의 조합을 통한 프로그래밍 방식에 익숙해 지는 것이 필요할 듯 합니다.
작성일자

[Java] Java8, 스트림(Streams)

A java.util.Stream 클래스는 동일한 타입의, 다수의 데이터에 대해 다양한 연산을 빠르게 적용할 수 있는 기능을 제공합니다. 스트림은 java.util.Collection 객체로부터 생성되는데, 리스트나 집합 등이 그 예인데요. 맵은 지원하지 않습니다. 다음과 같은 리스트가 있다고 하고 이 리스트를 통해 스트림을 만들어 다양한, 유용한 연산의 예제 코드를 언급하겠습니다.

List stringCollection = new ArrayList<>();
		
stringCollection.add("신숙주");
stringCollection.add("김옥자");
stringCollection.add("조미현");		
stringCollection.add("송기숙");
stringCollection.add("최미라");
stringCollection.add("박미남");
stringCollection.add("김구라");
stringCollection.add("김형준");

filter

요소 중 ‘김’으로 시작하는 문자열을 걸러내어 화면에 표시합니다.

stringCollection
    .stream()
    .filter((s) -> s.startsWith("김"))
    .forEach(System.out::println);

sorted

요소를 정렬하고, 정렬된 리스트에 대해 ‘김’자로 시작하는 요소를 화면에 표시합니다.

stringCollection
    .stream()
    .sorted()
    .filter((s) -> s.startsWith("김"))
    .forEach(System.out::println);

map

요소 각각에 함수를 호출합니다. 아래는 각 요소의 뒤에 ‘씨’ 자를 붙이고 정렬한 후 출력합니다.

stringCollection
    .stream()
    .map((a) -> a + "씨")
    .sorted((a, b) -> b.compareTo(a))
    .forEach(System.out::println);

count

‘김’자로 시작하는 요소의 개수를 얻습니다.

long cntKim = stringCollection
    .stream()
    .filter((s) -> s.startsWith("김"))
    .count();

reduce

각 요소를 하나로 묶습니다.

Optional reduced = stringCollection
    .stream()
    .sorted()
    .reduce((s1, s2) -> s1 + "," + s2);

reduced.ifPresent(System.out::println);

anyMatch, allMatch, noneMatch

각 요소에 대해 지정한 조건에 부합하는지를 검사합니다. 첫번째인 anyMatch는 ‘김’으로 시작하는 요소가 하나라도 있다면 참입니다. 두번째인 allMatch는 모든 요소가 ‘김’으로 시작해야만 참입니다. 끝으로 세번째는 ‘고’로 시작하는 요소가 하나도 없어야 ‘참’입니다.

boolean anyStartsWithKim = stringCollection
    .stream()
    .anyMatch((s) -> s.startsWith("김"));

boolean allStartsWithKim = stringCollection
    .stream()
    .allMatch((s) -> s.startsWith("김"));

boolean noneStartsWithGo = stringCollection
    .stream()
    .noneMatch((s) -> s.startsWith("고"));
작성일자

[Java] Java8, 람다 표현식(Lambda expressions)

많은 프로그래밍 언어에서 람다 표현식은 한번 사용하고 버릴 함수를 정의하기 위한 용도로 많이 사용됩니다. 물론 이 람다 표현식에 의해 만들어진 함수를 변수에 담아 두번 이상 사용할 수도 있지만… 어찌되었든, 람다는 빠르게 함수를 만들어 사용하고는, 버리는 용도로 사용합니다.

Java 8에서 람다 표현식을 지원하고 있는데요. 문자열 요소를 가지는 리스트를 정렬하는 예를 통해 람다 표현식을 살펴 보겠습니다. 정렬할 문자열 리스트로 사용할 names 객체 변수는 아래와 같습니다.

List names = 
    Arrays.asList("검소", "겸손", "명상", "욕심", "탐하는 마음", "경솔", "교만", "어질지못함");

람다 표현식이 아닌 우리가 이미 알고 있는 방식의 코드는 아래와 같습니다.

Collections.sort(names, new Comparator() {
    @Override
    public int compare(String a, String b) {
        return -b.compareTo(a);
    }
});

위의 Collections의 sort 함수의 두번째 인자에 1회용 목적으로 익명 객체를 생성해 던져주고 있습니다. 이 익명 객체를 생성하기 위한 인터페이스가 단 하나의 매서드에 대한 정의를 필요로 합니다. 이를 람다 표현식으로 바꾸면 아래와 같습니다.

Collections.sort(names, (String a, String b) -> {
    return -b.compareTo(a);
});

람다식을 컴파일로가 해석할 때 어떤 타입의 어떤 매서드를 정의하는지를 자동으로 추론해 줍니다. (염병할, 나보다 더 똑똑해!) 위의 람다식을 보면 함수의 코드가 한줄이므로 아래처럼 더 줄일 수 있습니다.

Collections.sort(names, (String a, String b) ->  -b.compareTo(a));

코드가 한줄이므로 {}을 제거할 수 있고, return 키워드를 제거해도 반환한다라는 개념을 이미 추론을 통해 파악하고 있습니다. (이제 니가 코딩해라, 난 뭐하냐?) 충분히 줄였다 싶을 람다 표현식을 더 줄일 수 있는데요. 어차피 어떤 함수를 람다식으로 정의하는지를 알고 있다면 해당 함수의 타입을 명시적으로 언급하지 않아도 추론이 가능할 것으므로 아래처럼 더 최적화할 수 있습니다.

Collections.sort(names, (a, b) -> -b.compareTo(a));

(이젠 나도 모르겠을 암호 코드.. ㅜ_ㅜ) 위의 내용은 람다식의 일부입니다. 람다에 좀더 깊이 들어가면.. 깜짝 놀라거임.. -O-;