Position/column mappings: using HashSet instead of ArrayList for better performances - Some better handling of integer boxing

[marcosalis]

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<Integer, Integer> 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.

[marcosalis]

Apologies for the multiple commits. I checked out the fork in a Windows machine and it showed 2000+ additions and deletions because of the different line return.

[maurycyw]

Hmm i agree performance will be better... "very expensive" is a little harsh haha, I hope users don't have lists that contain more than 1000's of views (plus should always prune when possible). I want to make sure the order does not matter then I will merge (for future purposes).

[lalith-b]

I think ArrayLists are faster than Hashsets/other collections in terms of adding/removing/modifying so its better to use an ArrayList.

[briangriffey]

ArrayLists are not necessarily faster regarding any of those operations. ArrayLists are only the fastest collection when their size is fixed and there's not any copy operations happening.

[marcosalis]

@maurycyw I agree in that "very expensive" was overstated. Anyway, I think that there might be a very decrease in the computation and, other than that, it's always good to use the proper data structure. @deathlord87, your statement is too generic to be true in all scenarios. It all depends on what's the operation you perform more often, how big your data is and on many other factors. In this case, the most common operation is checking for the existence of an element, which is much faster in an HashSet than in an ArrayList for the reasons I have already explained in my first post ;)

[pjtfernandes]

This edit worked wonders for the performance in my app. Thanks.

[marcosalis]

Glad to hear that!