No trees in the stdlib?

[João Valverde]

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. ;)