4-딥* : 캐쉬를 이용한 빠른 4-원 딥
4-Deap* : A Fast 4-ary Deap using Cache
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
스케쥴링이나 정렬과 같은 응용에 이용될 수 있는 양단 우선순위 큐는 포인터를 사용하는 것과 포인터를 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 자료 구조는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 본 논문에서는 캐쉬 메모리를 효율적으로 이용하는 새로운 묵시 양단 우선순위 큐인 4-딥*를 제안한다. 실험을 통하여, 제안된 4-딥*가 이진 트리에 근거한 딥뿐만 아니라 대칭 최소-최대 힙보다 빠름을 보인다.
Abstract
Double-ended Proirity queues(DEPQ) can be used in applications such as scheduling or sorting. The data structures for DEPQ can be constructed with or without pointers. The implicit representation without pointers uses less memory space than pointer-based representation. This paper presents a novel fast implicit heap called 4-deap* which utilizes cache memory efficiently. Experimental results show that the 4-deap* is faster than symmetric min-max heap as well as deap.
참고문헌 (8)
- "The deap-a double-ended heap to implement double-ended priority queues", 26, pp.33~36 (1987)
- "Min-Max heaps and generalized priority queues", pp.996~1000 (1986)
- "Symmetric Min-Max heap：A Simpler data structure for double-ended priority queue", 69, pp.197~199 (1999)
- "Handbook of data structures and applications" (2004), Chapman-Hall[DOI]
- "Supernode binary search trees", 14(3), pp.465~490 (2003)
- "8-?*：빠른 8-원 묵시 우선순위 큐"", 11-A(3), pp.213~216
- "Mergeable double-ended priority queues", 10(1), pp.1~17 (1999)
- "An empirical comparison of priority-queue and event-set implementation Comm. of the Association for Computing Machinery", 29(4), pp.300~311 (1986)