우선순위 큐 성능 시험에 관한 연구

정해재 한국정보처리학회 2010 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.17 No.4

This paper proposes a set of runtime test models for priority queues and shows the runtime test results based on the proposed test models for the representative priority queues: the traditional heap, post-order heap, and pairing heap. Among these heaps, the traditional heap is the worst in time complexity analyzed. But, according to our experimental results based on the test models proposed, it is shown that the slowest one is the pairing heap that utilizes pointers and the fastest one is the traditional heap. For the two implicit heaps, these results are in contrary to the fact that the post-order heap is better than the traditional heap in time complexity analyzed. 본 논문에서는 우선순위 큐에 대한 성능 시험 모델을 제안하고, 제안된 모델에 따라 대표적인 우선순위 큐인 전통 힙, 후순위 힙, 및 페어링 힙의 성능 시험 결과를 보여준다. 이들 중 전통 힙이 분석된 시간복잡도에 있어서 최악인 것으로 알려져 있다. 그러나 제안된 성능 시험 모델에 근거한 성능 시험 결과에 따르면, 포인터를 사용하는 페어링 힙이 가장 느리고 전통 힙이 가장 빠른 것으로 나타났다. 두 묵시 힙에 대해서도, 분석된 시간복잡도로는 후순위 힙이 전통 힙보다 우수하지만, 성능 시험 결과는 반대인 것으로 나타났다.

우선순위 큐 알고리즘 성능 평가

정해재 한국정보기술학회 2010 한국정보기술학회논문지 Vol.8 No.6

묵시 다원 AM-힙

정해재 한국정보처리학회 2018 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.7 No.12

This paper proposes an implicit d-ary priority queue, called AM(d)-heap that is a generalized version of AM-heap, in which insert operation takes constant amortized time and remove operation takes O(logn) time. According to our experimental results, the best performance was shown when d is 4 or 8. Also, AM(d)-heap is about 1.5~1.8 times faster than the postorder heap. 본 논문에서는 AM-힙의 다원 버전인 AM(d)-힙이라고 하는 묵시 다원 우선순위 큐를 제안하며, 제안된 AM(d)-힙에서는 삽입에 O(1) 전이시간이 걸리고 삭제 연산에 O(logn) 시간이 걸린다. 실험 결과에 따르면, 전체적으로 d가 4 또는 8일 때 가장 우수한 성능을 나타내었다. 기존의 후위힙과 비교하면 AM(d)-힙이 약 1.5~1.8배 빠른 것으로 나타났다.

IMI-힙: 상수 삽입 전이 시간 복잡도를 가진 묵시 양단 우선순위 큐

정해재 한국정보처리학회 2019 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.8 No.2

Priority queues, one of the fundamental data structures, have been studied for a long time by computer scientists. This paper proposes an implicit double-ended priority queue, called IMI-heap, in which insert operation takes constant amortized time and each of removal operation of the minimum key or the maximum key takes O(logn) time. To the author’s knowledge, all implicit double-ended priority queues that have been published, perform insert, removeMin and removeMax operations in O(logn) time each. So, the proposed IMI-heap is superior than the published heaps in terms of insertion time complexity.The abstract should concisely state what was done, how it was done, principal results, and their significance. 우선순위 큐은 근본적인 자료 구조 중의 하나이며 오랫동안 많은 연구가 이루어여 왔다. 본 논문에서는 IMI-힙이라고 하는 묵시 양단 우선순위 큐를 제안한다. 제안된 IMI-힙에서는 삽입에 O(1) 전이시간이 걸리고 최소값과 최대값 삭제 연산에 각각 O(logn) 시간이 걸린다. 기존에 발표된 묵시 양단 우선순위 큐는 삽입과 최소/최대값 삭제에 모두 O(logn) 시간이 걸리는 것으로 본 저자는 알고 있다. 따라서 제안된 IMI-힙은 삽입 시간 복잡도에 있어서 기존의 힙보다 우수하다.

k 사다리꼴 셋의 영역 중심 비교 알고리즘

정해재,Jung, Hae-Jae 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.6

반도체 생산을 위한 마스크 자동 생성과 같은 기하 객체를 다루는 응용에서는, 사다리꼴로 분할된 수 많은 다각형으로 구성된 도면에 새로운 다각형을 추가하거나 삭제하기 위해 사다리꼴 삽입, 삭제, 및 검색 연산을 한다. 동일한 다각형에 대해 분할된 사다리꼴은 사용된 분할 알고리즘에 따라 모양, 크기 등에 있어서 다르게 된다. 사다리꼴로 구성된 기하 객체를 다루는 프로그램을 검증하는 것과 같은 예에서는 구성된 도면의 관심 부분을 나타내는 여러 사다리꼴 셋을 비교하는 알고리즘이 필요하다 본 논문에서는 k개 도면의 관심 영역으로부터 각각 추출된 사다리꼴로 구성된 k 셋이 주어졌을 때, 그 k 셋이 형성하는 기하 도형틀이 동일한지 아닌지를 비교하는 새로운 알고리즘을 제시한다. 제시된 알고리즘은 각 셋이 공히 n개의 사다리꼴을 포함하고 있다고 가정할 때, O(2$^{k-2}$ $n^2$(log n+k))시간 복잡도를 가진다. 제시된 알고리즘은 입력셋의 수 k(<<n)가 적을 때 훑기 중심 알고리즘과 동일한 시간 복잡도 O( $n^2$ log n)를 가지며, 특히 k 셋이 동일하거나 대부분 동일한 사다리꼴들로 구성되어 있을 경우 훑기 중심 알고리즘보다 kn배까지 빠른 것은 나타났다.다. In the applications like automatic masks generation for semiconductor production, a drawing consists of lots of polygons that are partitioned into trapezoids. The addition/deletion of a polygon to/from the drawing is performed through geometric operations such as insertion, deletion, and search of trapezoids. Depending on partitioning algorithm being used, a polygon can be partitioned differently in terms of shape, size, and so on. So, It's necessary to invent some comparison algorithm of sets of trapezoids in which each set represents interested parts of a drawing. This comparison algorithm, for example, may be used to verify a software program handling geometric objects consisted of trapezoids. In this paper, given k sets of trapezoids in which each set forms the regions of interest of each drawing, we present how to compare the k sets to see if all k sets represent the same geometric scene. When each input set has the same number n of trapezoids, the algorithm proposed has O(2$^{k-2}$ $n^2$(log n+k)) time complexity. It is also shown that the algorithm suggested has the same time complexity O( $n^2$ log n) as the sweeping-based algorithm when the number k(<< n) of input sets is small. Furthermore, the proposed algorithm can be kn times faster than the sweeping-based algorithm when all the trapezoids in the k input sets are almost the same.

8-힢*: 빠른 8-원 묵시 우선순위 큐

정해재,Jung, Hae-jae 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.3

스케줄링이나 정렬과 같은 응용에 이용될 수 있는 우선순위 큐는 포인터를 사용하는 것과 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 우선순위 큐는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 묵시 우선순위 에는 이진 트리에 근거한 전통적인 2-힙이 있는데, 이는 캐쉬 메모리를 효율적으로 이용하는 8-원 트리에 근거한 8-힙보다 느린 것으로 나타났다. 본 논문에서는 구현하기 쉽고 빠른 새로운 묵시 우선순위 큐인 8-힙*를 제안한다. 실험을 통하여 8-힙*가 2-힙 뿐만 아니라 8-힙보다 빠름을 보인다. 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 if shown that a 2-heap, a traditional Implicit PQ based on a binary tree, is slower than an f-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.

4-딥? : 캐쉬를 이용한 빠른 4-원 딥

정해재,Jung Haejae 한국정보처리학회 2004 정보처리학회논문지 A Vol.11 No.7

스케쥴링이나 정렬과 같은 응용에 이용될 수 있는 양단 우선순위 큐는 포인터를 사용하는 것과 포인터를 이용하지 않고 묵시적으로 표현하는 두 가지가 있다. 묵시 자료 구조는 메모리 이용에 있어서 포인터를 사용하는 것보다 효율적이다. 본 논문에서는 캐쉬 메모리를 효율적으로 이용하는 새로운 묵시 양단 우선순위 큐인 4-딥$\ast$를 제안한다. 실험을 통하여, 제안된 4-딥$\ast$가 이진 트리에 근거한 딥뿐만 아니라 대칭 최소-최대 합보다 빠름을 보인다. Double-ended Proirity queues(DEPQ) can be used in applications such as scheduling or sorting. The data structures for DEPQ can be con-structed 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-deapr$\ast$ which utilizes cache memory efficiently. Experimental results show that the 4-deap$\ast$ is faster than symmetric min-max heap as well as deap.

우선순위 큐 성능 시험에 관한 연구

정해재,Jung, Hae-Jae 한국정보처리학회 2010 정보처리학회논문지 A Vol.17 No.4

본 논문에서는 우선순위 큐에 대한 성능 시험 모델을 제안하고, 제안된 모델에 따라 대표적인 우선순위 큐인 전통 힙, 후순위 힙, 및 페어링 힙의 성능 시험 결과를 보여준다. 이들 중 전통 힙이 분석된 시간복잡도에 있어서 최악인 것으로 알려져 있다. 그러나 제안된 성능 시험 모델에 근거한 성능 시험 결과에 따르면, 포인터를 사용하는 페어링 힙이 가장 느리고 전통 힙이 가장 빠른 것으로 나타났다. 두 묵시 힙에 대해서도, 분석된 시간복잡도로는 후순위 힙이 전통 힙보다 우수하지만, 성능 시험 결과는 반대인 것으로 나타났다. This paper proposes a set of runtime test models for priority queues and shows the runtime test results based on the proposed test models for the representative priority queues: the traditional heap, post-order heap, and pairing heap. Among these heaps, the traditional heap is the worst in time complexity analyzed. But, according to our experimental results based on the test models proposed, it is shown that the slowest one is the pairing heap that utilizes pointers and the fastest one is the traditional heap. For the two implicit heaps, these results are in contrary to the fact that the post-order heap is better than the traditional heap in time complexity analyzed.

배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘

정해재 한국정보처리학회 2006 정보처리학회논문지. 컴퓨터 및 통신시스템 Vol.13 No.3

스케줄링, 정렬, 및 최단 거리 계산 네트워크 문제 등과 같은 응용에 이용될 수 있는 우선 순위 큐 중, 피보나치 힙, 페어링 힙, 및 M-힙은 포인터를 이용하는 자료 구조이다. 본 논문에서는 [1]에서 문제점으로 남겨두었던 M-힙을 배열을 이용하여 표현한 MA-힙(M-heap with an array representation)를 제안한다. MA-힙은 M-힙과 동일한 시간 복잡도인 O(1) 삽입 전이 시간과 O(logn) 삭제 시간 복잡도를 가지며, 단순한 전통적인 힙에 근거하고 있기 때문에 [5]에서 제안된 힙보다 구현이 매우 용이하다. Priority queues can be used in applications such as scheduling, sorting, and shortest path network problem. Fibonacci heap, pairing heap, and M-heap are priority queues based on pointers. This paper proposes a modified M-heap with an array representation, called MA-heap, that resolves the problem mentioned in [1]. The MA-heap takes O(1) amortized time and O(logn) time to insert an element and delete the max/min element, respectively. These time complexities are the same as those of the M-heap. In addition, it is much easier to implement an MA-heap than a heap proposed in [5] since it is based on the simple traditional heap.

배열 표현을 이용한 M-힙에서 삽입/삭제 알고리즘

정해재,Jung Hae-Jae 한국정보처리학회 2006 정보처리학회논문지 A Vol.13 No.3

Priority queues can be used in applications such as scheduling, sorting, and shortest path network problem. Fibonacci heap, pairing heap, and M-heap are priority queues based on pointers. This paper proposes a modified M-heap with an way representation, called MA-heap, that resolves the problem mentioned in [1]. The MA-heap takes O(1) amortized time and O(logn) time to insert an element and delete the max/min element, respectively. These time complexities are the same as those of the M-heap. In addition, it is much easier to implement an MA-heap than a heap proposed in [5] since it is based on the simple traditional heap. 스케줄링, 정렬, 및 최단 거리 계산 네트워크 문제 등과 같은 응용에 이용될 수 있는 우선 순위 큐 중, 피보나치 힙, 페어링 힙, 및 M-힙은 포인터를 이용하는 자료 구조이다. 본 논문에서는 [1]에서 문제점으로 남겨두었던 M-힙을 배열을 이용하여 표현한 MA-힙(M-heap with an array representation)를 제안한다. MA-힙은 M-힙과 동일한 시간 복잡도인 O(1) 삽입 전이 시간과 O(logn) 삭제 시간 복잡도를 가지며, 단순한 전통적인 힙에 근거하고 있기 때문에 [5]에서 제안된 힙보다 구현이 매우 용이하다.