commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jörg Schmücker <joerg.schmuec...@ekkono.com>
Subject RE: [collections] Implementation of List with a tree
Date Wed, 04 Feb 2004 10:08:38 GMT
I don't know if it makes sense to consolidate the code because I am using a
lot of information about the structure of the tree and how the rebalancing
is performed.

The implementation passed all the tests in the test framework for lists,
i.e. AbstractTestList.

I ran a quick performance check it's better than I thought for 100 000 of
each (all times in millis):

Add; insert; get
FastInsertionList = 300;501;110;
ArrayList = 70;20390;20;
LinkedList = 50;226636;279742;

Ok, how do I declare the later?

Cheers,

	Joerg

-----Original Message-----
From: Stephen Colebourne [mailto:scolebourne@btopenworld.com]
Sent: Tuesday, February 03, 2004 11:14 PM
To: Jakarta Commons Developers List
Subject: Re: [collections] Implementation of List with a tree


Sounds interesting. See
http://jakarta.apache.org/commons/patches.html

Also see Bugzilla for an AVLTree/Set already proposed. (You may want to
reuse this in some way)
http://issues.apache.org/bugzilla/show_bug.cgi?id=22853

What I really need is a good implementation with tests written using the
collections testframework. Plus a reason for including it. (Performance
between Array and Linked is a good reason ;-)

Finally, you must declare that your submission is donated to the Apache
Software Foundation.

Stephen

----- Original Message -----
From: "Jörg Schmücker" <joerg.schmuecker@ekkono.com>
> We have implemented a list based on a tree which allows insertion in log n
> and access in log n.  This means it is not as slow as an ArrayList for the
> insertion of elements anywhere but at the end of the list, and not as slow
> as LinkedList for locating an element.  But not as fast as LinkedList with
> insertion at the end.  It uses an AVL-Tree and offsets to accomplish that.
> I would like to contribute it.  How should I go forward?




---------------------------------------------------------------------
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