Miles Kaufmann wrote:
João Valverde wrote:
To answer the question of what I need the BSTs for, without getting
into too many boring details it is to merge and sort IP blocklists,
that is, large datasets of ranges in the form of (IP address, IP
address, string). Originally I was also serializing them in a binary
format (but no more after a redesign). I kept the "merge and sort"
part as a helper script, but that is considerably simpler to implement.
...
As an anecdotal data point (honestly not trying to raise the "Python
is slow" strawman), I implemented the same algorithm in C and Python,
using pyavl. Round numbers were 4 mins vs 4 seconds, against Python
(plus pyavl). Even considering I'm a worse Python programmer than C
programmer, it's a lot. I know many will probably think I tried to do
"C in Python" but that's not the case, at least I don' t think so.
Anyway like I said, not really relevant to this discussion.
What format were you using to represent the IP addresses? (Is it a
Python class?) And why wouldn't you use a network address/subnet mask
pair to represent block ranges? (It seems like being able to
represent ranges that don't fit into a subnet's 2^n block wouldn't be
that common of an occurrence, and that it might be more useful to make
those ranges easier to manipulate.)
I was using a bytes subclass. I'm not free to choose CIDR notation,
range boundaries must be arbitrary.
One of the major disadvantages of using a tree container is that
usually multiple comparisons must be done for every tree operation.
When that comparison involves a call into Python bytecode (for custom
cmp/lt methods) the cost can be substantial. Compare that to Python's
hash-based containers, which only need to call comparison methods in
the event of hash collisions (and that's hash collisions, not hash
table bucket collisions, since the containers cache each object's hash
value). I would imagine that tree-based containers would only be
worth using with objects with comparison methods implemented in C.
I would flip your statement and say one of the advantages of using trees
is that they efficiently keep random input sorted. Obviously no
algorithm can do that with single comparisons. And not requiring a hash
function is a desirable quality for non-hashable objects. There's a
world beyond dicts. :)
I profiled the code and indeed the comparisons dominated the execution
time. Trimming the comparison function to the bare minimum, a single
python operation, almost doubled the program's speed.
Not that I'm trying to be an apologist, or reject your arguments; I
can definitely see the use case for a well-implemented, fast
tree-based container for Python. And so much the better if, when you
need one, there was a clear consensus about what package to use (like
PIL for image manipulation--it won't meet every need, and there are
others out there, but it's usually the first recommended), rather than
having to search out and evaluate a dozen different ones.
Thanks, and I'm not trying to start a religion either. ;)
--
http://mail.python.org/mailman/listinfo/python-list
