Overriding for efficiency Recall in Week 6 that we had an implementation of clear() in AbstractCollection that used the
Posted: Fri Jul 01, 2022 5:46 am
Overriding for efficiency Recall in Week 6 that we had animplementation of clear() in AbstractCollection that used theiterator and repeatedly called next() followed by remove() to wipeout the collection. This implementation was O(n). However, for thesake of efficiency, it was overridden in ArrayCollection with animplementation that just created a new empty array and set the sizeto zero. That implementation was O(1). [see the Week 6 code fordetails]
In the same manner, there are methods of AbstractList that haveworking implementations that are less efficient than they could beif direct access to the instance fields. What method(s) ofAbstractCollection and AbstractList should be overridden inArrayList in order to improve efficiency (i.e., what method(s)could execute faster if a different algorithm had direct access tothe instance fields)? Think about all the “slow” algorithms inAbstractList applied to array-based collections and thinkcreatively about how they could be made faster by doing fewer“shifts.” Justify your answer with a high-level algorithmicexplanation.
Hints: What is the impact of the iterator's remove method inArrayList being O(n) instead of O(1)? What is the impact of addingan element in the middle of the array being O(n) instead of O(1) atthe end? What if larger "gaps" were opened when adding to the arrayinstead of just a single element? What if we used "tombstones"(unique objects that replace a deleted item) to mark off elements-- as was done in AbstractCollection.equals() -- for deletion andthen the "gaps" were closed in one pass?
1. Method: _____ Current Big-O: ____ New algorithm (describe) :____ New Big-O: ____
In the same manner, there are methods of AbstractList that haveworking implementations that are less efficient than they could beif direct access to the instance fields. What method(s) ofAbstractCollection and AbstractList should be overridden inArrayList in order to improve efficiency (i.e., what method(s)could execute faster if a different algorithm had direct access tothe instance fields)? Think about all the “slow” algorithms inAbstractList applied to array-based collections and thinkcreatively about how they could be made faster by doing fewer“shifts.” Justify your answer with a high-level algorithmicexplanation.
Hints: What is the impact of the iterator's remove method inArrayList being O(n) instead of O(1)? What is the impact of addingan element in the middle of the array being O(n) instead of O(1) atthe end? What if larger "gaps" were opened when adding to the arrayinstead of just a single element? What if we used "tombstones"(unique objects that replace a deleted item) to mark off elements-- as was done in AbstractCollection.equals() -- for deletion andthen the "gaps" were closed in one pass?
1. Method: _____ Current Big-O: ____ New algorithm (describe) :____ New Big-O: ____