Poor performance of StaticCluster#remove

[YegorKozlov]

NonHierarchicalDistanceBasedAlgorithm calls StaticCluster#remove when re-clustering candidates:

android-maps-utils/library/src/main/java/com/google/maps/android/clustering/algo/NonHierarchicalDistanceBasedAlgorithm.java

Line 212 in 862db8c

itemToCluster.get(clusterItem).remove(clusterItem.mClusterItem);

StaticCluster internally stores the items in a ArrayList

android-maps-utils/library/src/main/java/com/google/maps/android/clustering/algo/StaticCluster.java

Line 32 in 862db8c

private final List<T> mItems = new ArrayList<T>();

and the call of ArrayList#remove is O(N), i.e. every time we remove an item the list needs to iterate the elements until it finds the item. This results in poor performance on large data sets (100K+ points)

A low-hanging fix is to change the container from ArrayList to HashSet (or LinkedHashSet if ordering matters)

[googlemaps-bot]

🎉 This issue has been resolved in version 2.2.5 🎉

The release is available on:

• v2.2.5
• GitHub release

Your semantic-release bot 📦🚀