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/
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
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
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
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
>>>>> "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
>>>>> "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
>>>>> "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
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
[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
