[Python-Dev] Google Summer of Code proposal: New class for work with binary trees AVL and RB as with the standard dictionary.

[Vladimir 'Yu' Stepanov]

Josiah Carlson wrote:
> There exists various C and Python implementations of both AVL and
> Red-Black trees.  For users of Python who want to use AVL and/or
> Red-Black trees, I would urge them to use the Python implementations. 
> In the case of *needing* the speed of a C extension, there already
> exists a CPython extension module for AVL trees:
>     http://www.python.org/pypi/pyavl/1.1
>
> I would suggest you look through some suggested SoC projects in the
> wiki:
>     http://wiki.python.org/moin/SummerOfCode
>
>  - Josiah
>
>   
Thanks for the answer!

I already saw pyavl-1.1. But for this reason I would like to see the module
in a standard package python. Functionality for pyavl and dict to compare
difficultly. Functionality of my module will differ from functionality dict
in the best party. I have lead some tests on for work with different types
both for a package pyavl-1.1, and for the prototype of own module. The 
script
of check is resulted in attached a file avl-timeit.py In files
timeit-result-*-*.txt results of this test. The first in the name of a file
means quantity of the added elements, the second - argument of a method
timeit. There it is visible, that in spite of the fact that the module 
xtree
is more combined in comparison with pyavl the module (for everyone again
inserted pair [the key, value], is created two elements: python object - 
pair,
and an internal element of a tree), even in this case it works a little bit
more quickly. Besides the module pyavl is unstable for work in multithread
appendices (look the attached file module-avl-is-thread-unsafe.py).

I think, that creation of this type (together with type of pair), will make
programming more convenient since sorting by function sort will be required
less often.

I can probably borrow in this module beyond the framework of the project
google. The demand of such type of data is interesting. Because of 
necessity
of processing `gcmodule.c' and `obmalloc.c' this module cannot be realized
as the external module.


-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: avl-timeit.py
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment.pot 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: install-pyavl.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: module-avl-is-thread-unsafe.py
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0001.pot 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-30-1000000.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0001.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-100-100000.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0002.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-1000-10000.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0003.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-10000-1000.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0004.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-100000-100.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0005.txt 
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: timeit-result-1000000-10.txt
Url: http://mail.python.org/pipermail/python-dev/attachments/20060426/3df7dab5/attachment-0006.txt