Transcript O(n)

CSE 143
Lecture 21
Iterators
slides created by Alyssa Harding
http://www.cs.washington.edu/143/
AbstractIntList review
• Recall our AbstractIntList class
public abstract class AbstractIntList
implements IntList {
public abstract int indexOf(int value);
public boolean contains(int value)
return indexOf(value) >= 0;
}
...
It contains both methods with bodies
and abstract methods
}
2
AbstractIntList review
• Now let’s examine the complexity of some of the methods
• Recall that time complexity refers to the growth rate
of how long code takes as the input size increases
• O(1): no matter how much input there is,
we only have to do one step
• O(n): if there is n amount of input,
we’ll have to do n steps
3
isEmpty() complexity
• What’s the complexity of isEmpty() for ArrayIntList?
public boolean isEmpty()
return size() == 0;
}
• Its size() method returns the size field
• This is O(1)
4
isEmpty() complexity
• What’s the complexity of isEmpty() for LinkedIntList?
public boolean isEmpty()
return size() == 0;
}
• Its size() method loops through all the
nodes to calculate the size
• This is O(n)
5
contains() complexity
• What’s the complexity of contains() for ArrayIntList?
public abstract int indexOf(int value);
public boolean contains(int value)
return indexOf(value) >= 0;
}
• contains() calls indexOf(), which looks at every value
• This is O(n)
6
contains() complexity
• What’s the complexity of contains() for LinkedIntList?
public abstract int indexOf(int value);
public boolean contains(int value)
return indexOf(value) >= 0;
}
• contains() calls indexOf(), which looks at every value
• This is O(n)
7
equals() complexity
• What’s the complexity of equals() for ArrayIntList?
public boolean equals(Object other) {
if ( other instanceof IntList ) {
IntList otherList = (IntList)other;
if ( this.size() == otherList.size() ) {
for (int i = 0; i < this.size(); i++) {
if ( this.get(i) != otherList.get(i) )
return false;
}
return true;
}
The most repeated line of code is getting a
return false; value from the list, so this is our most
significant line
}
}
8
equals() complexity
• What’s the complexity of equals() for ArrayIntList?
• If there are n values, we’ll loop through n times
– This is O(n)
• For each value, we get the value from the array
– This is O(1)
• Overall, this is O(n) * O(1) = O(n)
9
equals() complexity
• What’s the complexity of equals() for LinkedIntList?
• If there are n values, we’ll loop through n times
– This is O(n)
• For each value, we get the value by looping through
the nodes in the list
– This is O(n)
• Overall, this is O(n) * O(n) = O(n2)
10
Complexity comparison
method
isEmpty()
ArrayIntList
O(1)
contains() O(n)
equals()
O(n)
LinkedIntList
O(n)
O(n)
O(n2)
• Ouch!
• Our code worked pretty well for ArrayIntList,
but not LinkedIntList
• Can we both reduce redundancy and maintain efficiency?
11
Iterator<E>
• Java gives us an Iterator<E> that we can
use to loop through the values in a collection
– http://java.sun.com/javase/6/docs/api/java/util/Iterator.html
public interface Iterator<E> {
// returns true if another value exists
public boolean hasNext();
// returns the next value in the collection
public E next();
// removes the current value
public void remove();
}
12
Iterable<E> interface
• Java also gives us a way of letting it know that
a collection can be iterated over
– http://java.sun.com/javase/6/docs/api/java/lang/Iterable.html
public interface Iterable<E> {
public Iterator<E> iterator();
}
13
Iterable<E> interface
• Any class that implements this interface must
have an iterator
public interface IntList extends
Iterable<Integer> {
...
}
14
Iterable<E> interface
• First we’d need to write iterators for
ArrayIntList and LinkedIntList
• What would we need to keep track of for
the ArrayIntList iterator?
– the index we’re examining
• How fast would it be to look at the next value?
– We just increment the index
– O(1)
15
Iterable<E> interface
• First we’d need to write iterators for
ArrayIntList and LinkedIntList
• What would we need to keep track of for
the LinkedIntList iterator?
– the node that we’re examining
• How fast would it be to look at the next value?
– We just increment the index
– O(1)
16
Iterator example
• Now we can use an iterator to loop through our list:
IntList list1 = new ArrayIntList();
list1.add(7);
list1.add(42);
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
17
Iterator example
• Now we can also use a foreach loop with any class
that is Iterable:
foreach (int i : list)
System.out.println(i);
• This accomplishes the same thing as the previous slide,
but looks much cleaner
18
indexOf()
• Now we can use iterators for indexOf()
for any AbstractIntList
public int indexOf(int value) {
Iterator<Integer> it = iterator();
int i = 0;
while ( it.hasNext() ) {
if ( it.next() == value )
return i;
}
return -1;
}
19
isEmpty()
• Instead of calculating the entire size, we can check
whether our list has any elements
public boolean isEmpty()
return !iterator().hasNext();
}
20
equals()
• The next method is more complex:
public boolean equals(Object other) {
if ( other instanceof IntList ) {
Iterator<Integer> it1 = this.iterator();
Iterator<Integer> it2 =
(IntList)other.iterator();
while ( it1.hasNext() && it2.hasNext() ) {
if ( it1.next() != it2.next() )
return false;
}
return !it1.hasNext() && !it2.hasNext();
}
}
return false;
21
Complexity revisited
method
isEmpty()
ArrayIntList
O(1)
contains() O(n)
equals()
O(n)
LinkedIntList
O(1)
O(n)
O(n)
• Now they’re the same!
22