Chapter 3. Need for speed: Time efficiency
This chapter covers
- Comparing the performance of common data structures, including lists, sets, and trees
- Evaluating worst-case performance and average long-run performance of a given data structure
- Focusing the computational load on a specific method of a class, or spreading it on all methods
Achieving the maximum possible speed for a given computational task has fascinated programmers since the ancient times of punch-card programming. Indeed, you might say that a large part of computer science itself was born to satisfy this urge. In this chapter, I’ll present three different container implementations that optimize speed in different ways. Why three? Can’t I just present you with the best one? The thing is, there is no single best version, and that’s one of the main takeaways from this chapter.
Basic programming classes and even introductory computer science curricula overlook this fact. The latter deal extensively with time efficiency, particularly in algorithm and data structure classes. Those classes and their textbooks focus on one problem at a time, be it visiting a graph or balancing a tree. When you consider a single algorithmic problem, with given inputs and desired outputs, you can compare any two algorithms for performance. You may find that the fastest possible procedure is the one with the least asymptotic worst-case time complexity. This is indeed how research makes progress on single computational questions.