commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bugzi...@apache.org
Subject DO NOT REPLY [Bug 26680] New: - Implementation of List with an AVLTree (TreeList)
Date Thu, 05 Feb 2004 10:33:58 GMT
DO NOT REPLY TO THIS EMAIL, BUT PLEASE POST YOUR BUG 
RELATED COMMENTS THROUGH THE WEB INTERFACE AVAILABLE AT
<http://nagoya.apache.org/bugzilla/show_bug.cgi?id=26680>.
ANY REPLY MADE TO THIS MESSAGE WILL NOT BE COLLECTED AND 
INSERTED IN THE BUG DATABASE.

http://nagoya.apache.org/bugzilla/show_bug.cgi?id=26680

Implementation of List with an AVLTree (TreeList)

           Summary: Implementation of List with an AVLTree (TreeList)
           Product: Commons
           Version: unspecified
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: Enhancement
          Priority: Other
         Component: Collections
        AssignedTo: commons-dev@jakarta.apache.org
        ReportedBy: js@ekkono.com


The existing Java List implementations are rather slow if it comes to big lists 
and insertions and/or random access.  To mitigate that this List is based on an 
AVL-Tree and uses offsets to locate objects.  The following benchmarks show the 
performance compared to LinkedList and ArrayList.

          add     insert    get
TreeList  300     501       110
ArrayList  70   20390        20
LinkedList 50  226636    279742

add - 100K times add( new Object() )
insert - 100k times add( random() * 100K, new Object() ) on a List with 100K 
elements.
get - 100k times get( random() * 100k ) on a List with 200K elements.

P.S.: I will try to attach the code as a zip.

---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org


Mime
View raw message