[
https://issues.apache.org/jira/browse/COLLECTIONS-672?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Aleksandr Maksymenko updated COLLECTIONS-672:
---------------------------------------------
Description:
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?
was:
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?
> 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)
