[ https://issues.apache.org/jira/browse/COLLECTIONS-672?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Aleksandr Maksymenko updated COLLECTIONS-672: --------------------------------------------- Priority: Major (was: Minor) > There are no List collestion with optimized indexOf method. > ----------------------------------------------------------- > > Key: COLLECTIONS-672 > URL: https://issues.apache.org/jira/browse/COLLECTIONS-672 > Project: Commons Collections > Issue Type: Improvement > Components: Collection > Reporter: Aleksandr Maksymenko > Priority: Major > > All known implementations of List are all have O(n) for indexOf() operation. > Here is my implementation of such List on github which has O(log n) for > indexOf() and contains(): > [https://github.com/masyamandev/indexable-set] > There are two modifications: one implements both List and Set, so it can > contains unique elements, second modification can contains any amount of > unique objects, but it's a bit slower. > It's based on TreeList and provide complexity: > * get by index is O(log n) > * insertion, removing (both by index or by value) are O((log n) * (1 + log > m)) where is amount of elements equals to inserted/removed element. > * insertion, removing are O(log n) if all elements are unique. > * indexOf and lastIndexOf are O(log n). > * contains is O(1) or (log n) depending on Map implementation. > As those collections have complexity similar to TreeSet (at least in cases of > unique elements), overall performance is 20-30% slower due to element > indexing and eliminating some optimizations. However it provides fast indexOf > and contains. > Can I help in porting my code to Apache common Collections library? -- This message was sent by Atlassian JIRA (v7.6.3#76005)