You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Jörg Schmücker <jo...@ekkono.com> on 2004/02/03 18:04:46 UTC
[collections] Implementation of List with a tree
Hi,
We just discovered commons collections, and are replacing a lot of our stuff
with your classes. Thanks!
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?
Cheers
Joerg
--
Jörg Schmücker
ekkono GmbH
Geschäftsführer
p: 06151 10 14 54
f: 06151 10 15 71
m: 0173 32 37 82 8
js@ekkono.com
Dinow 3.0 ist da!
Unsere sichere Peer-to-Peer-Groupware erleichtert die Kommunikation im
Unternehmen und über Unternehmensgrenzen hinweg. Besuchen Sie unsere Website
und informieren Sie sich über die kostenfreie Dinow 3.0 Personal Edition.
http://www.ekkono.com/deutsch/indexcontent_download.htm
Dinow 3.0 is ready! Our secure peer-to-peer platform enables communication
inside and across organizations. Please visit our website and download
Dinow 3.0 Personal Edition free of charge.
http://www.ekkono.com/english/indexcontent_download.htm
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] Implementation of List with a tree
Posted by Stephen Colebourne <sc...@btopenworld.com>.
These figures look good (although they could do with a litle more
explanation ;-)
I suggest either adding to the existing Bugzilla entry, or creating a new
one with your code and tests. Also I would ideally want a one word name for
the list, not including 'Fast' (as that has other meanings in
[collections]). Perhaps BalancedList or TreeList?
Stephen
----- Original Message -----
From: "Jörg Schmücker" <jo...@ekkono.com>
> 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" <jo...@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
RE: [collections] Implementation of List with a tree
Posted by Jörg Schmücker <jo...@ekkono.com>.
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" <jo...@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
Re: [collections] Implementation of List with a tree
Posted by Stephen Colebourne <sc...@btopenworld.com>.
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" <jo...@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