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. #!/usr/local/bin/python # Initialize modules import avl import xtree import types import sys import timeit if len(sys.argv) != 3: iterations = 1000000 count = 10 else: iterations = int(sys.argv[1]) count = int(sys.argv[2]) print "Iterations", iterations print "Repeats", count print result_avl = timeit.Timer(""" import avl a = avl.new() for i in xrange(%d): a.insert(i) """ % iterations).timeit(count) print "object avl.new()", result_avl result_xtree = timeit.Timer(""" import xtree a = xtree.xtree() for i in xrange(%d): a[i] = True """ % iterations).timeit(count) print "object xtree.xtree()", result_xtree result_dict = timeit.Timer(""" import types a = dict() for i in xrange(%d): a[i] = True """ % iterations).timeit(count) print "object dict()", result_dict print " Dict Xtree AVL" print "Dict %.2f %.2f %.2f" % (float(result_dict)/result_dict, float(result_dict)/result_xtree, float(result_dict)/result_avl) print "Xtree %.2f %.2f %.2f" % (float(result_xtree)/result_dict, float(result_xtree)/result_xtree, float(result_xtree)/result_avl) print "AVL %.2f %.2f %.2f" % (float(result_avl)/result_dict, float(result_avl)/result_xtree, float(result_avl)/result_avl) fox:root!~/Downloads/Python/PYTHON/pyavl-1.1 > python setup.py install running install running build running build_ext building 'avl' extension creating build creating build/temp.freebsd-5.4-RELEASE-i386-2.4 cc -fno-strict-aliasing -DNDEBUG -O -pipe -D__wchar_t=wchar_t -DTHREAD_STACK_SIZE=0x20000 -O2 -fPIC -DHAVE_AVL_VERIFY -DAVL_FOR_PYTHON -I/usr/local/include/python2.4 -c avl.c -o build/temp.freebsd-5.4 -RELEASE-i386-2.4/avl.o -O2 -Wno-parentheses -Wno-uninitialized cc -fno-strict-aliasing -DNDEBUG -O -pipe -D__wchar_t=wchar_t -DTHREAD_STACK_SIZE=0x20000 -O2 -fPIC -DHAVE_AVL_VERIFY -DAVL_FOR_PYTHON -I/usr/local/include/python2.4 -c avlmodule.c -o build/temp.freeb sd-5.4-RELEASE-i386-2.4/avlmodule.o -O2 -Wno-parentheses -Wno-uninitialized creating build/lib.freebsd-5.4-RELEASE-i386-2.4 cc -shared -pthread -O2 build/temp.freebsd-5.4-RELEASE-i386-2.4/avl.o build/temp.freebsd-5.4-RELEASE -i386-2.4/avlmodule.o -o build/lib.freebsd-5.4-RELEASE-i386-2.4/avl.so -Wl,-x running install_lib copying build/lib.freebsd-5.4-RELEASE-i386-2.4/avl.so -> /usr/local/lib/python2.4/site-packages