Data Structures
As the various Fibonacci implementations demonstrated, good algorithms and good data structures are keys to a fast application. Android and Java define many data structures you should have good knowledge of to be able to quickly select the right ones for the right job. Consider choosing the appropriate data structures one of your highest priorities.
The most common data structures from the java.util package are shown in Figure 1.1.
To those data structures Android adds a few of its own, usually to solve or improve performance of common problems.
- LruCache
- SparseArray
- SparseBooleanArray
- SparseIntArray
- Pair
NOTE: Java also defines the Arrays and Collections classes. These two classes contain only static methods, which operate on arrays and collections respectively . For example, use Arrays.sort to sort an array and Arrays.binarySearch to search for a value in a sorted array.
Figure 1-1. Data structures in the java.util package
While one of the Fibonacci implementations used a cache internally (based on a sparse array), that cache was only temporary and was becoming eligible for garbage collection immediately after the end result was computed. It is possible to also use an LruCache to save end results, as shown in Listing 1–13.
Listing 1–13. Using an LruCache to Remember Fibonacci Terms
int maxSize = 4 * 8 * 1024 * 1024; // 32 megabits
LruCache<Integer, BigInteger> cache = new LruCache<Integer, BigInteger> (maxSize) {
protected int sizeOf (Integer key, BigInteger value) {
return value.bitLength(); // close approximation of object's size, in bits
}
};
…
int n = 100;
BigInteger fN = cache.get(n);
if (fN == null) {
fN = Fibonacci. computeRecursivelyWithCache(n);
cache.put(n, fN);
}
Whenever you need to select a data structure to solve a problem, you should be able to narrow down your choice to only a few classes since each class is usually optimized for a specific purpose or provides a specific service. For example, choose ArrayList over Vector if you don't need the operations to be synchronized. Of course, you may always create your own data structure class, either from scratch (extending Object) or extending an existing one.
NOTE: Can you explain why LruCache is not a good choice for computeRecursivelyWithCache's internal cache as seen in Listing 1–11?
If you use one of the data structures that rely on hashing (e.g. HashMap) and the keys are of a type you created, make sure you override the equal and hashCode methods. A poor implementation of hashCode can easily nullify the benefits of using hashing.
TIP: Refer to http://d.android.com/reference/java/lang/Object.html for a good example of an implementation of hashCode().
Even though it is often not natural for many embedded application developers, don't hesitate to consider converting one data structure into another in various parts of your application: in some cases, the performance increase can easily outweigh the conversion overhead as better algorithms can be applied. A common example is the conversion of a collection to an array, possibly sorted. Such a conversion would obviously require memory as a new object needs to be created. On memory-constrained devices, such allocation may not always be possible, resulting in an OutOfMemoryError exception. The Java Language Specification says two things:
- The class
Errorand its subclasses are exceptions from which ordinary programs are not ordinarily expected to recover. - Sophisticated programs may wish to catch and attempt to recover from Error exceptions.
If your memory allocation is only part of an optimization and you, as a sophisticated application developer, can provide a fallback mechanism (for example, an algorithm, albeit slower, using the original data structure) then catching the OutOfMemoryError exception can make sense as it allows you to target more devices. Such optional optimizations make your code harder to maintain but give you a greater reach.
NOTE: Counterintuitively, not all exceptions are subclasses of Exception. All exceptions are subclasses of Throwable (from which Exception and Error are the only direct subclasses).
In general, you should have very good knowledge of the java.util and android.util packages since they are the toolbox virtually all components rely on. Whenever a new Android version is released, you should pay special attention to the modifications in these packages (added classes, changed classes) and refer to the API Differences Report on http://d.android.com/sdk. More data structures are discussed in java.util.concurrent, and they will be covered in Chapter 5.