8 - 힙 ＊ ：빠른 8-원 묵시 우선순위 큐
8-heap* : A fast 8-ary implicit priority queue
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
스케쥴링이나 정렬과 같은 응용에 이용될 수 있는 우선순위 큐는 포인터를 사용하는 것과 포인터를 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 우선순위 큐는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 묵시 우선순위 큐에는 이진 트리에 근거한 전통적인 2-힝이 있는데, 이는 캐쉬 메모리를 효율적으로 이용하는 8-원 트리에 근거한 8-힝보다 느린 것으로 나타났다. 본 논문에서는 구현하기 쉽고 빠른 새로운 묵시 우선순위 큐인 8-힝*를 제안한다. 실험을 통하여 8-힝*가 2-힝 뿐만 아니라 8-힝보다 빠름을 보인다.
Abstract
Proirity queues(PQ) can be used in applications such as scheduling or sorting. The data structures for PQ can be constructed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. It is shown that a 2-heap, a traditional implicit PQ based on a binary tree, is slower than an 8-heap based on a 8-ary tree. This is because 8-heap utilizes cache memory more efficiently. This paper presents a novel fast implicit heap called 8-heap* which is easier to implement. Experimental results show that the 8-heap* is faster than 8-heap as well as 2-heap.
참고문헌 (7)
- "Fibonacci heaps and their uses in improved network optimization algorithms", pp.596~615 (1987)
- "The pairing heap：A new form of self-adjusting heap", 1(111129) (1986)
- T. J. Stasko, "Communications of the ACM", pp.234~249 (1987)
- "Fundamentals of Data Structures in C++" (1995), W. H. Freeman
- A. LaMarca, "The Influence of Caches on the Performance of Heaps", 1(4) (1996)
- "Supernode binary search trees", 14(3), pp.465~490
- "An empirical comparison of priority-queue and event-set implementation Communications of the Association for Computing Machinery", pp.300~311 (1986)