On 12/27/2010 3:05 AM, Ulrich Eckhardt wrote:
Hi!
I'm trying to solve a computational problem and of course speed and size is
important there.
Then you probably shouldn't be using CPython.
Apart from picking the right algorithm, I came across an
idea that could help speed up things and keep memory requirements down. What
I have is regions described by min and max coordinates. At first, I just
modeled these as a simple class containing two values for each axis.
There are more effective techniques for that. In game physics
collision detection systems, it's common to use axis-ordered lists
of bounding boxes to partition objects. This still works even when
the ranges overlap. Look up "I-Collide" for a classic implementation.
> Am I looking in the wrong direction? Is there some better approach?
> Please
> don't tell me to use C, as I'm specifically interested in
> learning Python,
> I'm pretty sure I could have solved the problem quickly in
> C++ otherwise.
CPython is a naive interpreter which does dictionary
lookups for every variable and attribute access. If you're doing
fast manipulation of linked data structures in CPython, performance
is going to suck.
Check out Shed Skin 0.7, which is a much faster Python
system. It's limited, but for the kind of data structure work
you're doing, all the features you should need already work.
John Nagle
In a second step, I derived this class from tuple instead of object. Some
code then moved from __init__ to __new__ and some code that modified these
objects had to be changed to replace them instead. The upside to this is
that they can be used as keys in sets and dicts, which isn't the case for
mutable types[1].
What I'm now considering is to only allow a single instance of these objects
for each set of values, similar to interned strings. What I would gain is
that I could safely compare objects for identity instead of equality. What
I'm not yet sure is how much overhead that would give me and/or how to keep
it low. The idea is to store each instance in a set and after creating a new
object I would first look up an equal object in the global set and return
that instead, otherwise add the new one.
The problem I foresee is that if I define equality as identity, this lookup
when creating will never eliminate duplicates. If I only fall back to
equality comparison for non-identical objects, I would probably sacrifice
most of the gain. If I build a dict mapping between the values and the
actual objects, I would have doubled the required memory and uselessly store
the same values twice there.
Cheers!
Uli
[1] Somebody correct me if I'm wrong, but I believe I could have defined a
hashing function for the type and thus allowed its use in a set or dict,
right? However, goofing up because you accidentally modified an object and
changed its hash value is something I don't want to risk anyway.
--
http://mail.python.org/mailman/listinfo/python-list
