An efficient data structure for the simulation event set

ABSTRACT

Recently algorithms have been presented for the realization of event scheduling routines suitable for general purpose discrete event simulation systems. Several exhibited a performance superior to that of commonly used simple linked list algorithms. In this paper a new event scheduling algorithm is presented which improves on two aspects of the best of the previously published algorithms. First, the new algorithm's performance is quite insensitive to skewed distributions, and second, its worst-case complexity is O(√n), where n is the number of events in the set. Furthermore, tests conducted to estimate the average complexity showed it to be nearly independent of n.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Franta, W.R., and Maly, K. An event scanning algorithm of nearly constant complexity. Tech. Rep. 75-18, Univ. of Minnesota, Minneapolis, Minn. Nov. 1975.
• 3: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 4: Jean G. Vaucher , Pierre Duval, A comparison of simulation event list algorithms, Communications of the ACM, v.18 n.4, p.223-230, April 1975 [doi>10.1145/360715.360758]
• 5: F. Paul Wyman, Improved event-scanning mechanisms for discrete event simulation, Communications of the ACM, v.18 n.6, p.350-353, June 1975 [doi>10.1145/360825.360873]

INDEX TERMS

Keywords:
event scanning mechanisms, multilinked lists, simulation, time flow mechanisms