Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Python (http://www.velocityreviews.com/forums/f43-python.html)
-   -   Red Black Tree implementation? (http://www.velocityreviews.com/forums/t960279-red-black-tree-implementation.html)

Dan Stromberg 05-01-2013 11:11 PM

Red Black Tree implementation?
 
What's the best Red Black Tree implementation for Python with an opensource
license?

I started out looking at
http://newcenturycomputers.net/proje...ee.htmlbecause it was
pretty high in Google and had the operators I wanted, but it
gets very slow at about half a million elements. I've been discussing this
with a C programmer who believes that Red Black Trees should perform very
similarly to an AVL tree, but that's not at all what I'm getting with the
newcenturycomputers implementation.

I'd prefer something that looks like a dictionary, runs on 2.x and 3.x, and
passes pylint, but if that's not yet available I might make it so.

This is part of a comparison of Python tree types I did a while back...
I've been thinking that I've given Red Black Trees short shrift by using a
poor implementation. The comparison so far is at
http://stromberg.dnsalias.org/~strom...ap-comparison/

Thanks!


duncan smith 05-02-2013 02:06 AM

Re: Red Black Tree implementation?
 
On 02/05/13 00:11, Dan Stromberg wrote:
>
> What's the best Red Black Tree implementation for Python with an
> opensource license?
>
> I started out looking at
> http://newcenturycomputers.net/projects/rbtree.html because it was
> pretty high in Google and had the operators I wanted, but it gets very
> slow at about half a million elements. I've been discussing this with a
> C programmer who believes that Red Black Trees should perform very
> similarly to an AVL tree, but that's not at all what I'm getting with
> the newcenturycomputers implementation.
>
> I'd prefer something that looks like a dictionary, runs on 2.x and 3.x,
> and passes pylint, but if that's not yet available I might make it so.
>
> This is part of a comparison of Python tree types I did a while back...
> I've been thinking that I've given Red Black Trees short shrift by using
> a poor implementation. The comparison so far is at
> http://stromberg.dnsalias.org/~strom...ap-comparison/
>
> Thanks!
>
>



I have an implementation that you can try out. It's not based on any
other implementation, so my bugs will be independent of any bugs in the
code you're currently using. It looks more like a set - add, remove,
discard. Not tried on Python 3 or run through pylint. I just tried
adding a million items to a tree, and it takes about 25% longer to add
items at the end compared to those at the beginning. Timing removals
uncovered a bug. So if you want the code I'll fix the bug and send it
(to your gmail e-mail address?). Cheers.

Duncan

Dan Stromberg 05-03-2013 02:00 AM

Re: Red Black Tree implementation?
 
On Wed, May 1, 2013 at 7:06 PM, duncan smith <buzzard@invalid.invalid>wrote:

> I have an implementation that you can try out. It's not based on any other
> implementation, so my bugs will be independent of any bugs in the code
> you're currently using. It looks more like a set - add, remove, discard.
> Not tried on Python 3 or run through pylint. I just tried adding a million
> items to a tree, and it takes about 25% longer to add items at the end
> compared to those at the beginning. Timing removals uncovered a bug. So if
> you want the code I'll fix the bug and send it (to your gmail e-mail
> address?). Cheers.
>
> Duncan
> --
> http://mail.python.org/**mailman/listinfo/python-list<http://mail.python.org/mailman/listinfo/python-list>
>


What license?

Thanks!


duncan smith 05-07-2013 12:55 AM

Re: Red Black Tree implementation?
 
On 03/05/13 03:00, Dan Stromberg wrote:
>
> On Wed, May 1, 2013 at 7:06 PM, duncan smith <buzzard@invalid.invalid
> <mailto:buzzard@invalid.invalid>> wrote:
>
> I have an implementation that you can try out. It's not based on any
> other implementation, so my bugs will be independent of any bugs in
> the code you're currently using. It looks more like a set - add,
> remove, discard. Not tried on Python 3 or run through pylint. I just
> tried adding a million items to a tree, and it takes about 25%
> longer to add items at the end compared to those at the beginning.
> Timing removals uncovered a bug. So if you want the code I'll fix
> the bug and send it (to your gmail e-mail address?). Cheers.
>
> Duncan
> --
> http://mail.python.org/__mailman/listinfo/python-list
> <http://mail.python.org/mailman/listinfo/python-list>
>
>
> What license?
>
> Thanks!
>


Here's the text I usually prepend.


##Copyright (c) 2013 duncan g. smith
##
##Permission is hereby granted, free of charge, to any person obtaining a
##copy of this software and associated documentation files (the "Software"),
##to deal in the Software without restriction, including without limitation
##the rights to use, copy, modify, merge, publish, distribute, sublicense,
##and/or sell copies of the Software, and to permit persons to whom the
##Software is furnished to do so, subject to the following conditions:
##
##The above copyright notice and this permission notice shall be included
##in all copies or substantial portions of the Software.
##
##THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
##OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
MERCHANTABILITY,
##FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
##THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
##OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
##ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
##OTHER DEALINGS IN THE SOFTWARE.


Basically, "do what you want with it but don't blame me if it goes tits
up". I'm happy to consider tidying it up a bit and using a more
recognized form of licence. Just had a bank holiday here, so bug not yet
squashed. But it is the sort of bug that might account for what you've
seen (if a similar bug exists in the code you've been using). The tree
doesn't always get properly rebalanced on node removals. I'll attack the
problem later tomorrow (technically, later today). Cheers.

Duncan

Chris Angelico 05-07-2013 01:21 AM

Re: Red Black Tree implementation?
 
On Tue, May 7, 2013 at 10:55 AM, duncan smith <buzzard@invalid.invalid> wrote:
> Here's the text I usually prepend.
>
>
> ##Copyright (c) 2013 duncan g. smith
> ##
> ##Permission is hereby granted, free of charge, to any person obtaining a
> ##copy of this software and associated documentation files (the "Software"),
> ##to deal in the Software without restriction, including without limitation
> ##the rights to use, copy, modify, merge, publish, distribute, sublicense,
> ##and/or sell copies of the Software, and to permit persons to whom the
> ##Software is furnished to do so, subject to the following conditions:
> ##
> ##The above copyright notice and this permission notice shall be included
> ##in all copies or substantial portions of the Software.
> ##
> ##THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
> ##OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> ##FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
> ##THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> ##OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
> ##ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
> ##OTHER DEALINGS IN THE SOFTWARE.
>
>
> Basically, "do what you want with it but don't blame me if it goes tits up".
> I'm happy to consider tidying it up a bit and using a more recognized form
> of licence.


Is that the MIT license? If not, consider using it; it's well known
and trusted. I haven't eyeballed yours closely but it looks extremely
similar, at least.

ChrisA

duncan smith 05-07-2013 01:28 PM

Re: Red Black Tree implementation?
 
On 07/05/13 02:20, Dan Stromberg wrote:
>

[snip]
>
> I'm starting to think Red Black Trees are pretty complex.
>
>


A while ago I looked at a few different types of self-balancing binary
tree. Most look much easier to implement.

BTW, the licence might be MIT - I just copied it from someone else's code.

Duncan

duncan smith 05-08-2013 11:21 PM

Re: Red Black Tree implementation?
 
On 07/05/13 02:20, Dan Stromberg wrote:
>
> On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard@invalid.invalid
> <mailto:buzzard@invalid.invalid>> wrote:
>
>


[snip]

>
> I'd prefer Apache or MIT or BSD 3-clause, but I could probably work with
> this.
> http://joinup.ec.europa.eu/community...ration-way-out
>
> I'm eager to see the code, and would love it if you sorted out the
> deletion rebalance issue.
>
> I just plunked some time into
> https://github.com/headius/redblack/..._black_tree.py , only
> to find that it didn't appear to be doing deletions correctly - the tree
> would become unprintable after deleting one element. It's possible I
> introduced the bug, but right now I don't particularly suspect so,
> having not changed the __del__ method.
>
> I'm starting to think Red Black Trees are pretty complex.
>
>


Mine is fixed now (sent to your gmail address). Restoring the tree
properties after deletion is awkward to get right, and doesn't affect
the performance noticeably for smallish trees if you get it wrong.

I realised my code was buggy when I tried adding, then removing a
million items and ran into the recursion limit. It now passes a test
where I check the tree properties after each addition / deletion.

Duncan

Dan Stromberg 05-09-2013 01:40 AM

Re: Red Black Tree implementation?
 
OK, I've got one copy of trees.py with md5
211f80c0fe7fb9cb42feb9645b4b3ffe. You seem to be saying I should have
two though, but I don't know that I do...


On 5/8/13, duncan smith <buzzard@invalid.invalid> wrote:
> On 07/05/13 02:20, Dan Stromberg wrote:
>>
>> On Mon, May 6, 2013 at 5:55 PM, duncan smith <buzzard@invalid.invalid
>> <mailto:buzzard@invalid.invalid>> wrote:
>>
>>

>
> [snip]
>
>>
>> I'd prefer Apache or MIT or BSD 3-clause, but I could probably work with
>> this.
>> http://joinup.ec.europa.eu/community...ration-way-out
>>
>> I'm eager to see the code, and would love it if you sorted out the
>> deletion rebalance issue.
>>
>> I just plunked some time into
>> https://github.com/headius/redblack/..._black_tree.py , only
>> to find that it didn't appear to be doing deletions correctly - the tree
>> would become unprintable after deleting one element. It's possible I
>> introduced the bug, but right now I don't particularly suspect so,
>> having not changed the __del__ method.
>>
>> I'm starting to think Red Black Trees are pretty complex.
>>
>>

>
> Mine is fixed now (sent to your gmail address). Restoring the tree
> properties after deletion is awkward to get right, and doesn't affect
> the performance noticeably for smallish trees if you get it wrong.
>
> I realised my code was buggy when I tried adding, then removing a
> million items and ran into the recursion limit. It now passes a test
> where I check the tree properties after each addition / deletion.
>
> Duncan
> --
> http://mail.python.org/mailman/listinfo/python-list
>


duncan smith 05-09-2013 04:31 AM

Re: Red Black Tree implementation?
 
On 09/05/13 02:40, Dan Stromberg wrote:
> OK, I've got one copy of trees.py with md5
> 211f80c0fe7fb9cb42feb9645b4b3ffe. You seem to be saying I should have
> two though, but I don't know that I do...
>
>


I've just re-sent it.

Duncan


duncan smith 05-09-2013 01:52 PM

Re: Red Black Tree implementation?
 
On 09/05/13 02:40, Dan Stromberg wrote:
> OK, I've got one copy of trees.py with md5
> 211f80c0fe7fb9cb42feb9645b4b3ffe. You seem to be saying I should have
> two though, but I don't know that I do...
>


[snip]

Yes, 211f80c0fe7fb9cb42feb9645b4b3ffe is the correct checksum for the
latest version. The previous version had an issue when adding
non-distinct items (items that compare equal to items already in the
tree). Cheers.

Duncan



All times are GMT. The time now is 04:33 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.