I would like to participate in Google Summer of Code. The idea consists in creation of a specialized class for work with binary trees AVL and RB. The part of ideas is taken from Parrot (Perl6) where for pair values the specialized type is stipulated. As advantages it is possible to note: * High speed. On simple types at quantity of elements up to 10000 speed of work concedes to the standard dictionary of all in 2.7 times. * Safety of work in a multithread operating mode. * The method for frosts of object is stipulated. * The data storage is carried out in the sorted kind. * A high overall performance `item' and `iteritem' methods as it is not necessary to create new objects. * At lots of objects in a tree memory is used much less intensively. * Absence of collisions. As consequence, it is impossible to generate bad data for creation DoS of the attacks influencing the dictionary of transferred arguments. * For objects existence of a method __ hash __ is not necessary. * The same kind of the dictionary by means of the overloaded operations probably change of its behaviour so that it supported the multivariational representation based on stratification given and subsequent recoils. Additional requirements to key objects: * The opportunity of comparison of key objects function cmp is necessary. There are the reasons, braking development of this project: * Compulsion of heading of a module `gc' for each compound object (this structure is unessential to some objects, but updating `gc' the module is required). * Absence of standard object the pair, probably depends on the previous item. Lacks of a binary tree: * Average time of search for hash - O (1), and for trees - O (log2 N). * A lot of memory under a single element of a tree: (3*sizeof (void *) + sizeof (int))*2, one element is used rather - the pair, the second site of memory is allocated under node of a tree. In protection of object "pair": * The logic of methods of the given object noticeably is easier than tuple, that as a result can affect speed of work of the program in the best party. * Alignment on 8 bytes has no big sense at present architecture where in cache sample a minimum on 64 bytes is made. Use of type "pair" will give an appreciable prize at use of alignment in 4 bytes. Otherwise on 64-bit platforms it is much more favourable to use tuple object. The given project can demand processing of the module `gcmodule.c' and `tupleobject.c'. It is necessary to reduce the size of static objects, for this purpose the opportunity is necessary is transparent to pass objects not having direct support from the module `gcmodule.c'. Also it will be partially necessary to process the module `obmalloc.c' for more effective distribution of memory. I shall be glad to answer questions on this theme.

On 4/25/06, Josiah Carlson <jcarlson@uci.edu> 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

And a C implementation for redblack tree is here: http://python.org/sf/1324770 :) Hye-Shik

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

"Josiah Carlson" <jcarlson@uci.edu> wrote in message news:20060426094148.66EE.JCARLSON@uci.edu...

Then again, you already have your own implementation of a tree module, and it seems as though you would like to be paid for this already-done work. I don't know how google feels about such things,

They are explicitly against that in the student FAQ. They are paying for new code writen after the project is approved and before the endpoint.

but you should remember to include this information in your application.

Existing code can legitimately be used to show feasibility of the project and competancy of the student Terry Jan Reedy

Vladimir 'Yu' Stepanov wrote:

* To adapt allocation of blocks of memory with other alignment. Now alignment is rigidly set on 8 bytes. As a variant, it is possible to use alignment on 4 bytes. And this value can be set at start of the interpreter through arguments/variable environments/etc. At testing with alignment on 4 or 8 bytes difference in speed of work was not appreciable.

That depends on the hardware you use, of course. Some architectures absolutely cannot stand mis-aligned accesses, and programs will just crash if they try to perform such accesses. So Python should err on the safe side, and only use a smaller alignment when it is known not to hurt. OTOH, I don't see the *advantage* in reducing the alignment.

* To expand the maximal size which can be allocated by means of the given module. Now the maximal size is 256 bytes.

Right. This is somewhat deliberate, though; the expectation is that fragmentation will increase dramatically if even larger size classes are supported.

* At the size of the allocated memory close to maximal, the allocation of blocks becomes inefficient. For example, for the sizesof blocks 248 and 256 (blocksize), values of quantity of elements (PAGESIZE/blocksize) it is equal 16. I.e. it would be possible to use for the sizes of the block 248 same page, as for the size of the block 256.

Good idea; that shouldn't be too difficult to implement: for sizes above 215, pools need to be spaced apart only at 16 bytes. Regards, Martin

Tim Peters wrote:

[Vladimir 'Yu' Stepanov]

...

...

* To adapt allocation of blocks of memory with other alignment. Now alignment is rigidly set on 8 bytes. As a variant, it is possible to use alignment on 4 bytes. And this value can be set at start of the interpreter through arguments/variable environments/etc. At testing with alignment on 4 or 8 bytes difference in speed of work was not appreciable.

[Martin v. Löwis]

...

That depends on the hardware you use, of course. Some architectures absolutely cannot stand mis-aligned accesses, and programs will just crash if they try to perform such accesses.

Note that we _had_ to add a goofy "long double" to the PyGC_Head union because some Python platform required 8-byte alignment for some types ... see rev 25454. Any spelling of malloc() also needs to return memory aligned for any legitimate purpose, and 8-byte alignment is the strictest requirement we know of across current Python platforms. It is possible to receive the reference about these tests? I have lead some tests, which very small difference of speed of work at alignment on 4 and 8 byte (a maximum of 8%, and in the basic less than one percent).

In tests consecutive search of elements in one piece of memory was used. I understand, that it is necessary to lead still the test with a casual choice of addresses to minimize optimization of work cache the processor. And certainly not all platforms will show the same result (I shall try to not forget to attach a source code of the test and its result of work :) ). On the other hand reduction of a memory size by each separate copy of object is capable to increase speed by the same percent that is lost at change of displacement about 8 bytes up to 4 :) Besides begins to refuse probably superstructures on allocation of memory at some objects, since int.

...

So Python should err on the safe side, and only use a smaller alignment when it is known not to hurt.

OTOH, I don't see the *advantage* in reducing the alignment.

It could cut wasted bytes. There is no per-object memory overhead in a release-build obmalloc: the allocatable part of a pool is entirely used for user-visible object memory, except when the alignment requirement ends up forcing unused (by both the user and by obmalloc) pad bytes. For example, Python ints consume 12 bytes on 32-bit boxes, but if space were allocated for them by obmalloc (it's not), obmalloc would have to use 16 bytes per int to preserve 8-byte alignment. Good note.

OTOH, obmalloc (unlike PyGC_Head) has always used 8-byte alignment, because that's what worked best for Vladimir Marangozov during his extensive timing tests. It's not an isolated decision -- e.g., it's also influenced by, and influences, "the best" pool size, and (of course) cutting alignment to 4 would double the number of "size classes" obmalloc has to juggle. Yes, the maximum quantity of buffers will really be doubled. But it should not to affect as that productivity of system, or on total amount of consumed memory. Change of a fragmentation of memory to count it is impossible, since it will depend on the concrete application.

...

...

* To expand the maximal size which can be allocated by means of the given module. Now the maximal size is 256 bytes.

...

Right. This is somewhat deliberate, though; the expectation is that fragmentation will increase dramatically if even larger size classes are supported.

It's entirely deliberate ;-) obmalloc is no way trying to be a general-purpose allocator. It was designed specifically for the common memory patterns in Python, aiming at large numbers of small objects of the same size. That's extremely common in Python, and allocations larger than 256 bytes are not. The maximum size was actually 64 bytes at first. After that, dicts grew an embedded 8-element table, which vastly increased the size of the dict struct. obmalloc's limit was boosted to 256 then, although it could have stopped at the size of a dict (in the rough ballpark of 150 bytes). There was no reason (then or now) to go beyond 256. See below.

...

...

* At the size of the allocated memory close to maximal, the allocation of blocks becomes inefficient. For example, for the sizesof blocks 248 and 256 (blocksize), values of quantity of elements (PAGESIZE/blocksize) it is equal 16. I.e. it would be possible to use for the sizes of the block 248 same page, as for the size of the block 256.

...

Good idea; that shouldn't be too difficult to implement: for sizes above 215, pools need to be spaced apart only at 16 bytes.

I'd rather drop the limit to 215 then <0.3 wink>. Allocations that large probably still aren't important to obmalloc, but it is important that finding a requested allocation's "size index" be as cheap as possible. Uniformity helps that. An available module on allocation of memory really does not approach for overall aims. And speed of work can "blink" in case of existing non-uniform realization on allocation of memory. In some cases allocation of memory in the module `obmalloc.c' work as function of a wrapper for standard malloc/free, that does not raise speed :) .

On modern boxes, it may be desirable to boost POOL_SIZE -- nobody has run timing experiments as comprehensive as Vladimir ran way back when, and there's no particular reason to believe that the same set of tradeoffs would look best on current architectures. As to speed of work it will be not less than in available systems of allocation of memory. Naturally, there are no pluses without what that of minuses. In my opinion available minuses can be made insignificant. Language Python has obviously expressed specificity on allocation of memory

For an example we shall assume, that two pieces of memory are allocated. One is allocated `obmalloc.c'. Another is allocated standard malloc. Both of a piece are small enough to be realized by similar methods. In a number of OS malloc will lose in speed of work for multi-thread programs, because of blocking the global lock on allocation of memory. Certainly it concerns not to all operational systems. that it is possible to use favourably, having developed system of allocation of memory is direct under it. The properties inherent in language Python: * At work in multi-thread a mode already there is blocking GIL which can be used and in case of with allocation of memory. * Objects which are often used, it is better to adapt on the real size, instead of on log2(size(ob)) therefore as function realloc is carried out extremely seldom or even less often :) . * Extremely seldom there are objects the size of the allocated memory multiple 512, 1024, 2048 since before them heading Python of object, and the parameters describing properties of object is placed still. First two items concern and to present `obmalloc.c', but for a narrow circle of allocated blocks of memory. In some interpreters own system of allocation of memory is used. Adjustment of a control system of memory not the latest step to acceleration Python. Thanks everyone who has answered. The theme on former is interesting. #include <stdio.h> #include <unistd.h> #include <sys/types.h> #include <sys/time.h> #include <sys/resource.h> typedef union __genlink { struct { union __genlink *qcl_prev; union __genlink *qcl_next; } qcl; /* Queue of Cycle List */ void *point[2]; union __genlink *link[2]; } genlink; void qcl_init(genlink *root) { root->qcl.qcl_next = root; root->qcl.qcl_prev = root; } void qcl_insert_after(genlink *root, genlink *p) { genlink *next; p->qcl.qcl_prev = root; p->qcl.qcl_next = (next = root->qcl.qcl_next); root->qcl.qcl_next = p; next->qcl.qcl_prev = p; } #define COUNT 10000000 #define REPEAT 1000 long long rusage_print(const char *s, struct rusage *oru) { struct rusage ru; int sec; int usec; long long ret; getrusage(RUSAGE_SELF, &ru); sec = ru.ru_utime.tv_sec - oru->ru_utime.tv_sec; if ((usec = ru.ru_utime.tv_usec - oru->ru_utime.tv_usec) < 0) { sec--; usec = 1000000 + usec; } printf("%s: user time %d.%6.6d\n", s, sec, usec); fflush(stdout); ret = sec*1000000; ret += usec; return ret; } main() { genlink root; genlink *p; genlink *base; int i; int k; struct rusage ru; long long tm_normal; long long tm_align4; long long tm_align2; if ((base = malloc((COUNT + 1)*sizeof(genlink))) == NULL) { fprintf(stderr, "malloc failed\n"); exit(1); } bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + sizeof(genlink)); // add compenstion. qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_normal = rusage_print("align for two pointers", &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + 4); qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_align4 = rusage_print("align for 4 bytes", &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); getrusage(RUSAGE_SELF, &ru); bzero(base, (COUNT + 1)*sizeof(genlink)); qcl_init(&root); for (i = 0; i < COUNT; i++) { p = (genlink *)(((char *)(&base[i])) + 2); qcl_insert_after(&root, p); } for (k = 0, p = &root; k < REPEAT; k++) for (i = 0; i < COUNT; i++) p = p->qcl.qcl_next; tm_align2 = rusage_print("align for 2 bytes", &ru); printf(" Normal Align4 Align2\n"); printf("Normal %8.2f %8.2f %8.2f\n", ((double)tm_normal*100)/tm_normal, ((double)tm_normal*100)/tm_align4, ((double)tm_normal*100)/tm_align2 ); printf("Align4 %8.2f %8.2f %8.2f\n", ((double)tm_align4*100)/tm_normal, ((double)tm_align4*100)/tm_align4, ((double)tm_align4*100)/tm_align2 ); printf("Align2 %8.2f %8.2f %8.2f\n", ((double)tm_align2*100)/tm_normal, ((double)tm_align2*100)/tm_align4, ((double)tm_align2*100)/tm_align2 ); } At once: fox:root!~/test > cc aligntest.c; a.out ----------------------------------------- align for two pointers: user time 42.819181 align for 4 bytes: user time 42.725775 align for 2 bytes: user time 59.198894 Normal Align4 Align2 Normal 100.00 100.22 72.33 Align4 99.78 100.00 72.17 Align2 138.25 138.56 100.00 ------------------------------------------ At second: fox:root!~/test > cc -O2 aligntest.c; a.out ------------------------------------------ align for two pointers: user time 10.152062 align for 4 bytes: user time 10.161598 align for 2 bytes: user time 10.145807 Normal Align4 Align2 Normal 100.00 99.91 100.06 Align4 100.09 100.00 100.16 Align2 99.94 99.84 100.00 ------------------------------------------ XXX:vys!~ > a.out align for two pointers: user time 0.228938 align for 4 bytes: user time 0.237644 align for 2 bytes: user time 0.235519 Normal Align4 Align2 Normal 100.00 96.34 97.21 Align4 103.80 100.00 100.90 Align2 102.87 99.11 100.00 XXX:vys!~ > a.out align for two pointers: user time 0.254978 align for 4 bytes: user time 0.236627 align for 2 bytes: user time 0.242168 Normal Align4 Align2 Normal 100.00 107.76 105.29 Align4 92.80 100.00 97.71 Align2 94.98 102.34 100.00 XXX:vys!~ >

Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" <vys@renet.ru> wrote:

...

Comparison of functions of sorting and binary trees not absolutely correctly. I think that function sort will lose considerably on greater lists. Especially after an insert or removal of all one element.

Generally speaking, people who understand at least some of Python's internals (list internals specifically), will not be *removing* entries from lists one at a time (at least not using list.pop(0) ), because that is slow. If they need to remove items one at a time from the smallest to the largest, they will usually use list.reverse(), then repeatedly list.pop(), as this is quite fast (in general).

Yes. I understood it when resulted a set example.

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

- Josiah

As an aside, I have personally implemented trees a few times for different reasons. One of the issues I have with most tree implementations is that it is generally difficult to do things like "give me the kth smallest/largest item". Of course the standard solution is what is generally called a "partial order" or "order statistic" tree, but then you end up with yet another field in your structure. One nice thing about Red-Black trees combined with order-statistic trees, is that you can usually use the uppermost bit of the order statistics for red/black information. Of course, this is really only interesting from an "implement this in C" perspective; because if one were implementing it in Python, one may as well be really lazy and not bother implementing guaranteed balanced trees and be satisfied with randomized-balancing via Treaps. Here that I have found through Google on a line " order statistic binary

Such problem arises at creation of the list of timers. And this list is in constant change: addition/removal of elements in the list. collections.deque here does not approach, as if addition in the big list is made or search of the nearest value on the average it is necessary to lead quantity of checks N/2 is made. For a binary tree the quantity of necessary checks on former is equal log2 (N). Other variant of use of binary trees: search of concurrence to ranges. Such ranges can be blocks IP of addresses. Also this kind of the dictionary can be used for a fast finding, whether the given point enters into one of pieces. These problems can be realized by means of binary search. For binary search the same lacks, as for above resulted example are characteristic: the insert and removal for lists are carried out slowly and after an insert sorting of the list is required. Except for that function of binary search is absent in standard package Python. It is possible to write its analogue on pure Python, but it will be more than twice more slowly. tree ": http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic20/ I have understood, that similar I have already made something :). The result of the test shows on the most bad result, but is certainly worse, than a usual tree. Badly that up to the end I have not tested this realization. Percent on 90 I am assured that it is efficient. There is a question. What API should be used? Therefore as if to address to object, as to MAP to object __getitem__ will return one result. And if as to the list - another. Here the list of already existing attributes and methods: class xtree(__builtin__.object) | X-Tree. Binary tree with AVL balance mechanism. | | Methods defined here: | | __contains__(...) | x.__contains__(y) <==> y in x | | __delitem__(...) | x.__delitem__(y) <==> del x[y] | | __getitem__(...) | x.__getitem__(y) <==> x[y] | | __iter__(...) | x.__iter__() <==> iter(x) | | __len__(...) | x.__len__() <==> len(x) | | __repr__(...) | x.__repr__() <==> repr(x) | | __setitem__(...) | x.__setitem__(i, y) <==> x[i]=y | | append(...) | D.append((k: v)) -> None, append new pair element into tree with sorting. | Return pair element if argument is exist. | | clear(...) | D.clear() -> None. Remove all items from D. | | copy(...) | D.copy() -> a shallow copy of D. | | get(...) | D.get(k[,d]) -> D[k] if k in D, else d. d defaults to None. | | has_key(...) | D.has_key(k) -> True if D has a key k, else False. | | items(...) | D.items() -> list of D's (key, value) pairs. | | iteritems(...) | D.iteritems() -> an iterator over the (key, value) items of D. | | iterkeys(...) | D.iterkeys() -> an iterator over the keys of D. | | itervalues(...) | D.itervalues() -> an iterator over the values of D. | | keys(...) | D.keys() -> list of D's keys. | | pop(...) | D.pop(k[,d]) -> v, remove specified key and return the corresponding value. | If key is not found, d is returned if given, otherwise KeyError is raised. | | popitem(...) | D.popmin() -> (k, v), remove and return minimal (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | popmax(...) | D.popmax() -> (k, v), remove and return maximal (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | popmin(...) | D.popmin() -> (k, v), remove and return minimal (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | pushmax(...) | D.pushmax(item) -> (k, v), remove and return maximal (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | pushmin(...) | D.pushmin(item) -> (k, v), remove and return minimal (key, value) pair as a | 2-tuple; but raise KeyError if D is empty. | | rebuild(...) | D.rebuild() -> None. Take compare function for rebuild dictionary. | It works without use of additional memory on a place. | | setdefault(...) | D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D. | | update(...) | D.update(E) -> None. Update D from E and F: for k in E: D[k] = E[k] | (if E has keys else: for (k, v) in E: D[k] = v). | | values(...) | D.values() -> list of D's values. | | ---------------------------------------------------------------------- | Data descriptors defined here: | | cmp | function of comparison of objects | | freeze | to block an opportunity change of object. | | ---------------------------------------------------------------------- | Data and other attributes defined here: | | __new__ = <built-in method __new__ of type object at 0x282a4aa0> | T.__new__(S, ...) -> a new object with type S, a subtype of T

Of course all of this discussion about trees in Python is fine, though there is one major problem. With minimal work, one can construct 3 values such that ((a < b < c) and (c < a)) is true.

The same problem is inherent in the standard dictionary - dict (), only roots at it, it is others. For example: class test: def __hash__(self): return random.randint(0, 1000000) The binary tree is very easy for tearing down. Therefore when any reference to it is made, blocking either on reading, or on record should be established. If it is opened iterator on the given object also blocking on reading should be established where iterator will not come to the end or while it will not be closed or destroyed. Thus it is possible to guarantee security of object. Functions of blocking are similar on pthread_rdlock_trylock, and pthread_wrlock_trylock. If blocking is impossible, exception RDLockError, WRLockError, FreezeLockError is generated. Thanks. -- Vladimir Stepanov #!/usr/local/bin/python # Initialize modules import avl import xtree import collections 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] = i """ % iterations).timeit(count) print "object xtree.xtree()", result_xtree result_rbtree = timeit.Timer(""" import collections a = collections.rbtree() for i in xrange(%d): a[i] = i """ % iterations).timeit(count) print "object collections.rbtree()", result_rbtree result_dict = timeit.Timer(""" import types a = dict() for i in xrange(%d): a[i] = i """ % iterations).timeit(count) print "object dict()", result_dict print " Dict Rbtree Xtree AVL" print "Dict %.2f %.2f %.2f %.2f" % ( float(result_dict)/result_dict, float(result_dict)/result_rbtree, float(result_dict)/result_xtree, float(result_dict)/result_avl) print "Rbtree %.2f %.2f %.2f %.2f" % ( float(result_rbtree)/result_dict, float(result_rbtree)/result_rbtree, float(result_rbtree)/result_xtree, float(result_rbtree)/result_avl) print "Xtree %.2f %.2f %.2f %.2f" % ( float(result_xtree)/result_dict, float(result_xtree)/result_rbtree, float(result_xtree)/result_xtree, float(result_xtree)/result_avl) print "AVL %.2f %.2f %.2f %.2f" % ( float(result_avl)/result_dict, float(result_avl)/result_rbtree, float(result_avl)/result_xtree, float(result_avl)/result_avl) Iterations 1000000 Repeats 10 object avl.new() 34.5930659771 object xtree.xtree() 16.2341389656 object collections.rbtree() 79.2434329987 object dict() 4.01597499847 Dict Rbtree Xtree AVL Dict 1.00 0.05 0.25 0.12 Rbtree 19.73 1.00 4.88 2.29 Xtree 4.04 0.20 1.00 0.47 AVL 8.61 0.44 2.13 1.00 Iterations 1000000 Repeats 10 object avl.new() 35.8164830208 object xtree.xtree() 18.5456049442 object collections.rbtree() 74.5128099918 object dict() 4.09129810333 Dict Rbtree Xtree AVL Dict 1.00 0.05 0.22 0.11 Rbtree 18.21 1.00 4.02 2.08 Xtree 4.53 0.25 1.00 0.52 AVL 8.75 0.48 1.93 1.00

Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" <vys@renet.ru> wrote:

...

Josiah Carlson wrote:

...

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

Such problem arises at creation of the list of timers.

I've never seen that particular use-case.

Please understand something. I believe that trees can be useful in some cases. However, I don't believe that they are generally useful enough in Python, given that we already have key,value dictionaries and sortable lists. They become even less worthwhile in Python, given the total ordering problem that I describe later in this message.

I tiresome. It so :) Sorry for that.

...

Here that I have found through Google on a line " order statistic binary tree ":

http://www.cs.mcgill.ca/~cs251/OldCourses/1997/topic20/

Yes, that link does describe what an 'order statistic tree' is. One thing to note is that you can add order statistics to any tree wih one more field on each tree node. That is, you can have your AVL or Red-Black tree, and add order statistics to it. Allowing tree['x'] to return the associated value for the key 'x' (the same as a dictionary), as well as offer the ability to do tree.select(10) to get the 10th (or 11th if one counts from 0) smallest key (or key,value), or get the 'rank' of a key with tree.rank('x').

Thanks.

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

It is sad. I did not know it. Therefore and have not understood. I have looked in Google on "python dev total ordering". On intentions to correct this problem I have not found anything. It already earlier was discussed ? -- Vladimir Stepanov

On Sat, May 06, 2006 at 03:12:11AM -0700, Josiah Carlson wrote:

"Vladimir 'Yu' Stepanov" <vys@renet.ru> wrote:

...

Josiah Carlson wrote:

...

This problem has nothing to do with dictionaries and hashing, it has to do with the fact that there may not be a total ordering on the elements of a sequence.

It is sad. I did not know it. Therefore and have not understood.

I have looked in Google on "python dev total ordering". On intentions to correct this problem I have not found anything. It already earlier was discussed ?

Not really. It has to do with how non-comparable instances compare to each other. Generally speaking, when instances aren't comparable, Python compares their type, which is actually comparing the names of types. This wouldn't be a big deal, except that:

...

...

...

str < tuple < unicode True

And you can actually compare str and unicode, so, if you have a str that is greater than the unicode, you run into this issue. With unicode becoming str in Py3k, we may not run into this issue much then, unless bytes are comparable to str, in which case we end up witht the same problems.

Actually, according to my google of "python dev total ordering", it gives me...

http://mail.python.org/pipermail/python-dev/2003-March/034169.html http://mail.python.org/pipermail/python-list/2003-March/154142.html

Which were earlier discussions on this topic, which are quite topical. The ultimate solution is to choose a total ordering on types and consider the problem solved. Then list.sort() and binary trees will work properly.

Thanks for so detailed answer. Under these references discussion is conducted is presented in the form of "so is", instead of "as it to correct". Therefore I would like to mention a question "as it to correct". In case of incomparability of types can be it is meaningful compare the identifiers compared to each concrete type. More truly on them to calculate weight which will play a direct role in case of impossibility of comparison of types. Below one of variants of the decision of this problem is resulted. To each type of data in Python to add three fields: .. int tp_id; int tp_qualifier; int tp_weight; .. Rigidly to appoint some built in and external to types identifiers (tp_id). The others receive free identifiers on their initialization. Except for that types should be classified on their basic properties - tp_qualifier. The type can be classified as: 0 = None 1 = integer (bool, int, long, etc..) 2 = float (decimal, float, etc..) 3 = math (complex, matrix may be ?? ) 4 = string (str, unicode, splice, etc..) 5 = sequence (iterators, deque, xrange, enumerate, etc..) 6 = array (tuple, list, bytes, array, etc..) 7 = dictionary (dict, defdict, etc..) 8 = set (set, etc..) 9 = file (file, socket.socket, cStringIO.StringIO) .. 127 = non qualifier (sre.*, datetime.*, ClassType, IntsenceType, etc..) It is the approximate list on which it will be convenient to classify types (in my opinion). The weight can be precisely set in structure or if be equal -1 should is calculated under the formula: ob_type->tp_weight = (ob_type->tp_qualifier<<24) + (ob_type->tp_id<<8) Thus objects with similar properties will follow one after another. A problem can make external types. But if to develop further classification, problems to arise should not. -- SY. Vladimir Stepanov

Guido van Rossum wrote:

On 5/6/06, Vladimir Yu. Stepanov <root@renet.ru> wrote: [proposing a total ordering between types]

It Ain't Gonna Happen. (From now on, I'll write this as IAGH.)

In Python 3000, we'll actually *remove* ordering between arbitrary types as a feature; only types that explicitly care to be ordered with respect to one another will be ordered. Equality tests are unaffected, x==y will simply return False if x and y are of incomparable types; but x<y (etc.) will raise an exception.

-- --Guido van Rossum (home page: http://www.python.org/~guido/) _______________________________________________ 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/vys%40renet.ru

When comparison is made like ("something" < 123), generating of exception is necessary. At sorting or use of binary trees it is not so obvious. The behavior function of comparison in this case depends on needs of the user. At present time use of redefined function is complicated. I shall give an example. By a call of a method sort for the list can give absolutely different exceptions, depending on the order of sorted values or data (thanks for David Mertz and Josiah Carlson): -----------------------------------------------------------------

...

...

[chr(255),1j,1,u't'].sort() Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: no ordering relation is defined for complex numbers [chr(255),1j,u't',1].sort() Traceback (most recent call last): File "<stdin>", line 1, in <module> UnicodeDecodeError: 'ascii' codec can't decode byte 0xff in position 0: ordinal not in range(128)

If for Python-3000 similar it will be shown concerning types str(), int(), complex() and so on, and the type of exceptions will strongly vary, it will make problematic redefinition of behavior of function of sorting. It would be quite good to create one more class of exceptions which would unify generation of mistakes at comparison of non-comparable types or data.

Guido van Rossum wrote:

On 5/11/06, Vladimir 'Yu' Stepanov <vys@renet.ru> wrote:

...

If for Python-3000 similar it will be shown concerning types str(), int(), complex() and so on, and the type of exceptions will strongly vary, it will make problematic redefinition of behavior of function of sorting.

Not really. We'll just document that sort() should only be used on a list of objects that implement a total ordering. [...]

It might be useful in some cases to have a keyword argument to sort/sorted that says to ignore exceptions arising from comparing elements, and leaves the ordering of non-comparable values undefined. -Edward

On 5/11/06, Vladimir 'Yu' Stepanov <vys@renet.ru> wrote:

If for Python-3000 similar it will be shown concerning types str(), int(), complex() and so on, and the type of exceptions will strongly vary, it will make problematic redefinition of behavior of function of sorting.

I don't see what you mean by "redefinition of behavior of function of sorting". Is this something a Python programmer might want to do? Can you give an example? On 5/16/06, Vladimir 'Yu' Stepanov <vys@renet.ru> wrote:

It will be possible it conveniently to use as exception of management by a stream, for indication of necessity to involve `.__r(eq|ne|le|lt|ge|gt|cmp)__()' a method. This kind of a class can carry out function, similarly to StopIteration for `.next()'.

There are no .__r(eq|ne|le|lt|ge|gt|cmp)__() methods, for a logical reason which you might enjoy deducing yourself...

At present time similar function is carried out with exception NotImplemented. This exception is generated in a number of mathematical operations. For this reason I ask to consider an opportunity of creation of a new class.

Can you explain this? NotImplemented isn't an exception. (NotImplementedError is, but that's something quite different.) NotImplemented has exactly one purpose in Python, as far as I can tell. What mathematical operations do you mean? -j

Vladimir, Your examples seem to indicate that you've misunderstood the change that's proposed for Python 3000. Especially this: On 5/17/06, Vladimir 'Yu' Stepanov <vys@renet.ru> wrote:

# BEGIN: Emulation python3000 if type(a) is not type(b) and ( not operator.isNumberType(a) or not operator.isNumberType(b) ): raise TypeError("python3000: not-comparable types", (a,b)) # END: Emulation python3000

Python 3000 will not do anything like this. It'll try a.__cmp__(b), and failing that b.__cmp__(a) (but imagine this using tp_ slots instead of actual Python method calls), and if both return NotImplemented, it'll throw a TypeError (rather than guess, which is what it does now). There's a lot of legacy oddness in PyObject_RichCompare() and its many helper functions; presumably they'll delete some of that, but it won't be anything you care about. Comparison with None should also continue to work as it does now, unless I missed something. -j

Josiah Carlson wrote:

And you can actually compare str and unicode, so, if you have a str that is greater than the unicode, you run into this issue. With unicode becoming str in Py3k, we may not run into this issue much then, unless bytes are comparable to str, in which case we end up witht the same problems.

Actually, according to my google of "python dev total ordering", it gives me...

http://mail.python.org/pipermail/python-dev/2003-March/034169.html http://mail.python.org/pipermail/python-list/2003-March/154142.html

Which were earlier discussions on this topic, which are quite topical. The ultimate solution is to choose a total ordering on types and consider the problem solved. Then list.sort(

Under the second reference there was a question. complex it can be partially comparable with int, long, float? In fact 1 == 1+0j?

Martin v. Löwis wrote:

Vladimir 'Yu' Stepanov wrote:

...

Yes. I understood it when resulted a set example.

...

However, as I just said, people usually don't remove items from just-sorted lists, they tend to iterate over them via 'for i in list:' .

Such problem arises at creation of the list of timers.

For a list of timers/timeout events, a priority queue is often the best data structure, which is already available through the heapq module.

It is in most cases valid so. heapq very much approaches for these purposes. The unique problem is connected with removal of an any element from the list. -- Vladimir Stepanov