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
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
