Ben Finney writes:
> The ‘cmp’ implementation must decide *at least* between three
> conditions... The implementation of ‘__lt__’ and the implementation
> of ‘__eq__’ each only need to decide two conditions (true, false).
> If you're saying the latter implementation is somehow *more* expensive
>
Antoon Pardon :
> And when I need some personal object as a key, I can avoid the
> duplication by using some kind of cmp cache when I implement __lt__
> and family.
Yes, that's what you can do in rare, extreme cases where key comparison
takes a long time. For caching, you will simply need to requ
Op 09-04-16 om 17:31 schreef Chris Angelico:
> On Sun, Apr 10, 2016 at 1:24 AM, Antoon Pardon
> wrote:
>>
>> So? I need a structure that can easily give me an answer to the
>> following: Given key1 and key2 what are the the keys between them
>> with their corresponding values. As long as a dict ca
On Sat, Apr 9, 2016, at 07:49, Ben Finney wrote:
> I find that a dubious claim.
>
> The ‘cmp’ implementation must decide *at least* between three
> conditions: less-than, equal-to, greater-than. That is *at least* two
> inflection points.
Yes, but in a sequence it can decide that at each element,
On Sun, Apr 10, 2016 at 1:24 AM, Antoon Pardon
wrote:
> Op 09-04-16 om 16:41 schreef Chris Angelico:
>
>>
>> In this case, you're likely to end up with large branches of your tree
>> that have the same prefix. (And if you don't, your iterations are all
>> going to end early anyway, so the comparis
Op 09-04-16 om 16:41 schreef Chris Angelico:
>
> In this case, you're likely to end up with large branches of your tree
> that have the same prefix. (And if you don't, your iterations are all
> going to end early anyway, so the comparison is cheap.) A data
> structure that takes this into account
Antoon Pardon :
> Now this probably is not a problem most of the times, but when you
> work with tree's this kind of comparison to make a three way decision
> happens often and the lower you descend in the tree, the close your
> argument will be with the keys of the nodes you visit, making it more
On Sun, Apr 10, 2016 at 12:25 AM, Antoon Pardon
wrote:
> Let me give you an artifical example to show what can happen. The keys are all
> iterables of equal lengths with integers as elements.
>
> Then this could be the cmp function:
>
> def cmp(ob1, ob2):
> itr1 = iter(ob1)
> itr2 = iter(o
Op 09-04-16 om 13:49 schreef Ben Finney:
> Antoon Pardon writes:
>
>> 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 expensi
Antoon Pardon writes:
> 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.k
Op 08-04-16 om 16:25 schreef Chris Angelico:
> On Sat, Apr 9, 2016 at 12:20 AM, Antoon Pardon
> 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 travers
Ian Kelly :
> On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa wrote:
>> Ian Kelly :
>>
>>> That's fine for those operations and probably insert, but how do you
>>> search an AVL tree for a specific key without also using __eq__?
>>
>> Not needed:
>>
>>
On Fri, Apr 8, 2016 at 10:33 AM, Marko Rauhamaa wrote:
> Ian Kelly :
>
>> That's fine for those operations and probably insert, but how do you
>> search an AVL tree for a specific key without also using __eq__?
>
> Not needed:
>
> ===
Ian Kelly :
> That's fine for those operations and probably insert, but how do you
> search an AVL tree for a specific key without also using __eq__?
Not needed:
if key < node.key:
look_right()
elif node.key < key:
On Sat, Apr 9, 2016 at 12:22 AM, Ian Kelly wrote:
>> seq1 == seq2
>> seq1 < seq2
>>
>> 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?
>
> When there are three possible code paths depending on the res
On Fri, Apr 8, 2016, at 10:08, Chris Angelico wrote:
> seq1 == seq2
> seq1 < seq2
>
> 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?
== might be just as expensive as the others, particularly if the
se
On Sat, Apr 9, 2016 at 12:20 AM, Antoon Pardon
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 smalle
On Fri, Apr 8, 2016 at 8:08 AM, Chris Angelico wrote:
> On Fri, Apr 8, 2016 at 11:31 PM, Antoon Pardon
> wrote:
>> Doing it as follows:
>> seq1 < seq2
>> seq2 < seq1
>>
>> takes about 110 seconds.
>>
>>
>> Doing it like this:
>> delta = cmp(seq1, seq2)
>> delta < 0
>> delta >
Op 08-04-16 om 15:52 schreef Marko Rauhamaa:
> Antoon Pardon :
>
>> Well having a list of 1000 Sequence like object. Each sequence
>> containing between 1 and 100 numbers. Comparing each sequence
>> to each other a 100 times. I get the following results.
>>
>> Doing it as follows:
>> seq1 < seq
Op 08-04-16 om 16:08 schreef Chris Angelico:
> On Fri, Apr 8, 2016 at 11:31 PM, Antoon Pardon
> wrote:
>> Doing it as follows:
>> seq1 < seq2
>> seq2 < seq1
>>
>> takes about 110 seconds.
>>
>>
>> Doing it like this:
>> delta = cmp(seq1, seq2)
>> delta < 0
>> delta > 0
>>
>> ta
On Fri, Apr 8, 2016 at 3:23 AM, Steven D'Aprano wrote:
> On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:
>
>> Antoon Pardon :
>>
>>> In python2 descending the tree would only involve at most one
>>> expensive comparison, because using cmp would codify that comparison
>>> into an integer which w
On Fri, Apr 8, 2016 at 11:31 PM, Antoon Pardon
wrote:
> Doing it as follows:
> seq1 < seq2
> seq2 < seq1
>
> takes about 110 seconds.
>
>
> Doing it like this:
> delta = cmp(seq1, seq2)
> delta < 0
> delta > 0
>
> takes about 50 seconds.
Why are you comparing in both direction
Antoon Pardon :
> Well having a list of 1000 Sequence like object. Each sequence
> containing between 1 and 100 numbers. Comparing each sequence
> to each other a 100 times. I get the following results.
>
> Doing it as follows:
> seq1 < seq2
> seq2 < seq1
>
> takes about 110 seconds.
>
> D
Op 08-04-16 om 09:47 schreef Ben Finney:
> Antoon Pardon writes:
>
>> But it was already working and optimized. The python3 approach forces
>> me to make changes to working code and make the performance worse.
> Yes, changing from Python 2 to Python 3 entails changing working code,
> and entails d
Steven D'Aprano :
> I would be stunned if tuple comparisons with only a handful of values
> were slow enough that its worth caching their results with an
> lru_cache. But try it, and see how you go.
There are two ways your Python program can be slow:
* You are doing something stupid like an O(e
On Fri, 8 Apr 2016 05:45 pm, Antoon Pardon wrote:
> Op 07-04-16 om 23:08 schreef Ben Finney:
>> Antoon Pardon writes:
>>
>>> With this method I have to traverse the two tuples almost always
>>> twice. Once to find out if they are equal and if not a second time to
>>> find out which is greater.
>>
On Fri, 8 Apr 2016 05:35 pm, Antoon Pardon wrote:
> Op 08-04-16 om 00:21 schreef Chris Angelico:
>> On Fri, Apr 8, 2016 at 6:56 AM, Antoon Pardon
>> wrote:
>>> That solution will mean I will have to do about 100% more comparisons
>>> than previously.
>> Try it regardless. You'll probably find tha
On Fri, 8 Apr 2016 06:34 pm, Marko Rauhamaa wrote:
> Antoon Pardon :
>
>> In python2 descending the tree would only involve at most one
>> expensive comparison, because using cmp would codify that comparison
>> into an integer which would then be cheap to compare with 0. Now in
>> python3, I may
Marko Rauhamaa writes:
> With AVL trees, it's easier to be convinced about worst-case
> performance.
I'd have thought the main reason to use AVL trees was persistence, so
you could have multiple slightly different trees sharing most of their
structures.
> It is more difficult to see the potentia
Antoon Pardon :
> In python2 descending the tree would only involve at most one
> expensive comparison, because using cmp would codify that comparison
> into an integer which would then be cheap to compare with 0. Now in
> python3, I may need to do two expensive comparisons, because there is
> no
Antoon Pardon writes:
> Op 07-04-16 om 23:08 schreef Ben Finney:
> > You are essentially describing the new internal API of comparison
> > operators. That's pretty much unavoidable.
>
> And nobody thought about this kind of cases
I'm quite confident the API changes were thought about by many peo
Antoon Pardon writes:
> But it was already working and optimized. The python3 approach forces
> me to make changes to working code and make the performance worse.
Yes, changing from Python 2 to Python 3 entails changing working code,
and entails different implementations for some things.
As for
Op 07-04-16 om 23:08 schreef Ben Finney:
> Antoon Pardon writes:
>
>> With this method I have to traverse the two tuples almost always
>> twice. Once to find out if they are equal and if not a second time to
>> find out which is greater.
> You are essentially describing the new internal API of com
Paul Rubin :
> Marko Rauhamaa writes:
>> On the surface, the garbage collection scheme looks dubious, but
>> maybe it works perfect in practice.
>
> It looked suspicious at first glance but I think it is ok. Basically
> on at most every timeout event (scheduling, expiration, or
> cancellation), i
On Fri, Apr 8, 2016 at 5:35 PM, Antoon Pardon
wrote:
> Op 08-04-16 om 00:21 schreef Chris Angelico:
>> On Fri, Apr 8, 2016 at 6:56 AM, Antoon Pardon
>> wrote:
>>> That solution will mean I will have to do about 100% more comparisons
>>> than previously.
>> Try it regardless. You'll probably find
Op 08-04-16 om 00:21 schreef Chris Angelico:
> On Fri, Apr 8, 2016 at 6:56 AM, Antoon Pardon
> wrote:
>> That solution will mean I will have to do about 100% more comparisons
>> than previously.
> Try it regardless. You'll probably find that performance is fine.
> Don't prematurely optimize!
>
> C
Marko Rauhamaa writes:
> On the surface, the garbage collection scheme looks dubious, but maybe
> it works perfect in practice.
It looked suspicious at first glance but I think it is ok. Basically on
at most every timeout event (scheduling, expiration, or cancellation),
it does an O(n) operation
Terry Reedy :
> On 4/8/2016 12:22 AM, Marko Rauhamaa wrote:
>> The issue is known. It has been tackled with a kind of a "garbage
>> collection" scheme:
>>
>> https://bugs.python.org/issue22448>
>
> and fixed 1 1/2 years ago.
On the surface, the garbage collection scheme looks dubious, but may
On 4/8/2016 12:22 AM, Marko Rauhamaa wrote:
Paul Rubin :
Marko Rauhamaa writes:
Guido chose a different method to implement timers for asyncio. He
decided to never remove canceled timers.
Only initially. He approved a change immediately when presented with a
concrete problem.
Oh my, th
On 4/7/2016 3:32 PM, Marko Rauhamaa wrote:
I use AVL trees to implement timers. You need to be able to insert
elements in a sorted order and remove them quickly.
Guido chose a different method to implement timers for asyncio. He
decided to never remove canceled timers.
In 3.5.1, asyncio.base_
Ian Kelly :
> On Apr 7, 2016 10:22 PM, "Marko Rauhamaa" wrote:
>> The keys are expiry times. You could use numbers or you could use
>> datetime objects.
>
> Yes, but why would you want to use both?
I was never talking about mixing key types. I was simply reacting (out
of context) to a suggestion
On Apr 7, 2016 10:22 PM, "Marko Rauhamaa" wrote:
>
> Ian Kelly :
>
> > On Thu, Apr 7, 2016 at 1:32 PM, Marko Rauhamaa wrote:
> >> I use AVL trees to implement timers. You need to be able to insert
> >> elements in a sorted order and remove them quickly.
> >
> > Why would AVL trees implementing ti
Paul Rubin :
> Marko Rauhamaa writes:
>> Guido chose a different method to implement timers for asyncio. He
>> decided to never remove canceled timers.
>
> Oh my, that might not end well. There are other approaches that don't
> need AVL trees and can remove cancelled timers, e.g. "timer wheels" a
Ian Kelly :
> On Thu, Apr 7, 2016 at 1:32 PM, Marko Rauhamaa wrote:
>> I use AVL trees to implement timers. You need to be able to insert
>> elements in a sorted order and remove them quickly.
>
> Why would AVL trees implementing timers ever need non-numeric keys
> though?
>
> It seems to me that
On 07/04/2016 21:56, Antoon Pardon wrote:
Op 07-04-16 om 14:22 schreef Chris Angelico:
...
There's no __cmp__ method, but you could easily craft your own
compare() function:
def compare(x, y):
"""Return a number < 0 if x < y, or > 0 if x > y"""
if x == y: return 0
return -1 if
On Thu, Apr 7, 2016 at 2:56 PM, Antoon Pardon
wrote:
> Op 07-04-16 om 14:22 schreef Chris Angelico:
>
> ...
>
>> There's no __cmp__ method, but you could easily craft your own
>> compare() function:
>>
>> def compare(x, y):
>> """Return a number < 0 if x < y, or > 0 if x > y"""
>> if x ==
On Thu, Apr 7, 2016 at 1:32 PM, Marko Rauhamaa wrote:
> Paul Rubin :
>
>> Chris Angelico writes:
>>> First off, what does it actually *mean* to have a tree with numbers
>>> and keys as strings? Are they ever equal? Are all integers deemed
>>> lower than all strings? Something else?
>>
>> If the A
On Fri, Apr 8, 2016 at 6:56 AM, Antoon Pardon
wrote:
>
> That solution will mean I will have to do about 100% more comparisons
> than previously.
Try it regardless. You'll probably find that performance is fine.
Don't prematurely optimize!
ChrisA
--
https://mail.python.org/mailman/listinfo/pyth
Marko Rauhamaa writes:
> Guido chose a different method to implement timers for asyncio. He
> decided to never remove canceled timers.
Oh my, that might not end well. There are other approaches that don't
need AVL trees and can remove cancelled timers, e.g. "timer wheels" as
used in Erlang and f
Antoon Pardon writes:
> With this method I have to traverse the two tuples almost always
> twice. Once to find out if they are equal and if not a second time to
> find out which is greater.
You are essentially describing the new internal API of comparison
operators. That's pretty much unavoidabl
Op 07-04-16 om 14:22 schreef Chris Angelico:
...
> There's no __cmp__ method, but you could easily craft your own
> compare() function:
>
> def compare(x, y):
> """Return a number < 0 if x < y, or > 0 if x > y"""
> if x == y: return 0
> return -1 if keyify(x) < keyify(y) else 1
>
>
On Fri, Apr 8, 2016 at 5:26 AM, Paul Rubin wrote:
> Chris Angelico writes:
>> First off, what does it actually *mean* to have a tree with numbers
>> and keys as strings? Are they ever equal? Are all integers deemed
>> lower than all strings? Something else?
>
> If the AVL tree's purpose is to be
Paul Rubin :
> Chris Angelico writes:
>> First off, what does it actually *mean* to have a tree with numbers
>> and keys as strings? Are they ever equal? Are all integers deemed
>> lower than all strings? Something else?
>
> If the AVL tree's purpose is to be an alternative lookup structure to
>
Chris Angelico writes:
> First off, what does it actually *mean* to have a tree with numbers
> and keys as strings? Are they ever equal? Are all integers deemed
> lower than all strings? Something else?
If the AVL tree's purpose is to be an alternative lookup structure to
Python's hash-based dict
On 07/04/2016 13:05, Antoon Pardon wrote:
I am looking at my avltree module for converting it to
python3.
One of the things that trouble me here is how python3 no
longer has cmp and how things have to be of "compatible"
type in order to be comparable.
So in python2 it wasn't a problem to have a
On Thu, Apr 7, 2016 at 10:05 PM, Antoon Pardon
wrote:
> I am looking at my avltree module for converting it to
> python3.
>
> One of the things that trouble me here is how python3 no
> longer has cmp and how things have to be of "compatible"
> type in order to be comparable.
>
> So in python2 it w
I am looking at my avltree module for converting it to
python3.
One of the things that trouble me here is how python3 no
longer has cmp and how things have to be of "compatible"
type in order to be comparable.
So in python2 it wasn't a problem to have a tree with
numbers and strings as keys. In p
57 matches
Mail list logo
