SLENDER ANKLES's 개발블로그

최소 비용 스패닝 트리

그래프의 서브 그래프 중에 모든 vertex를 가지고 있고, edge를 가지는 것을 스패닝 트리라고 한다.

가중치가 있는 그래프에서 이러한 스패닝 트리 중에서 최소 비용인 것을 최소 비용 스패닝 트리라고 한다. 

신장 트리의 중요한 요건

하나, 순환이 되어서는 안 된다.

잠시만!!

최소 비용 스패닝 트리는 실제로 어디에 쓸 수 있을까? 맹목적으로 알고리즘을 배우고 외우는 것 보다 어디에 쓰일 수 있는지에 대해서 알면 좀 더 필요서이 생길 것 같다. 

필요한 상황에 대해서 한 번 예를 들어보겠다. 우리가 위치기반 서비스를 통해 가장 서울 지역 관광 명소를 현재 위치를 기반으로 최소의 거리 비용으로 돌 수 있는 서비스를 만들고 있다고 쳐보자.

위의 경우에 우리는 최소의 비용으로 관광지를 모두 돌 수 있는 알고리즘이 필요하다. 이러한 상황에서 최소 비용 스패닝 트리 알고리즘을 적용 해 볼 수 있을 것이다.

최소 비용 스패닝 트리를 구하기 위한 몇 가지 용어들에 대해서 알아두어야 한다.

트리(tree)정점 : 지금까지 만든 트리에 속하는 정점

주변확인(fringe) 정점 : 트리에는 속하지 않고, 트리에 속한 정점과 인접한 정점

미확인(unseen) 정점 : 나머지 정점들

프림(Prim) 알고리즘

모든 정점을 미확인 정점으로 초기화한다.

임의의 정점 s를 출발정점으로 한다. 

s에 인접한 모든 정점을 주변 정점으로 둔다. 

while(주변 정점이 있으면)

{

트리 정점 t와 주변 정점들 사이의 최소 가중치를 가진 에지 tv를 선택한다.

v를 트리 정점으로 둔다. 에지 tv를 트리에 추가한다.

v에 인접한 모든 미확인 정점을 주변정점으로 한다. 

}

다음의 그래프를 통해 prim알고리즘을 통해 greedy한 방법으로 최소비용스패닝트리를 구하는 과정을 설명하겠다.

JVM은 가비지 컬렉션(GC)을 어떻게 처리하나?

(1) 힙(heap) 내의 객체 중에서 가비지(garbage)를 찾아낸다.

(2) 찾아낸 가비지를 처리해서 힙의 메모리를 회수한다.

JVM은 무엇을 기준으로 가비지를 선별하나?

reachability에 의해 결정된다.

유효한 참조가 있으면 reachability, 유효한 참조가 없으면 unreachability라고 하는데,

힙의 객체가 참조 되는 경우의 수는

(1) 스택영역에서 참조되는 경우

(2) 메소드영역에서 참조되는 경우

(3) 네이티브 스택(JNI)에서 참조되는 경우

(4) 힙내에서 참조되는 경우

 이렇게 4가지가 있는데, (1) ~ (3)까지를 root set 이라 하여 reachability, 즉 유효한 참조가 있다고 하고,

힙 내에서 있는 경우에는 unreachability라고 하여 유효하지 않은 참조로서 가비지 컬렉션의 대상이 된다.

원래의 jvm은 사용자 코드와 무관하게 gc가 일어나게끔 하였지만, 자바 버전이 높아지면서 일부 사용자의 코드가 gc에 반영될 수 있게 했다. soft, weak, phantom reference를 클래스 형태로 제공하면서 gc에 일부 참여할 수 있게 했다.

Map인터페이스를 구현한 하위 클래스들 HashMap과 LinkedHashMap과 TreeMap은 분명한 몇 가지 차이가 있다.

Map 인터페이스를 구현하였으므로, Key - Value Store형태로 저장하여, 사용할 수 있다는 공통점이 있다.

다음과 같은 차이점이 있다.

<입력되는 순서로 저장 보장>

HashMap

들어 간 순서로 저장되지 않으며, 출력되는 순서가 일치하는 것을 보장하지 않는다.

HashTable

들어 간 순서로 저장되지 않으며, 출력되는 순서가 일치하는 것을 보장하지 않는다.

LinkedHashMap

들어 간 순서대로 저장되어 출력되는 순서가 일치하는 것을 보장한다.

TreeMap

들어 간 순서대로 저장되지 않으며, 정렬된 순서로 저장되어 출력된다.

위의 결과로 봤을 때 HashMap과 HashTable 역시 정렬되는 것 같지만, 하나는 오름차순, 하나는 내림차순으로 정렬된다. 그냥 맘 편하게 안 된다고 생각하자.

<구조 및 성능>

HashMap

검색성능 O(1) 시간복잡도, 해시테이블과 비교하여 동기화(Synchronized) 지원하지 않지만 성능은 더 빠름

HashTable 

검색성능 O(1) 시간복잡도, 해시맵과 비교하여 동기화(Synchronized) 지원하지만 성능은 더 느림

LinkedHashMap

검색성능 O(1) 시간복잡도, 더블링크드리스트 자료구조로 이루어짐

TreeMap

검색성능 O(log(n)) 시간복잡도, Red Black Tree 자료구조로 이루어짐

<Null Keys and values>

HashMap

하나의 null Key와 여러 개의 null values를 허용한다.

HashTable

null Key 또는 null Value를 허용하지 않는다. => Null Pointer Exception 발생

LinkedHashMap

하나의 null Key와 여러 개의 null values를 허용한다.

TreeMap

null Key 또는 null Value를 허용하지 않는다. => Null Pointer Exception 발생

자바 성능 튜닝

성능에 영향을 미치는 요인은 크게 두 가지로 나눌 수 있다.

GC, HotSpot

* 2GB의 힙을 사용하는 JVM과 8GB의 힙을 사용하는 JVM의 차이는 어떻게 나타날까?

2GB의 힙을 사용하는 JVM이 GC를 처리하는 “STOP-THE-WORLD”가 짧을 것이므로 성능 상 유리할 수 있다.

반면에 8GB의 힙은 GC를 처리하는 시간은 길지 모르나 2GB의 힙에 비해 GC가 덜 빈번하게 일어나 성능 상 유리할 수도 있다.

32bit JVM vs 64bit JVM

동일 조건이라면 32bit JVM이 성능 상 더 유리하다.

왜?)

웹 서버의 가장 좋은 GC알고리즘은 무엇인가?

모든 경우는 아니지만 대부분 Concurrent Mark Sweep GC알고리즘이 성능이 가장 좋다. 이유는 낮은 딜레이가 중요하기 때문이다.

New 영역과 Old영역의 GC

New 영역의 GC보다 Old 영역에서 일어나는 Full GC가 일반적으로 시간이 오래 걸리기 때문에 New GC에서 충분한 크기를 잡아주는 것 역시 중요하다.

New영역이 너무 커져버려도 반응 속도가 느려 질 수 있다.

NEW영역에서의 GC의 메커니즘은 한 서바이버 영역에서 다른 서바이버 영역으로 복사가 일어나므로 이 또한 "STOP THE WORLD"가 발생한다.