Today we look at chained traversal of a collection, searching a collection for a particular element, and computational complexity.
The Portfolio
class supports indexed access of
the elements it holds:
// Portfolio with capacity 3 Portfolio pf = new Portfolio("My Portfolio", 3); Investment inv0 = new Investment( new Stock("HR.A"), 1, 1.00 ); Investment inv1 = new Investment( new Stock("HR.B"), 1, 2.00 ); Investment inv2 = new Investment( new Stock("HR.C"), 1, 3.00 ); pf.add(inv0); pf.add(inv1); pf.add(inv2); Investment inv = pf.get(1); output.println(inv);
To iterate over the investments, the client writes a loop that
counts from 0
to the size - 1:
for (int i = 0; i < pf.size(); i++) { Investment inv = pf.get(i); // do something with the investment here ... }
import java.io.PrintStream; import type.lib.Investment; import type.lib.Stock; import type.lib.Portfolio; public class Collections5 { public static void main(String[] args) { PrintStream output = System.out; Portfolio pf = new Portfolio("My Portfolio", 3); Investment inv0 = new Investment( new Stock("HR.A"), 1, 1.00 ); Investment inv1 = new Investment( new Stock("HR.B"), 1, 2.00 ); Investment inv2 = new Investment( new Stock("HR.C"), 1, 3.00 ); pf.add(inv0); pf.add(inv1); pf.add(inv2); for (int i = 0; i < pf.size(); i++) { Investment inv = pf.get(i); output.println(inv); } } }
Some collections provide chained traversal instead of indexed traversal. In chained traversal, the client gets the first element in the collection, and then the next, and then the next, and so on until there are no more elements.
The traversal order depends on the implementation details of the collection. Some collections will traverse the elements in a "natural" (sorted) order, whereas other collections will traverse the elements in some order not meaningful to the client. All that is guaranteed is that the traversal visits every element, and each element is visitied only once.
Both Portfolio
and GlobalCredit
support chained traversal. To perform a chained traversal,
the client writes a loop:
// make a portfolio filled with random investments
Portfolio pf = Portfolio.getRandom();
final int PERCENT = 100;
for (Investment i = pf.getFirst();
i != null;
i = pf.getNext())
{
double bookValue = i.getQty() * i.getBookValue();
Stock s = i.getStock();
double currValue = i.getQty() * s.getPrice();
double yield =
(currValue - bookValue) / bookValue * PERCENT;
output.printf("yield for %s is %.2f%%%n",
s.getName(), yield);
}
If getFirst
returns null
, the
collection is empty and the loop will be skipped. Otherwise,
the loop visits one investment per iteration until
getNext
returns null
.
import java.io.PrintStream; import type.lib.Investment; import type.lib.Stock; import type.lib.Portfolio; public class Collections6 { public static void main(String[] args) { PrintStream output = System.out; // make a portfolio filled with random investments Portfolio pf = Portfolio.getRandom(); final int PERCENT = 100; for (Investment i = pf.getFirst(); i != null; i = pf.getNext()) { double bookValue = i.getQty() * i.getBookValue(); Stock s = i.getStock(); double currValue = i.getQty() * s.getPrice(); double yield = (currValue - bookValue) / bookValue * PERCENT; output.printf("yield for %s is %.2f%%%n", s.getName(), yield); } } }
Once you have a collection of things it becomes a very frequent occurrence that you want to find a particular element of the collection. For example, you might want to search for:
In one type of search, you are only interested whether or
not the element is in the collection (you don't need a
reference to the element). This type of search returns a
boolean value (true
if the element is in the
collection, and false
otherwise).
A second type of search, you want the reference to the
searched for element. This type of search returns a
reference to an object if the element is in the collection,
and null
otherwise.
Both kinds of search can be solved using traversal. By
visiting every element in the collection you can determine
if a particular element is in the collection using
equals
and a boolean variable.
The following loop incorrectly searches for an investment of a particular stock in a portfolio:
Portfolio pf = Porfolio.getRandom(); // the stock to search for Stock st = new Stock(".MP"); boolean found = false; for (Investment i = pf.getFirst(); i != null; i = pf.getNext()) { found = i.getStock().equals(st); }
The above loop uses traversal to visit every investment
in the portfolio.
The problem with the loop is that the value of found
is determined by the last investment visited in the traversal.
To correct the loop, we need to stop the loop when
found
becomes true
; that is,
we want the loop to run whenever the investment is
not null
AND found
is false
:
// the stock to search for
Stock st = new Stock(".MP");
boolean found = false;
for (Investment i = pf.getFirst();
i != null && !found;
i = pf.getNext())
{
found = i.getStock().equals(st);
}
!found
(NOT found) is equivalent to
found == false
.
When a reference to the searched for object is needed, you use the exact same approach except you also need a reference variable to hold the reference to the searched for object:
boolean found = false; Investment inv = null; for (Investment i = pf.getFirst(); i != null && !found; i = pf.getNext()) { found = i.getStock().equals(st); if (found) { inv = i; } } if (found) { output.printf("you have %d shares of %s%n", inv.getQty(), st.getName()); } else { output.printf("you have no investments in %s%n", st.getName()); }
import java.io.PrintStream; import type.lib.Investment; import type.lib.Stock; import type.lib.Portfolio; /* WARNING: You might have to run this program many times before it generates a random portfolio with an .MP stock investment. */ public class Collections7 { public static void main(String[] args) { PrintStream output = System.out; // make a portfolio filled with random investments Portfolio pf = Portfolio.getRandom(); // the stock to search for Stock st = new Stock(".MP"); boolean found = false; Investment inv = null; for (Investment i = pf.getFirst(); i != null && !found; i = pf.getNext()) { found = i.getStock().equals(st); if (found) { inv = i; } } if (found) { output.printf("you have %d shares of %s%n", inv.getQty(), st.getName()); } else { output.printf("you have no investments in %s%n", st.getName()); } } }
The previous two types of search stopped after we found the first element that satisified the search criteria. Another kind of search looks for all of the elements that satisfy the search criteria. For example, we might want to count all investments in a portfolio where the stock name begins with a letter in the range [A-M]:
final String SPLIT = "N"; int num = 0; boolean found = false; for (Investment i = pf.getFirst(); i != null; i = pf.getNext()) { String namei = i.getStock().getName(); if (SPLIT.compareToIgnoreCase(namei) > 0) { num++; } } output.println(num);
Computational complexity is a branch of theoretical computer science
concerned with classifying computational problems based on their
difficulty. One measure of difficulty is the worst-case complexity:
how many basic operations are required to solve a problem of size
N
where N
is a large number.
For search of a collection, N
is the size of the
collection. In the worst case, you have to visit all N
elements in the collection. We say that the complexity of
exhaustive search is O(N
).
O(N
) is pronounced "big-O of N" or "order of N".
Suppose you wanted to output the investments in a portfolio in order from the smallest total current value to the highest total current value. A simple algorithm that can perform this sorting is called selection sort.
1. find the investment with the smallest current value output it and remove it from the portfolio 2. repeat step 1 3. continue repeating step 1 until the portfolio is empty
What is the worst-case complexity of step 1? What is the worst-case complexity of the entire algorithm?