Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

NOT (Faster Implementation ==>Better Algorithm), A Case Study

Published

Author(s)

Stephen B. Balakirsky, Thomas R. Kramer

Abstract

Given two algorithms that perform the same task, one may ask which is better. One simple answer is that the algorithm that delivers the ?best? answer is the better algorithm. But what if both algorithms deliver results of similar quality? In this case, a common metric that is utilized to differentiate between the two algorithms is the time to find a solution. Measurements, however, must be performed using an implementation of an algorithm (not an abstract algorithm) and must be taken using specific test data. Because the effects of implementation quality and test data selection may be large, the measured time metric is an insufficient measure of algorithm performance and quality. In this paper we present the specific case of several different implementations of the same Dijkstra graph search algorithm applied to graphs with various branching factors. Our experimental results show that quality rankings based on time may be heavily influenced by the choice of operational scenario and code quality. In addition, we explore possible alternative ranking schemes for the specific case of Dijkstra graph search algorithms.
Proceedings Title
Proceedings of the Performance Metrics for Intelligent Systems (PerMIS) Workshop
Conference Dates
August 16-18, 2003
Conference Location
Gaithersburg, MD
Conference Title
Performance Metrics for Intelligent Systems (PerMIS) Workshop

Keywords

algorithm performance, autonomous systems, performance metric, planning systems, Robotics & Intelligent Systems, Software Engineering, Standards

Citation

Balakirsky, S. and Kramer, T. (2003), NOT (Faster Implementation ==>Better Algorithm), A Case Study, Proceedings of the Performance Metrics for Intelligent Systems (PerMIS) Workshop, Gaithersburg, MD, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=822567 (Accessed April 21, 2024)
Created August 18, 2003, Updated February 17, 2017