Fibonacci heaps are especially desirable when the number of EXTRACT-MIN and DELETE operations is small relative to the number of other operations performed. This situation arises in many applications. For example, some algorithms for graph problems may call DECREASE-KEY once per edge. For dense graphs, which have many edges, the O(1) amortized time of each call of DECREASE-KEY adds up to a big improvement over the Θ(lg n) worst-case time of binary or binomial heaps.

From a practical point of view, however, the constant factors and programming complexity of Fibonacci heaps make them less desirable than ordinary binary (or k-ary) heaps for most applications. Thus, Fibonacci heaps are predominantly of theoretical interest.

Binary heap과 Binomial heap에서 각각의 operation이 왜 위와 같은 복잡도가 나오는지 잘 설명해주는 강의노트

binary_and_binomial_heaps.pdf

---

Introduction to Algorithms

저자

Cormen, Thomas H./ Leiserson, Charles E./ Rivest, 지음

출판사

McGraw-Hill | 2001-07-01 출간

카테고리

과학/기술

책소개

-

---

데이터가 정렬된 상태로 컨테이너에 들어있어야 할 경우에는 PriorityQueue를 자주 사용한다.

PriorityQueue는 Comparable 인터페이스를 구현하는 클래스(boolean compareTo를 구현하여 priority를 매김)를 데이터로 갖거나

생성자에서 따로 Comparator를 받아서 어떻게 priority를 매길지 정할 수 있다.

나같은 경우에는 평소에 데이터들의 순차적 access가 필요 할 때 PrioirtyQueue를 자주 사용한다.

하지만 얼마전에 PriorityQueue를 남용한 잘못을 저질렀다.

PriorityQueue가 사용되기에 적절한 곳은 (내 생각)

1. 컨테이너 안의 데이터가 priority에 따라 사용 순서가 결정

2. 컨테이너의 내용이 자주 바뀜 (poll과 add가 교차적으로 빈번하게 발생함)

3. 데이터를 재사용 할 일이 별로 없음

그런데 나같은 경우는 1번의 경우만 생각하고 2, 3번의 경우는 생각하지 않아서 문제가 발생했다.

어떤 raw 데이터를 통째로 읽어와서 PriorityQueue에 저장을 해놓고, PriorityQueue에서 데이터를 순차적으로 뽑아서, 데이터들 마다 "어떤 처리"를 한 다음 다시 파일로 쓰는 작업이었다.

여기서 나는 2번째 내용을 위반하였다.

나는 그냥 raw 데이터를 읽어오는 족족 PriorityQueue에다가 넣었는데, 이는 "오로지" 나중에 순차적으로 데이터를 뽑아 쓰려고 이렇게 하였다 (1번 이유).

그런데 이 경우 2번의 경우처럼 poll과 add가 교차적으로 빈번하게 발생하지 않는다.

즉, add가 한꺼번에 연속적으로 전부 발생하고나서, poll을 계속 하면서 데이터들을 처리한다.

따라서 이 경우에는 그냥 ArrayList에다가 데이터를 전부 add한 다음 그냥 Collections.sort로 ArrayList를 정렬해서 사용하면 그만이다.

(add와 poll의 교차수행이 빈번할 경우에 ArrayList보다 PriorityQueue가 좋은 점: ArrayList를 사용할 경우 데이터를 add하게되면 ArrayList의 "정렬됨"이라는 상태가 깨지기 때문에, valid한 ordered ArrayList를 유지하려면, add를 할때마다 매번 정렬을 해주어야 한다 (혹은, poll을 요청하기 전까지 add만 하다가 poll 요청이 들어오면 정렬을 해도 된다. 하지만 교차수행이 빈번한 경우에는 매번 정렬을 해야 할 수도 있다). 물론 ordered ArrayList는 정렬된 상태이므로, ArrayList를 traverse한 다음 적절한 위치에다가 add를 해주는 것도 가능하나, 이 또한 ArrayList의 특성상 비효율적일 수가 있다.)

사실 위의 경우에서는 PriorityQueue를 사용하거나 ArrayList와 Collections.sort를 사용하거나 별다른 차이가 없다.

왜냐하면 "재사용"이 없기 때문이다. 하지만 나는 재사용이 필요하였다 (3번 조건 위반).

만약 PriorityQueue의 데이터를 하나씩 뽑아와서 while (!pq.isEmpty()) 처리한다음 파일로 써버리면

PriorityQueue에 남아있는 내용이 없기 때문에, 만약 raw 데이터의 사용이 다시 필요하다면, 파일에서 또 읽어들여야 했다.

(PriorityQueue는 정렬된 list 상태가 아니라 heap 상태라서, iterator로 PriorityQueue를 traverse하게 되면 priority순으로 데이터가 traverse되지 않는다.

priority순으로 PriorityQueue의 데이터를 access하는 방법은 오로지 poll밖에 없다!)

문제는 이 파일이 용량이 꽤나 커서 읽어들이는데 10초정도의 시간이 소요된다는 것이었다.

따라서 내가 겪은 케이스에는 PriorityQueue를 사용하는것 보다 그냥 ArrayList와 Collections.sort를 사용하는 것이 낫다.

결론

1. 도구는 적재적소에 사용해야 한다.

2. 떄론 없어보이는 도구일지라도, 있어보이는 도구보다 나을때도 있다 (특히나 있어보이는 도구가 오로지 특정 상황에서만 최고의 성능을 발휘할 때).

Understanding Java Memory Structure

One strength of the java platform is that it shields the developer from the complexity of memory allocation and garbage collection.  We all know that java stores objects in a Heap memory.  Internally Java partitions the heap memory space logically into three areas called generations.

1. The Young Generation
2. The Tenured Generation
3. The Permanent Generation

Out if these three partitions, only the young and tenured generation spaces are used for allocating memory to objects. The permanent generation space is used for holding the data needed by the virtual machine to describe objects that do not have equivalence at the Java language level.

This partitioning is done in order to improve the performance of garbage collection as performing garbage collection on the entire heap will be very expensive. Instead the architects of java decided to partition the heap space into three parts.

The Young Generation

The young generation is where space is allocated for newly created objects.  In most applications, most of the objects created are used and referenced only for a very short span of time (high infant mortality rate), for example an iterator instance is discarded as soon as the loop is complete.

The purpose of having a separate space of young generation is to maximize promptness (the time between when an object becomes dead and when the memory becomes available) and to reduce the overhead of scanning the entire heap during every garbage collection process.

Garbage collection in the young generation happens when the space in this generation fills up and is called the minor collection. Minor collections can be optimized assuming a high infant mortality rate.  It is well-tuned in the sense that the young generation is large enough (and thus the period between minor collections long enough) that the minor collection can take advantage of the high infant mortality rate. The time required for garbage collection is directly proportional to the number of live objects.  A young generation full of dead objects is collected very quickly. Some surviving objects are moved to a tenured generation.

The Tenured Generation

Objects which survive the young generation are eventually moved into the tenured generation. Garbage collection in the tenured generation happens when the space in the tenured generation fills up and is called the major collection. Since the tenured generation usually have a large number of alive objects, the time required for garbage collecting the tenured generation is much higher than that for the young generation. Hence, garbage collection of the tenured generation is done at a much lesser rate than the young generation.

The Permanent Generation

The permanent generation is not used for allocating objects. Instead it is used for holding the data needed by the virtual machine to describe objects that do not have equivalence at the Java language level. For example objects describing classes and methods are stored in the permanent generation.


아래의 pdf파일은  Fillip Hanik이라는 개발자의 Inside the Java Virtual Machine: Memory Management and Troubleshooting이라는 제목의 슬라이드로 위의 내용을 이해하는데 도움이 된다.

출처:  http://www.springsource.com/files/uploads/all/pdf_files/news_event/Inside_the_JVM.pdf

Inside_the_JVM.pdf