Mailman 3 July 2009 - Python-ideas

Heap data type
by Facundo Batista Dec. 7, 2009

Dec. 7, 2009

Using the module heapq, I found that it's not easy to use. Or, at least, that it could be straightforward to use. My main issue is that for correct usage: - user should provide an external list, that shouldn't use for anything else to don't break the invariant - to alter the heap queue, a bunch of functions must be used, passing always the external list I think that changing "external list" for "internal attribute", and "bunch of functions " for "methods", it will leave the module easier to use, safer, and more object oriented. So, I basically coded it. What do you think about including this class in the heap module? """ class Heap(object): '''Maintains a heapified list, always conserving the invariant. Heaps are arrays for which heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2] for all k, counting elements from zero. ''' def __init__(self, iterable=None): '''Initializes the heap from any iterable. >>> Heap([1, 2]) Heap([1, 2]) >>> Heap([]) Heap([]) >>> Heap() Heap([]) >>> Heap((1, 2, 3)) Heap([1, 2, 3]) >>> Heap(x**2 for x in range(3)) Heap([0, 1, 4]) ''' if iterable is None: self._queue = [] else: self._queue = list(iterable) heapq.heapify(self._queue) def __repr__(self): return "Heap(%s)" % self._queue def push(self, item): '''Push the item to the heap queue. >>> h = Heap() >>> h.push(5) >>> h.push(4) >>> h.push(3) >>> h.push(2) >>> h.push(1) >>> h.push(0) >>> h Heap([0, 2, 1, 5, 3, 4]) ''' heapq.heappush(self._queue, item) def pop(self): '''Pop one item from the heap queue. >>> h = Heap([0, 2, 1, 5, 3, 4]) >>> h.pop() 0 >>> h.pop() 1 >>> h.pop() 2 >>> h.pop() 3 >>> h.pop() 4 >>> h.pop() 5 >>> h Heap([]) >>> h.pop() Traceback (most recent call last): ... IndexError: index out of range ''' return heapq.heappop(self._queue) def pushpop(self, item): '''Push the item and pop one from the heap queue. Note that this method is more efficient than calling both push() and pop() separately. >>> h = Heap() >>> h.pushpop(7) 7 >>> h.push(5) >>> h.push(4) >>> h.push(3) >>> h.pushpop(7) 3 >>> h.pushpop(7) 4 >>> h Heap([5, 7, 7]) ''' return heapq.heappushpop(self._queue, item) def replace(self, item): '''Pop one item and push the received one into the heap queue Note that this method is more efficient than calling both pop() and push() separately. >>> h = Heap() >>> h.replace(3) Traceback (most recent call last): ... IndexError: index out of range >>> h.push(7) >>> h.replace(2) 7 >>> h Heap([2]) >>> h.push(3) >>> h Heap([2, 3]) >>> h.replace(1) 2 >>> h.replace(9) 1 >>> h Heap([3, 9]) ''' return heapq.heapreplace(self._queue, item) """ Regards, -- . Facundo Blog: http://www.taniquetil.com.ar/plog/ PyAr: http://www.python.org/ar/

11 14

Python Bytecode Verifier
by Kornél Pál Sept. 20, 2009

Sept. 20, 2009

Hi, I've created a Python Bytecode Verifier in Python. I'm not a Python guru so I borrowed coding patterns from C/C++. I also created this with C portability in mind. The only reason I used Python was to experiment with Python and was easier to morph code during development. If this program were ported to C it would only need 8 bytes per opcode (some additional storage to track blocks) and a single pass. I haven't found backward jumps to previously unused code in any compiled Python code but it can easily be supported. In that case some more partial passes are required. I also was able to successfully verify all Python files in the Python-2.5.2 source package. The verification algorythm should be quite complete but I may have missed some limitations of the interpreter that could be checked by the verifier as well. The ability to create this verfier proved that although Python bytecode is designed for a dynamically typed interpreter, is still easily verifiable. I am willing port this code C but only in the case if there is any chance to be included in Python. I believe that Python in general would benefit having the ability to safely load .pyc files and create code objects on the fly. Both Java and .NET have the ability to safely load compiled byte code. .NET Framework, just like Python also has the ability to create and execute new code at run-time. You may feel that enabling closed source applications and/or creating a multi-language runtime would hurt Python but both of these have contributed to the success of Java (both the language and the runtime). Kornél

2 2

os.listdir with current working directory as default
by Tarek Ziadé Aug. 1, 2009

Aug. 1, 2009

Hello, A very small change: what about making the path argument optional for os.listdir ? and use the current working directory if not provided. listdir(...) listdir(path=None) -> list_of_strings Return a list containing the names of the entries in the directory. path: path of directory to list. If path is None, os.getcwd() is used. The list is in arbitrary order. It does not include the special entries '.' and '..' even if they are present in the directory. Cheers Tarek -- Tarek Ziadé | http://ziade.org

11 18

Changing the default install location, script versioning (Packages and PEP 370)
by Jesse Noller July 25, 2009

July 25, 2009

So, I've finally been able to kick my python 2.5 boat anchor, and I'm now relishing in the delightful future of 2.6. Two things struck me though, digging into PEP 370's (per user site-packages) behavior. The first is this - when you install a package (say, pip) into the .local directory via the --user command, the package ends up in the correct lib directory; but the binary get dropped into ./local/bin - this seems wrong. The reason being, is that what if I also have python 2.7 (which i do) installed, as well as python 3.1 and the release-which-will-not-be-named (3.0) - if I install that same package into one of the other versions, a new binary would be written with the same name - a script-pythonversion might also be installed, but the fact that the original script was overwritten seems broken to me. I think the "best" fix for this is to make the bin/ directory mirror the lib layout - each version would get it's own bin directory: .local/ bin/ python2.6/ python3.1/ lib/ python2.6/ python3.1/ Of course, doing this begs the question - why have /bin and /lib be top-level directories, instead favoring a layout which looks like: .local/ python2.6/ bin/ lib/ The data and doc directories which some packages might include should follow the same convention, to avoid conflicts in those directories as well. The second behavior is more of a "man I wish for a unicorn" type of thing - I think that --user should be removed, and by removed, I mean made the default action when "python setup.py install" is invoked. Users should need to instead pass in a --global flag to alter the behavior to install into the system's site-packages and bin directories. The reason is simple - installation to the global site is typically a super-user task, and can side-effect all users, it's growing into more of a no-no as more OS vendors grow to rely on the packaged/included versions of python. .002 cents jesse

9 21

universal set object for use in set manipulation
by Andy Kish July 25, 2009

July 25, 2009

Hi all, I think the addition of a universal set object would be a nice touch for python sets. Manipulation of collections of sets becomes much easier with it. Right now, certain operations are easy because empty sets are easy to create while the dual operation requires special cases: set_union = set() for s in sets: set_union |= s # this doesn't work set_intersection = set(???) for s in sets: set_intersection &= s Instead you have to do something contorted like: if len(sets) == 0: set_intersection = set() else: sets_i = iter(sets) set_intersection = sets_i.next() for s in sets: set_intersection &= s Implementation of a universal set would be pretty trivial. Trails of EasyExtend [1] has an implementation (albeit used a bit differently) that's basically the entirety of what's needed. The above intersection case would end up looking something like: set_intersection = set.universal() for s in sets: set_intersection &= s Thoughts? I'm happy to write the patch myself if people like this idea. Thanks, Andy Kish. [1] http://fiber-space.de/wordpress/?p=322

14 20

Re: [Python-ideas] universal set object for use in set manipulation
by Terry Jones July 25, 2009

July 25, 2009

>>>>> "Nick" == Nick Coghlan <ncoghlan(a)gmail.com> writes: Nick> Greg Ewing wrote: >> Andy Kish wrote: >> >>> It's really annoying to having appropriate identity element for >>> union built in while missing the *correct* identity element for >>> intersection. >> >> What would >> >> for x in set.universal(): >> ... >> >> do? Nick> Raise an exception, just like a signalling NaN in decimal. Agreed. The code I stuck on PyPI today raises InfiniteSetError on __len__ and __iter__. Nick> An expanded set concept with support for complementary set Nick> definitions is definitely something that should cook on PyPI for a Nick> while though. Just to repeat the URL: http://pypi.python.org/pypi/compset/0.1 It's had exactly zero downloads :-) Terry

2 1

Re: [Python-ideas] universal set object for use in set manipulation
by Terry Jones July 24, 2009

July 24, 2009

>>>>> "Terry" == Terry Reedy <tjreedy(a)udel.edu> writes: Terry> Did you register a module with PyPI? OK, I put my original set code into http://pypi.python.org/pypi/compset/0.1 It's just a quick hack, but it works. I didn't implement all the ideas I suggested in http://mail.python.org/pipermail/python-dev/2006-May/064977.html (e.g., universeExclusionFunc) but they'd be easy to add. Hopefully someone can take that code as a starting point for a more fully fleshed out package. The test suite could do with some love too. Terry

1 0

Re: [Python-ideas] universal set object for use in set manipulation
by Terry Jones July 24, 2009

July 24, 2009

>>>>> "Terry" == Terry Reedy <tjreedy(a)udel.edu> writes: Terry> Terry Jones wrote: >> See also this thread: >> >> http://mail.python.org/pipermail/python-dev/2006-May/064977.html >> >> I implemented some of what I was proposing there (in Python though, not C), >> and am happy to send people the code if there's any interest. [snip] Terry> Did you register a module with PyPI? No. Terry> In any case, it seems to me that adding a 'universal set' to the set Terry> class does not work. On the otherhand, a separate set-complement Terry> class (which I am guessing is what you did) should work fine as far Terry> as it goes. Each instance would have normal set as its data member, Terry> and operations on complements and mixed operations would be defined Terry> in terms of operations on sets. A universal set would then be an Terry> instance with an empty set for a complement. Yes, that's all exactly what I did. I'll clean it up a little and post it somewhere, PyPI I guess. BTW, in my original posting I was wondering about this being added to Python as a generalization of the set type. After the discussion in the above thread and thinking through the various oddities it would introduce, I also concluded that would be a mistake - there's just too much that's a bit weird. Raymond is right that a strong virtue of the current set module is its simplicity. It's not worth blowing that so as to add a more general behavior that very few people will ever use. But it would be a nice 3rd party module. Terry

1 0

Proposed convenience functions for re module
by Steven D'Aprano July 24, 2009

July 24, 2009

Following the thread "Experiment: Adding "re" to string objects.", I would like to propose the addition of two convenience functions to the re module: def multimatch(s, *patterns): """Do a re.match on s using each pattern in patterns, returning the first one to succeed, or None if they all fail.""" for pattern in patterns: m = re.match(pattern, s) if m: return m def multisearch(s, *patterns): """Do a re.search on s using each pattern in patterns, returning the first one to succeed, or None if they all fail.""" for pattern in patterns: m = re.search(pattern, s) if m: return m The rationale is to make the following idiom easier: m = re.match(s, pattern1) if not m: m = re.match(s, pattern2) if not m: m = re.match(s, pattern3) if not m: m = re.match(s, pattern4) if m: m.group() which will become: m = re.multimatch(s, pattern1, pattern2, pattern3, pattern4) if m: m.group() Is there any support or objections to this proposal? Any comments? -- Steven D'Aprano

14 28

Re: [Python-ideas] universal set object for use in set manipulation
by Raymond Hettinger July 24, 2009

July 24, 2009

[Andy Kish] > set_intersection = set.universal() > for s in sets: > set_intersection &= s -1 This complicates the API and the implementation for very little benefit (saving you from writing a tiny, clear helper function for an uncommon use case). Currently, sets enjoy a near zero learning curve. That would be lost by adding set.universal() whose semantics are not immediately obvious -- for example, with s=set.universal() what is the meaning of list(s) or frozenset(s) or s.pop(); what is its repr value; and what is s^set('abc') or s-set('abc') or other operations? You may be able to come-up with definitions that work, but those won't be intuitive to most users. Raymond

2 1