Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #106660

Re: how to convert code that uses cmp to python3

Show all headers | View raw

Paul Rubin <no.email@nospam.invalid>:

> Marko Rauhamaa <marko@pacujo.net> 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 (scanning and re-heapifying
> the timeout list) with probability O(1/n) where n is the queue size,
> which itself changes (by 0, +1 or -1) when a timeout event happens.
> That is, its overhead is a constant factor unless I'm missing
> something. There are some efficiency gains possible but it seems par
> for the course for Python code.

I compared the performance of AVL trees, the older heapq technique as
well as the "GC scheme" in 2014 with a challenging but realistic
test scenario. AVL trees and the GC scheme had pretty much the same
throughput (and the older, simple heapq was slower).

With AVL trees, it's easier to be convinced about worst-case
performance. It is more difficult to see the potential pathological
cases with the GC scheme.


Marko

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Re: how to convert code that uses cmp to python3 Paul Rubin <no.email@nospam.invalid> - 2016-04-07 12:26 -0700
  Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-07 22:32 +0300
    Re: how to convert code that uses cmp to python3 Paul Rubin <no.email@nospam.invalid> - 2016-04-07 14:15 -0700
      Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 07:22 +0300
        Re: how to convert code that uses cmp to python3 Terry Reedy <tjreedy@udel.edu> - 2016-04-08 02:20 -0400
          Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 09:53 +0300
            Re: how to convert code that uses cmp to python3 Paul Rubin <no.email@nospam.invalid> - 2016-04-08 00:03 -0700
              Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 10:40 +0300
                Re: how to convert code that uses cmp to python3 Paul Rubin <no.email@nospam.invalid> - 2016-04-08 01:43 -0700
    Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 07:17 +0300
      Re: how to convert code that uses cmp to python3 Ian Kelly <ian.g.kelly@gmail.com> - 2016-04-07 22:37 -0600
        Re: how to convert code that uses cmp to python3 Marko Rauhamaa <marko@pacujo.net> - 2016-04-08 08:00 +0300
    Re: how to convert code that uses cmp to python3 Terry Reedy <tjreedy@udel.edu> - 2016-04-08 02:12 -0400

csiph-web