Uploaded image for project: 'Commons Collections'
  1. Commons Collections
  2. COLLECTIONS-672

There are no List collection with optimized indexOf method.

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Open
    • Priority: Major
    • Resolution: Unresolved
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Collection
    • Labels:
      None

      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?

        Attachments

          Activity

            People

            • Assignee:
              Unassigned
              Reporter:
              masyamandev Aleksandr Maksymenko
            • Votes:
              2 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated: