maurycyw/StaggeredGridView — pull request #63 by marcosalis (2013-10-22 18:20:07+00:00)
Title: Position/column mappings: using HashSet instead of ArrayList for better performances - Some better handling of integer boxing

The class was using an ArrayList of ArrayList of Integers to simply map the column where an item was placed.
This solution is overly complicated and poor in performances, especially when the adapter holds hundreds (or more) items: some of the operations (contains() and remove() in particular) called on the ArrayList(s) containing the positions for a single column in fillUp() and fillDown() have a O(n) complexity. That required traversing the array multiple times for each position, which is a very expensive operation in a cpu-bound context (= user scrolling or flinging the list).

Since we don't need ordering in the columns mapping, I just replaced the internal ArrayList with an HashSet, whose complexity is O(1) for the same operations. We could have done even better with a HashMap or a SparseIntArray but the performance optimizations are not enough to justify drastically modifying the save/restore state code for the purpose of my pull request (SparseIntArray is not even parcelable or serializable).

I've also made a small optimization to avoid using multiple autoboxing for the same int value when iterating through the columns values.