I am using a TreeMap<Integer, Integer> to represent a sorted list which can have duplicate elements. The key corresponds to an arbitrary value in the list and the mapped value corresponds to the number of occurrences. I am using a sorted list concept because I need to efficiently operate over sublists (log n time) and I am using a TreeMap because Java doesn't have any default sorted list implementation.
However, I noticed that the performance of my algorithm was slower than expected, so after doing some research, it appears that the subMap method takes O(log n k) time, where n is the size of the map and k is the number of elements within the sub map. For large values of k relative to n, this approaches linear time.
How can I operate over submaps (sublists) in sublinear time; or alternatively, is there a better way I can represent a sorted list in Java?
The motivation behind this question: imagining the tree map as a binary search tree, I'd like to find the first node of some subtree, then use that as the entire tree itself, effectively removing the rest of the tree. Ideally this would only take O(log n) time.
CodePudding user response：
Google's Guava library has an extensive suite of collection classes that complement the ones in the standard library nicely.
Guava is a set of core Java libraries from Google that includes new collection types (such as multimap and multiset), immutable collections, a graph library, and utilities for concurrency, I/O, hashing, caching, primitives, strings, and more! It is widely used on most Java projects within Google, and widely used by many other companies as well.
You might like their SortedMultiset interface for collections that maintain elements in a sorted order and allow for duplicates. Implementations include: