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 #!/usr/local/bin/python import avl import time a = avl.new() crash = 61215 # may be any in range 0 .. 99998 a.insert(crash) a.insert(crash + 1) b = iter(a) b.next() for i in xrange(100000): a.insert(i) a.remove(crash) k=[] for i in xrange(100): # fill memory with padding for 32-bit machine k.append(pow(65536, 2)) # fill memory with padding for 64-bit machine k.append(pow(65536, 10)) for i in b: print i Iterations 30 Repeats 1000000 object avl.new() 44.3226678371 object xtree.xtree() 30.8406031132 object dict() 12.9507939816 Dict Xtree AVL Dict 1.00 0.42 0.29 Xtree 2.38 1.00 0.70 AVL 3.42 1.44 1.00 Iterations 100 Repeats 100000 object avl.new() 13.9669251442 object xtree.xtree() 10.1008188725 object dict() 3.32260894775 Dict Xtree AVL Dict 1.00 0.33 0.24 Xtree 3.04 1.00 0.72 AVL 4.20 1.38 1.00 Iterations 1000 Repeats 10000 object avl.new() 16.0562131405 object xtree.xtree() 11.6249010563 object dict() 2.73937296867 Dict Xtree AVL Dict 1.00 0.24 0.17 Xtree 4.24 1.00 0.72 AVL 5.86 1.38 1.00 Iterations 10000 Repeats 1000 object avl.new() 19.2930951118 object xtree.xtree() 14.0921308994 object dict() 4.18660902977 Dict Xtree AVL Dict 1.00 0.30 0.22 Xtree 3.37 1.00 0.73 AVL 4.61 1.37 1.00 Iterations 100000 Repeats 100 object avl.new() 22.347192049 object xtree.xtree() 15.4935331345 object dict() 4.46709012985 Dict Xtree AVL Dict 1.00 0.29 0.20 Xtree 3.47 1.00 0.69 AVL 5.00 1.44 1.00 object avl.new() 32.5346679688 object xtree.xtree() 17.4350678921 object dict() 4.39839410782 Dict Xtree AVL Dict 1.00 0.25 0.14 Xtree 3.96 1.00 0.54 AVL 7.40 1.87 1.00