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
_______________________________________________
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
