Sparse arraysAbout sparse arraysSparse arrays as linked listsA sparse array ADTImplementing the operationsTime analysisWhat is the problem?Example: Finding the maximumProblems with this approachFixing the ADTInterfacesImplementing an interfaceCode for SparseArrayIteratorExample, revisitedNot quite there yet...IndexIteratorCode for IndexIteratorWrapping the SparseArray classCode for SparseDoubleArrayPractical considerationsSparse two-dimensional arraysAnother implementationYet another implementationConsiderationsLooking up an itemA sparse 2D array ADTOne final implementationSummaryThe EndJan 14, 2019Sparse arrays2About sparse arraysA sparse array is simply an array most of whose entries are zero (or null, or some other default value)For example: Suppose you wanted a 2-dimensional array of course grades, whose rows are Penn students and whose columns are coursesThere are about 22,000 studentsThere are about 5000 coursesThis array would have about 110,000,000 entriesSince most students take fewer than 5000 courses, there will be a lot of empty spaces in this arrayThis is a big array, even by modern standardsThere are ways to represent sparse arrays efficiently3Sparse arrays as linked listsWe will start with sparse one-dimensional arrays, which are simplerWe’ll do sparse two-dimensional arrays laterHere is an example of a sparse one-dimensional array:Here is how it could be represented as a linked list:0 0 0 0 17 0 0 23 14 0 0 00 1 2 3 4 5 6 7 8 9 10 11ary4 17 7 23 8 14ary4A sparse array ADTFor a one-dimensional array of Objects, you would need:A constructor: SparseArray(int length)A way to get values from the array: Object fetch(int index)A way to store values in the array: void store(int index, Object value)Note that it is OK to ask for a value from an “empty” array positionFor an array of numbers, this should return zeroFor an array of Objects, this should return nullAdditional useful operations:int length() : return the size of the arrayint elementCount() : how many non-null values are in the arrayAre there any important operations we have forgotten?5Implementing the operationsclass List { int index; // the row number Object value; // the actual data List next; // the "pointer" public Object fetch(int index) { List current = this; // first "List" (node) in the list do { if (index == current.index) { return current.value; // found correct location } current = current.next; } while (index < current.index && next != null); return null; // if we get here, it wasn't in the list}}The store operation is basically the same, with the extra complication that we may need to insert a node into the list6Time analysisWe must search a linked list for a given indexWe can keep the elements in order by indexExpected time for both fetch and store is 1/2 the number of (nonzero/nonnull) elements in the listThat is, O(n), where n is the number of actual (non-default) elementsFor a “normal” array, indexing takes constant timeBut for a sparse array, this isn’t badThis is a typical example of a time-space tradeoff--in order to use less of one (space), we need to use more of the other (time)Expected time for the secondary methods, length and elementCount, is just O(1), that is, constant timeWe’re done, right?Unfortunately, this analysis is correct but misleading7What is the problem?True fact: In an ordinary array, indexing to find an element is the only operation we really needTrue fact: In a sparse array, we can do indexing reasonably quickly False conclusion: In a sparse array, indexing to find an element is the only operation we really needThe problem is that in designing the ADT, we didn’t think enough about how it would be used8Example: Finding the maximumTo find the maximum element in a normal array:double max = array[0];for (int i = 0; i < array.length; i++) { if (array[i] > max) max = array[i];}To find the maximum element in a sparse array:Double max = (Double) array.fetch(0);for (int i = 0; i < array.length(); i++) { Double temp = (Double) array.fetch(i); if (temp.compareTo(max) > 0) { max = temp; }}Do you see any problems with this?9Problems with this approachSince we tried to be general, we defined our sparse array to hold ObjectsThis means a lot of wrapping and casting, which is awkwardWe can deal with this (especially if we use Java 1.5)More importantly, in a normal array, every element is relevantIf a sparse array is 1% full, 99% of its elements will be zeroThis is 100 times as many elements as we should need to examineOur search time is based on the size of the sparse array, not on the number of elements that are actually in itAnd it’s a big array (else we wouldn’t bother using a sparse array)10Fixing the ADTAlthough “stepping through an array” is not a fundamental operation on an array, it is one we do frequentlyIdiom: for (int i = 0; i < array.length; i++) {...}This is a very expensive thing to do with a sparse arrayThis shouldn’t be so expensive: We have a list, and all we need to do is step through itPoor solution: Let the user step through the listThe user should not need to know anything about implementationWe cannot trust the user not to screw up the sparse arrayThese arguments are valid even if the user is also the implementer!Correct solution: Expand the ADT by adding operationsBut what, exactly, should these operations be?Java has an answer, and it is the answer we should use11InterfacesAn interface, in Java, is like a class, butIt contains only public methods (and maybe some final values)It only declares methods; it doesn’t define themExample:public interface Iterator { // Notice: no method bodies public boolean hasNext( ); public Object next( ); public void remove( );}This is an interface that is defined for you, in java.util“Stepping through all the values” is something that you want to do for many data structures, so Java defines a standard way to do itYou can write your own interfaces, using the above syntaxSo, how do you use this interface?12Implementing an interfaceTo use an interface, you say you are going to implement it, then you define every method in itExample: public class SparseArrayIterator implements Iterator { // any data you
View Full Document
Unlocking...