Browse Prior Art Database

ON THE EFFICIENCY OF SOME LIST MARKING ALGORITHMS

IP.com Disclosure Number: IPCOM000128705D
Original Publication Date: 1976-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 7 page(s) / 30K

Publishing Venue

Software Patent Institute

Related People

J. L. Baer: AUTHOR [+4]

Abstract

On the Efficiency of Some List Marking Algorithms J. L. Baer and M. 'Fries Four algorithms for making LISP-like lists are compared in terms of storage and run time-efficiency. The methodology used in the comparisons involves both theoretical considerations yielding orders of magnitude, and high-level language analyses which provide predictions of performance. It is shown that Schorr and Waite's linear algorithm [5] has the best composite performance when the nodes' structure permits the inclusion of an extra bit. Otherwise the bit stack algorithm is a good solution. This paper also gives more credibility to the possibility of comparing closely related algorithms through descriptive notations which are language and machine independent.

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

ON THE EFFICIENCY OF SOME LIST MARKING ALGORITHMS

by J. L. Baer and M. Fries #76-08-08

Department of Computer Science University of Washington Seattle, Washington 98195

ABSTRACT

On the Efficiency of Some List Marking Algorithms J. L. Baer and M. 'Fries

Four algorithms for making LISP-like lists are compared in terms of storage and run time- efficiency. The methodology used in the comparisons involves both theoretical considerations yielding orders of magnitude, and high-level language analyses which provide predictions of performance. It is shown that Schorr and Waite's linear algorithm [5] has the best composite performance when the nodes' structure permits the inclusion of an extra bit. Otherwise the bit stack algorithm is a good solution. This paper also gives more credibility to the possibility of comparing closely related algorithms through descriptive notations which are language and machine independent.

Introduction

In recent years, we have seen an increasing amount of research in the evaluation of performance of software. On the theoretical side, the analysis of worst and average behaviors of algorithms has developed into a fruitful field, yielding important results such as optimal or near- optimal algorithms, lower and upper bounds on running time, and new data structures. At the other extreme, measure- ments through hardware and/or software monitors have helped in discovering the bottlenecks in programs which are not amenable to mathematical analysis.. While the theoretical approach tends to give orders of magnitude, e.g. a balanced tree search takes an average of 0(logn) comparisonsl, the experimental one might be biased by implementation considerations such as the selections of the source language and of the host machine. There is a need in finding some metrics between these two approaches, mostly when one wants to choose between algorithms which have the same theoretical behavior and when we want the comparison to stand independently of the implementation. Knuth's solution [3] to this problem is to code all algorithms in an assembly language of his own design and to count the (expected) number of instructions

This work was supported in part by NSF Grant GJ-41164.

Current address - Boeing Company, Seattle, Wa.

In this paper all logarithms are taken base 2. We say that g(n) is of order f(n), written O(f(n)) if there exists a constant c such that g(n) cf(n) for all but a finite set of values of n. which are going to be executed. Although this method has the advantage of being machine-independent, we feel that the flavor of the algorithms might be lost and that too much "optimization" is left to the programmer. Our approach is based on an analysis of the code at the source level. It has been proven successful for a comparison of tree-balancing algorithms [1], whereupon algorithms were analyzed using implementation-free concepts. This methodology yielded accep...