Op 08-04-16 om 16:25 schreef Chris Angelico:
> On Sat, Apr 9, 2016 at 12:20 AM, Antoon Pardon
> <antoon.par...@rece.vub.ac.be> wrote:
>>> You only need ONE comparison, and the other is presumed to be its
>>> opposite. When, in the Python 3 version, would you need to compare
>>> twice?
>>
>> About 50% of the time. When I traverse the tree I go left when the
>> argument key is smaller than the node key, I go right when it is
>> greater than the node key and I have found the node I want when
>> they are equal.
>
> How about this:
>
> You have found the node if they are equal.
> Otherwise, go left if your argument is smaller than the node.
> Otherwise, go right.
>
> You don't have to do three comparisons, only two - and one of them is
> an equality, rather than an inequality, which is often cheaper.
You don't seem to understand. I only do two comparisons and no the
equality is not necesarrily cheaper.
I am talking about the difference between the following two:
if arg.key < node.key: # possible expensive computation
go_left()
elif arg.key == node.key # possible expensive computation
found_node()
else:
go_right()
and
delta = cmp(arg.key, node.key) # possible expensive computation
if delta < 0: # cheap computation
go_left()
elif delta == 0: # cheap computation
found_node()
else:
go_right()
> But
> hey. If you really can't handle the double comparison, *write your
> own* special-purpose comparison function - nobody's stopping you! It's
> just not something that exists *in the language*. If your specific
> objects need this, write it!
Sure I could do that, but it may not be worth the trouble without
language support. Just writing a cmp function is not sufficient, because
the trivial way to write it, will just hide the expense in that function.
For the moment I will probably go with Ben Finney's suggestion and go
with somekind of lru cache. So when I do one of the comparisons with
my own objects, it will do the expensive cmp-like computation behind
the scene and then return the result of the cheap computation. I just
check the cache before to see whether the result of the expensive
computation is already available.
--
Antoon Pardon
--
https://mail.python.org/mailman/listinfo/python-list
