This section includes two applications that demonstrate use of the ArrayList class. The method join() concatenates one ArrayList onto the end of another. We will develop join() and use it in a simple program. An ArrayList is useful when the amount of storage required is not know in advance. A particularly interesting example of this is the closet-pair program. Input any number of points in the plane and determine a pair of points that are closest together. We will conclude this section by developing an algorithm that solves the closest-pair problem and using it in an application.
Joining ArrayLists :
The concatenation of one string onto the end of another is the model for joining two ArrayList objects. The method join() takes two lists listA and listB as arguments. A loop scans the elements of listB and copies them onto the end of listA by using the add() method.
The algorithm begins by identifying the size of each ArrayList. A call to the method ensureCapacity() uses the sum of the two sizes as an argument. If ArrayList listA doesn't not have sufficient space to hold the incoming elements from listB, the operation makes a single allocation of new memory that contains the current elements in listA and space for the elements in listB. A simple loop scans the elements in listB and appends them to listA.
The Closest-Pair Problem :
The closest-pair problem requires finding the two closest points in a set of n points in the plane. Assume we specify each point using the standard Cartesian coordinate notation (x, y) and that the distance between two points Pi = (xi, yi) and Pj=(xj, yj) is :
A simple approach to the problem is to evaluate the distance between every pair of distinct points and determine the pair with the smallest distance. We do not want to determine the distance between the same pair of points twice. For instance d(P1, P8) = d(P8, P2). We avoid doing this by only considering pairs(Pi, Pj) where i
Our algorithm is similar to the selection sort algorithm that we discussed in Chapter 4. In a nested loop structure, we find the distance between P0 and the set of points {P1, P2, ... Pn-1}, keeping track of the minimum distance. We continue by computing the distance between P1 and the set of points {P2, P3, ... Pn-1}. In general, pass i of the algorithm computes the distances between Pi and the set of points {Pi+1, ... , Pn-1}. To optimize our algorithm's performance, we do not compute d(Pi, Pj) but compute d(Pi, Pj)^2. The square root takes additional time to compute and general cannot be computed exactly.
The method closestPair() implements the algorithm. Its arguments are ArrayList variables x and y containing the x-coordinate and the y-coordinate of the points. The method returns an array of two integers that contains the indices of the two closet points :
Analysis of the Closest-Pair Algorithm :
Pass 0 of the algorithm compares n-1 points, and pass 1 compares n-2 points. The total number of comparisons is :
(n-1) + (n-2) + ... + 1 = n(n-1)/2
The algorithm has running time O(n^2) ; in other words, it is quadratic. The technique we used is an example of a brute force algorithm. Brute force is a straightforward approach to solving a problem when we have something to search for or when we wish to optimize some property. It is usually based directly on the problem's statement. Normally, the technique enumerates all possible configurations of the input and picks the best of these enumerated configurations. There are important applications of the closest-pair problem. For instance, the algorithm will tell an air traffic controller which pair of n planes is closest during approach to the airport. For this reason, our brute algorithm is too slow. Actually there is a divide-and-conquer O(nlog2(n)) algorithm for the problem but it is too involved to discuss here.
沒有留言:
張貼留言