Browse Prior Art Database

Comparison of HEAPS and the TL Structure for the Simulation Event Set

IP.com Disclosure Number: IPCOM000128545D
Original Publication Date: 1977-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 2 page(s) / 14K

Publishing Venue

Software Patent Institute

Related People

W. R. Franta: AUTHOR [+4]

Abstract

In this paper we attempt to resolve the controversy of whether or not heaps subject might be the best physical realization of simulation event sets. Using a realistic experimental set-up we show that the TL structure is superior to the heap for this particular problem. Key Words and Phrases: simulation, event set,, heaps, TL structure CR Categories: 3.34, 4.22, 5.5, 8.1. Following publication of our paper [2], questions arose with respect to the superiority of the TL structure over heaps, particularly in the face of the remarks of Gonnet [3], concerning the use of heaps for the physical realization of the simulation event set. Gonnet's communication was in response to the Vaucher and Duval paper [5], and suggested the heap to be a more efficient structure than any proposed in [5'. As regards a comparison of heaps and the TL structure we can make the following remarks. 1. For the TL structure consecutive elements can be identified in o(1), for heaps o(n). (n denotes the number of notices in the set). Such identi- fication is necessary to support the scheduling constructs found in some extant languages, e.g., see [1]. .. 2. With the TL structure a FIFO or LIFO ordering is maintained automatically. For the heap a secondary field giving the event notice insertion time is necessary.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Comparison of HEAPS and the TL Structure for the Simulation Event Set

by

W. R. Franta and Kurt Maly

Computer Science Department

114 Lind Hall Institute of Technology University of Minnesota Minneapolis, Minnesota 55455 A Technical Report 77-19 November 1977 Cover design courtesy of Ruth and Jay Leavitt A Comparison of HEAPS and the TL Structure for the Simulation Event Set

by W.R. Franta and Kurt Maly

Abstract:

In this paper we attempt to resolve the controversy of whether or not heaps subject might be the best physical realization of simulation event sets. Using a realistic experimental set-up we show that the TL structure is superior to the heap for this particular problem.

Key Words and Phrases: simulation, event set,, heaps, TL structure CR Categories: 3.34, 4.22,
5.5, 8.1.

Following publication of our paper [2], questions arose with respect to the superiority of the TL structure over heaps, particularly in the face of the remarks of Gonnet [3], concerning the use of heaps for the physical realization of the simulation event set. Gonnet's communication was in response to the Vaucher and Duval paper [5], and suggested the heap to be a more efficient structure than any proposed in [5'. As regards a comparison of heaps and the TL structure we can make the following remarks.

1. For the TL structure consecutive elements can be identified in o(1), for heaps o(n). (n denotes the number of notices in the set). Such identi- fication is necessary to support the scheduling constructs found in some extant languages, e.g., see [1]. ..

2. With the TL structure a FIFO or LIFO ordering is maintained automatically. For the heap a secondary field giving the event notice insertion time is necessary.

3. Simple scheduling when the distribution of notices in the event set is uniform is o(1) for the heap, and o(1) for the TL structure (experimentally determined) and with the TL structure is nearly o(1) for all distribution...