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

Vladimir 'Yu' Stepanov vys at renet.ru
Wed Apr 26 09:15:13 CEST 2006

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/50c773c4/attachment-0001.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/50c773c4/attachment-0001.txt

More information about the Python-Dev mailing list