If we want to know which of two methods is faster, the most obvious approach is to time them. The TimeTest program (Figure 7-1) compares the `get()` methods from the ArrayList and LinkedList classes in the Java collections framework.

Lines 1416 of the method `test()` add many elements to `list`. We don't care what these elements are, so this is one of those rare occasions where it makes sense to create instances of the Object class.

To determine the time taken by line 18, we examine the clock before and after invoking `get()`. To get the current time, we invoke the static `currentTimeMillis()` method of the System class. For historical reasons involving the UNIX operating system, this is given as the number of milliseconds since midnight, January 1, 1970, Greenwich mean time. Because this is a very large number, the return type of `currentTimeMillis()` is long. A long is similar to an int, but its range is roughly ±1019.

Figure 7-1. The TimeTest class compares the `get()` methods of the ArrayList and LinkedList classes.

1 import java.util.*; 2 3 /** Time tests to compare performance of various algorithms. */ 4 public class TimeTest { 5 6 /** Number of Objects to store in each data structure. */ 7 public static final int LIST_LENGTH = 100; 8 9 /** 10 * Store LIST_LENGTH Objects in list. Time list's get() method, 11 * printing the number of milliseconds taken. 12 */ 13 public static void test(List list) { 14 for (int i = 0; i < LIST_LENGTH; i++) { 15 list.add(new Object()); 16 } 17 long before = System.currentTimeMillis(); 18 list.get(5); 19 long after = System.currentTimeMillis(); 20 System.out.println((after - before) + " milliseconds"); 21 } 22 23 /** Compare ArrayList with LinkedList. */ 24 public static void main(String[] args) { 25 System.out.print("ArrayList: "); 26 test(new ArrayList()); 27 System.out.print("LinkedList: "); 28 test(new LinkedList()); 29 } 30 31 } |

Unfortunately, running our program doesn't give us much information:

ArrayList: 0 milliseconds LinkedList: 0 milliseconds

Any modern computer is so fast that, on either of these data structures, the `get()` method takes less than one millisecond to run. A reasonable solution is to look at the time required to perform each operation a million times (Figure 7-2).

Figure 7-2. We can improve the resolution of our timing by performing the operation in question many times.

1 /** Number of times to perform the operation being timed. */ 2 public static final int TEST_RUNS = 1000000; 3 4 /** 5 * Store LIST_LENGTH Objects in list. Time list's get() method, 6 * printing the number of milliseconds taken. 7 */ 8 public static void test(List list) { 9 for (int i = 0; i < LIST_LENGTH; i++) { 10 list.add(new Object()); 11 } 12 long before = System.currentTimeMillis(); 13 for (int i = 0; i < TEST_RUNS; i++) { 14 list.get(5); 15 } 16 long after = System.currentTimeMillis(); 17 System.out.println((after - before) + " milliseconds"); 18 } |

The exact result of running this program varies from one run to the next. For example, one run might give

ArrayList: 21 milliseconds LinkedList: 39 milliseconds

while another might give

ArrayList: 22 milliseconds LinkedList: 40 milliseconds

This variation is due to a number of factors beyond our control, such as how Java manages its memory (Chapter 16) and what other programs are running on our machine. We could try harder to control these conditions and apply various statistical techniques to determine which method is faster, but the short answer is that the method from ArrayList is roughly twice as fast as the method from LinkedList. They are both very fast, so this is not a big difference.

The story is different if we get element 50 instead of element 5. Now the method from LinkedList takes vastly longer:

ArrayList: 22 milliseconds LinkedList: 226 milliseconds

In retrospect, this is not surprising. In an ArrayList, `get()` jumps right to the array element in question. In a LinkedList, it is necessary to traverse all of the previous list nodes to find the one we want. Our timing experiment provides empirical evidence that the time to get element i of a LinkedList increases with i, while the time to get element i of an ArrayList is independent of i. If we need a List and `get()` is going to be a very common operation, an ArrayList is a good choice.

We now have some evidence that LinkedList search time increases with i, but a couple of data points are not really a convincing case. Rather than perform a more extensive battery of tests, we can use some formal, mathematical tools to make statements about the efficiency of an algorithm. Section 7.2 introduces these tools.

The material that follows is important for designing general-purpose algorithms and data structures. Empirical timing is still important in optimization.

Exercises

7.1 |
The famous Y2K bug occurred because some old programs used two decimal digits to store years. This became a problem in the year 2000, because such programs had no way to tell whether "00" meant 1900 or 2000. A similar problem will occur for Java programs when the number of milliseconds since the beginning of 1970 exceeds the capacity of a long. In what year will this occur, given that the maximum value of a long is 9,223,372,036,854,775,807? What if |

Part I: Object-Oriented Programming

Encapsulation

Polymorphism

Inheritance

- Inheritance
- Extending a Class
- The Object Class
- Packages and Access Levels
- Summary
- Vocabulary
- Problems
- Projects

Part II: Linear Structures

Stacks and Queues

- Stacks and Queues
- The Stack Interface
- The Call Stack
- Exceptions
- The Queue Interface
- Summary
- Vocabulary
- Problems
- Projects

Array-Based Structures

- Array-Based Structures
- Shrinking and Stretching Arrays
- Implementing Stacks and Queues
- The List Interface
- Iterators
- The Java Collections Framework: A First Look
- Summary
- Vocabulary
- Problems
- Projects

Linked Structures

- Linked Structures
- List Nodes
- Stacks and Queues
- The LinkedList Class
- The Java Collections Framework Revisited
- Summary
- Vocabulary
- Problems
- Projects

Part III: Algorithms

Analysis of Algorithms

- Analysis of Algorithms
- Timing
- Asymptotic Notation
- Counting Steps
- Best, Worst, and Average Case
- Amortized Analysis
- Summary
- Vocabulary
- Problems
- Projects

Searching and Sorting

- Searching and Sorting
- Linear Search
- Binary Search
- Insertion Sort
- The Comparable Interface
- Sorting Linked Lists
- Summary
- Vocabulary
- Problems
- Projects

Recursion

- Recursion
- Thinking Recursively
- Analyzing Recursive Algorithms
- Merge Sort
- Quicksort
- Avoiding Recursion
- Summary
- Vocabulary
- Problems
- Projects

Part IV: Trees and Sets

Trees

Sets

- Sets
- The Set Interface
- Ordered Lists
- Binary Search Trees
- Hash Tables
- The Java Collections Framework Again
- Summary
- Vocabulary
- Problems
- Projects

Part V: Advanced Topics

Advanced Linear Structures

- Advanced Linear Structures
- Bit Vectors
- Sparse Arrays
- Contiguous Representation of Multidimensional Arrays
- Advanced Searching and Sorting
- Summary
- Vocabulary
- Problems
- Projects

Strings

Advanced Trees

- Advanced Trees
- Heaps
- Disjoint Set Clusters
- Digital Search Trees
- Red-Black Trees
- Summary
- Vocabulary
- Problems
- Projects

Graphs

- Graphs
- Terminology
- Representation
- Graph Traversal
- Topological Sorting
- Shortest Paths
- Minimum Spanning Trees
- Summary
- Vocabulary
- Problems
- Projects

Memory Management

Out to the Disk

- Out to the Disk
- Interacting with Files
- Compression
- External Sorting
- B-Trees
- Summary
- Vocabulary
- Problems
- Projects

Part VI: Appendices

A. Review of Java

- A. Review of Java
- A.1. The First Program
- A.2. Variables and Types
- A.3. Loops
- A.4. Interacting with the User
- A.5. Branching
- A.6. Methods and Breaking Out
- A.7. Constants
- A.8. Operators
- A.9. Debugging
- A.10. Coding Conventions

B. Unified Modeling Language

C. Summation Formulae

- C. Summation Formulae
- C.1. Sum Notation
- C.2. Sum of Constants
- C.3. Sum of First n Integers
- C.4. Sums of Halves and Doubles
- C.5. Upper Limit on Sum of a Function
- C.6. Constant Factors

D. Further Reading

Index

Data Structures and Algorithms in Java

ISBN: 0131469142

EAN: 2147483647

EAN: 2147483647

Year: 2004

Pages: 216

Pages: 216

Authors: Peter Drake

Flylib.com © 2008-2020.

If you may any questions please contact us: flylib@qtcs.net

If you may any questions please contact us: flylib@qtcs.net