Aleksandr Maksymenko created COLLECTIONS-672:
------------------------------------------------
Summary: 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
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)
