commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Aleksandr Maksymenko (JIRA)" <>
Subject [jira] [Created] (COLLECTIONS-672) There are no List collestion with optimized indexOf method.
Date Sun, 28 Jan 2018 13:47:00 GMT
Aleksandr Maksymenko created COLLECTIONS-672:

             Summary: There are no List collestion with optimized indexOf method.
                 Key: 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():

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

View raw message