Mailman 3 May 2006 - Python-Dev

Re: [Python-Dev] Efficient set complement and operation on large/infinite sets.
by Terry Jones 12 May '06

12 May '06

>>>>> "Raymond" == Raymond Hettinger <rhettinger(a)ewtllc.com> writes: Raymond> There's room in the world for alternate implementations of sets, Raymond> each with its own strengths and weaknesses. ... Raymond> Alternatve implementations will most likely start-off as Raymond> third-party extension modules Raymond> As for the built-in set types, I recommend leaving those alone and Raymond> keeping a API as simple as possible. Agreed. I implemented most of what I need last night - not surprisingly in less time than it took to write the original mail. Raymond> The __rand__ idea is interesting but I don't see how to implement Raymond> an equiprobable hash table selection in O(1) time -- keep in mind Raymond> that a set may be very sparse at the time of the selection. I think the rand issue is enough to make the proposal questionable. Another thing I realized which I think adds to the argument that this should be separate, is that it's not so straightforward to deal with operations on sets that have different universes. You can do it, but it's messy, not elegant, and not fun (and no-one is asking for it, not even me). This leads to a much nicer approach in which you have a separate module that provides a UniversalSet class. When you call the constructor, you tell it whatever you can about what the universe looks like: how big it is, how to generate random elements, how to exclude things, etc. This class provides a simple (a la Python set.__init__) method that hands back a set within this universe. You're then free to operate on that set, and other instances provided by UniversalSet, as usual, and you get to do complement. It's easy to imagine subclasses such as InfiniteSet, FiniteSet, etc. Python's sets are the case where nothing is known about the universe (aside from implementation details, like elements being hashable). The various different kinds of UniversalSet subclasses would provide methods according to what was known about their universes. That would clearly be a 3rd party extension. Terry

1 0

Re: [Python-Dev] [Python-3000] Questions on optional type annotations
by Neal Norwitz 12 May '06

12 May '06

On 5/11/06, Edward Loper <edloper(a)gradient.cis.upenn.edu> wrote: > Neal Norwitz wrote: > > Another benefit of this is the ability to get more info through > > introspection. Right now, you can't even find the number of arguments > > of a function implemented in C. You only know if it takes 0, 1, or > > variable # of arguments and if it accepts keywords. > > By this, do you mean that it's currently possible to distinguish these > cases (builtins that take 0 args, builtins that take 1 arg, builtins > that take varargs, builtins that take keywords) via introspection in > python? If so, could you let me know how this is done? For epydoc, > this would at least let me give a little more info when no signature is > present on the first line of the docstring. Hmm, well I only said the info was available. I didn't say it was available from Python code. :-) Actually, with the patch below the flags are available: >>> len.__flags__ 8 The flags are METH_XXX flags defined in Include/methodobject.h: #define METH_OLDARGS 0x0000 #define METH_VARARGS 0x0001 #define METH_KEYWORDS 0x0002 #define METH_NOARGS 0x0004 #define METH_O 0x0008 If you want this patch included in 2.5, feel free to ask on python-dev. I guess I'm +0 on it. This could be a trivial extension module for older versions of python. Aaaa, screw it, I copied python-dev, we'll see if anyone cares. n -- Index: Objects/methodobject.c =================================================================== --- Objects/methodobject.c (revision 45961) +++ Objects/methodobject.c (working copy) @@ -146,6 +146,12 @@ return PyString_FromString(m->m_ml->ml_name); } +static PyObject * +meth_get__flags__(PyCFunctionObject *m, void *closure) +{ + return PyInt_FromLong(m->m_ml->ml_flags); +} + static int meth_traverse(PyCFunctionObject *m, visitproc visit, void *arg) { @@ -174,6 +180,7 @@ {"__doc__", (getter)meth_get__doc__, NULL, NULL}, {"__name__", (getter)meth_get__name__, NULL, NULL}, {"__self__", (getter)meth_get__self__, NULL, NULL}, + {"__flags__", (getter)meth_get__flags__, NULL, NULL}, {0} };

1 0

PyThreadState_SetAsyncExc, PyErr_Clear and native extensions
by Gabriel Becedillas 11 May '06

11 May '06

I use PyThreadState_SetAsyncExc to stop a python thread but there are situations when the thread doesn't stop and continues executing normally. After some debugging, I realized that the problem is that PyThreadState_SetAsyncExc was called when the thread was inside a native extension, that for some reason calls PyErr_Clear. That code happens to be inside boost::python. I do need to stop the thread from executing Python code as soon as possible (as soon as it returns from a native function is also acceptable). Because we have embedded Python's VM in our product, I'm thinking of modifying PyErr_Clear() to return immediately if the thread was stopped (we determine if the thread should stop using our own functions). Example: void PyErr_Clear(void) { if (!stop_executing_this_thread()) PyErr_Restore(NULL, NULL, NULL); } Does anybody see any problem with this approach ?, Does anybody have a cleaner/better solution ? I've allready posted this in comp.lang.python a couple of days ago but got no answers, that's why I'm posting here, coz I think the only ones that could give me a solution/workaround are Python core developers. Thanks a lot.

3 2

python 2.4 and universal binaries
by Ronald Oussoren 11 May '06

11 May '06

Hi, I'd like to backport the patches I've done to the trunk regarding universal binary support for OSX and endian issues in Mac specific modules. The last set seems easy enough, all of those are clearly bugfixes. I'm not sure if the universal binary patches are acceptable for backport (and specifically the change to pyconfig.h.in) The rationale for this is simple: Apple seems to pick up a recent copy of python for every new major release of OSX (Python 2.2.x for Jaguar, Python 2.3.0 for Panther, Python 2.3.5 for Tiger) and is therefore likely to use Python 2.4.x for the next release of the OS. The official python 2.4 tree currently doesn't support building univeral binaries. Given that Apple ships a broken universal build of python 2.3 with the new intel macs I'm worrying that they won't fix this for their next OS release, which would increase the support load on the pythonmac-sig list. By adding support for universal binaries to python 2.4 we'd reduce the change for a broken python in the next OSX release. Ronald

4 3

Re: [Python-Dev] Efficient set complement and operation on large/infinite sets.
by Terry Jones 11 May '06

11 May '06

>>>>> "Guido" == Guido van Rossum <guido(a)python.org> writes: Guido> Hm... Without reading though all this, I expect that you'd be Guido> better off implementing this for yourself without attempting to pull Guido> the standard library sets into the picture (especially since sets.py Guido> is obsolete as of 2.4; set and frozenset are now built-in types). Guido> You're really after rather specialized set representations. I've Guido> done this myself and as long as you stick to solving *just* the Guido> problem at hand, it's easy. If you want a general solution, it's Guido> hard... I certainly would be better off in the short term, and probably the long term too. It's likely what I'll do in any case as it's much, much quicker, I only need a handful of the set operations, and I don't need to talk to anyone :-) I don't think I'm proposing something specialized. Set complement is something one learns in primary school. It's just difficult to provide in general, as you say. Aside from my own itch, which I know how to scratch, my question is whether it's worth trying to work this into Python itself. Sounds like not. Terry

2 1

Re: [Python-Dev] Efficient set complement and operation on large/infinite sets.
by Terry Jones 11 May '06

11 May '06

A quick followup to my own posting: I meant to say something about implementing __rand__() and pop(). I'd either add another optional function argument to the constructor. It would return a random element from the universe. Then for __rand__() and pop(), you'd call until it (hopefully!) returned something not excluded. Or, do something non-random, like return a random (non-excluded) integer. Or, just raise an exception. I think I prefer the extra argument approach, where the docs state clearly that you can expect to wait longer and longer for random elements as you empty a finite inverted set. I prefer this approach because getting a random element from a set is something you really should be able to do. Just raising an exception is the cleanest and clearest choice. One thing I certainly would not consider is trying to mess around with the excluded set (which may in any case be empty) to figure out a suitable return type. And yes, I agree in advance, adding 5 new optional arguments to the set() constructor isn't pretty. Is the added functionality is worth it? Terry

1 0

Efficient set complement and operation on large/infinite sets.
by Terry Jones 11 May '06

11 May '06

I'm about to write some code to manage sets, and wanted to float a few thoughts here because I have various ideas about how to implement what I want to do, and I think one of them could be done by changing Python's set type in useful and backward compatible way. Apologies if this is discussed in the archives. I didn't see it. My original motivation is a need to work efficiently with very large sets, let's say 10M elements. In some cases, you can operate on a set without needing to explicitly represent all its elements. For example, if my set is the Universal (U) set, then X in U, should return True. If my set is U and I union it with any other set, it is unchanged, etc. By also maintaining a finite set of things that are _not_ in my large set, I can do other operations efficiently. E.g., calling U.remove(X) would _add_ X to the set of elements that were known not to be in the big set that you were trying to represent efficiently. In most cases, such a set class would simply do the opposite/inverse operation on its finite exclusion set. While it's convenient to warm up by talk about the infinite Universal set, we could just as easily be talking about arbitrarily large finite sets. There are some examples below. Another way to discuss the same thing is to talk about set complements. It would be nice to be able to complement (or invert) a set. Once you did so, you might have an infinite set on your hands, but as the last paragraph argues, you can still operate on an infinite set efficiently. Naturally, you can't fully enumerate it, or take its size. I think that giving Python sets the ability to handle complementarity would have some nice uses - and that these go well beyond the particular thing that I need right now. For example, suppose you want to represent the set of all floating point numbers. You just create an empty set and complement it. Then you can test it as usual, and begin to exclude things from it. Or if you have a system with 10M objects and you need to support operations on these objects via a query language that lets the user type "not X" where X is a set of objects, there is a natural and efficient way (constant time) to execute the query - you just mark the set as being inverted (complemented). If I were going to implement the above by changing Python's built in set type, here's what I think I'd do: Add four optional keyword arguments to the set constructor: - invert=False - universalSet=None - universalSetSize=None - universeExclusionFunc=None invert is just a flag, indicating the sense of the set. If inverse is False: the set behaves exactly as a normal Python set and the other three new arguments are ignored. If inverse is True: universalSet represents the universal set. If it is None, then the universal set is infinite. Otherwise, universalSet is an iterable. The implementation should not call this iterable unless it's unavoidable, on the presumption that if the programmer wanted to operate directly on the contents of this iterable, they'd be doing it in a conventional fashion (e.g., with a normal set). The universalSetSize, used for len() calculations, is the number of elements in universalSet, if known & if finite. The universeExclusionFunc can be called with a single element argument to see if the element should be considered excluded from the universalSet. This may seem like a weird idea, but it's the key to flexibility and efficiency. In an invert=True set, the code would use the normal set content as a mutable set of objects that are not in the universe, as described above, but would, in addition, use the universeExclusionFunc (if defined) to identify elements not in the set (because they are not in the universe), and thus avoid the use of the expensive (or infinite) universalSet. Note that an inverted (or normal) set can be inverted by simply setting invert=False, so this requires a new invert() method (which could be triggered by the use of something like 'not' or '!' or '~'). In this case, an inverted set becomes a normal Python set. The elements represented by universeExclusionFunc remain invalid - they are simply not in the universe (and, if deemed sensible, this could be sanity checked in add()). If it's not clear, when a set is inverted, any iterable given to __init__, (i.e., the iterable argument in the normal case of constructing a Python set), is just treated as usual (but in this case will be taken to represent things not in the set initially). Here are some examples of usage: 1. Suppose you want to work with the set of integers [0, 100000000) and that initially your set is all such integers. You could create this set via: S = set(invert=True, universalSet=xrange(100000000), universalSetSize=100000000, universeExclusionFunc=(lambda x: x >= 100000000) This has the intended effect, is efficient, and no-one need call the iterator. You can (I think) do everything you could do with a normal set (including inverting it). If the user happens to want to list all the elements in the set, that's their business and they can do it, except in the case where universalSet=None, in which case I would raise an exception. 2. Suppose you wanted to represent the set of all floating point numbers > 0.0 that were not integers. You'd do this via: def excludeFunc(f): try: f = float(f) except ValueError: return True if f <= 0.0: return True if f - math.floor(f) == 0.0: return True return False S = set(invert=True, universeExclusionFunc=excludeFunc) 3. Let's say you wanted to work with the set of all IP addresses, as represented by lists of 4 integers, but that you want to exclude 127.0.0.1, and all the reserved RFC1918 address blocks def excludeFunc(ip): # Insert code to check type and length. if (ip == [127, 0, 0, 1]): return True if (ip[0] == 10 or (172, 16, 0, 0) <= ip <= (172, 31, 255, 255) or (191, 168, 0, 0) <= ip <= (192, 168, 255, 255)): return True # Insert code to check all bytes in [0..255], return True if not. return False S = set(invert=True, universeExclusionFunc=excludeFunc) It's pretty easy to think of other examples of wanting to efficiently use big sets, or to use small sets and then needing to complement them and operate efficiently on their large complements. One reaction to these examples might be that it's no big deal to write your own code to, say, manage sets of IP addresses. I think that's not so easy to do efficiently if the set is massive (and you'd end up keeping track of the complement or using offline storage). Doing it as suggested above makes it simple, and once you call the constructor, you just do normal Python set operations. This suggestion goes a little way towards giving "continuous" sets. One way to categorize set support is: A. Only support finite sets. B. Provide category A but also support infinite sets where at least one of the set and its complement is finite. C. Provide category B but also allow for the case where a set and its complement may both be infinite. Thus I am proposing something that would take set support in Python from category A to category B. Implementing B efficiently is provably possible since all operations are done on either a set or its complement, whichever is known to be finite, and Python already handles those operations (via its category A support). The downsides that I see at the moment are: 1. Two new exceptions that can arise. These only happen on sets that are in the inverted state, and only when the universal set is infinite: - You try to enumerate an infinite set. - You call len() on an infinite set. 2. Operations on regular sets get slightly slower because virtually all set operations would need to test the invert flag. So that's an extra Boolean test on every set operation. I don't think the implementation is too hard - the Python sets.py code is very clean - though there may be gotchas. Anyway, I wanted to see what people think of this before I go ahead and solve my actual problem. If the above is considered potentially worthwhile to Python, I can work on adapting sets.py. If not, I'll do the faster and simpler thing and write my own class. Regards, Terry

2 1

Re: [Python-Dev] total ordering.
by Delaney, Timothy (Tim) 11 May '06

11 May '06

Edward Loper wrote: > 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. Why? Far better to use a key (or cmp if you really want) that imposes a total (or at least consistent) ordering. Otherwise sorting is random. Tim Delaney

1 0

nag, nag -- 2.5 open issues
by Neal Norwitz 11 May '06

11 May '06

If you are addressed on this message, it means you have open issues that need to be resolved for 2.5. Some of these issues are documentation, others are code issues. This information comes from PEP 356. The best way to get me to stop bugging you is to close out these tasks. :-) Note the next alpha is coming up in a week or two, so now is a good time to finish these. Who is the owner for getting new icons installed with the new logo? Georg did some work, but it seems like a lot more work needs to be done to get them installed on all platforms. This will be deferred unless someone makes it happen. Code issues: +++++++++++ Fred, Fredrik, Martin: xmlplus/xmlcore situation re: ElementTree Jeremy: AST compiler issues Philip, AMK: add wsgiref to stdlib -- is this happening? We should really try to get these resolved soon, especially the XML issue since that could result in some sort of API change. The AST issues should just be bug fixes AFAIK. Documentation missing: +++++++++++++++++++ Fredrik: ElementTree Gerhard: pysqlite Martin: msilib -- Martin/Andrew is this done? Thomas: ctypes I think we heard from Gerhard and Thomas about their doc plans. Fredrik, are you planning to get ET doc into the python docs? Let me know if there's anything I missed. If you don't expect to have time to finish these tasks, then it's your job to find someone else who will (and it would be good to reply to this message). Update the PEP or tell me and I'll update the PEP. n

2 1

2.5 open issues
by Neal Norwitz 10 May '06

10 May '06

If you are addressed on this message, it means you have open issues that need to be resolved for 2.5. Some of these issues are documentation, others are code issues. This information comes from PEP 356. The best way to get me to stop bugging you is to close out these tasks. :-) Who is the owner for getting new icons installed with the new logo? Code issues: +++++++++++ Fred, Fredrik, Martin: xmlplus/xmlcore situation re: ElementTree Jeremy: AST compiler issues We should really try to get these resolved soon, especially the XML issue since that could result in some sort of API change. The AST issues should just be bug fixes AFAIK. Documentation missing: +++++++++++++++++++ Fredrik: ElementTree Gerhard: pysqlite Martin: msilib Thomas: ctypes Thomas, I know you checked in some ctypes docs. Is that everything or is there more coming? It seemed pretty short given the size of ctypes. If you don't expect to have time to finish these tasks, then it's your job to find someone else who will. n

11 19