On Wed, 11 Dec 2013 21:26:51 -0500, Terry Reedy wrote:
> On 12/11/2013 6:54 PM, Steven D'Aprano wrote:
>> I have some code which produces a list from an iterable using at least
>> one temporary list, using a Decorate-Sort-Undecorate idiom.
>
> It is a non-standard version thereof, as DSU usually means to decorate
> with a key that gets discarded.
I do decorate with a key that gets discarded. The actual values that are
being sorted are the enumerated values 0, 1, 2, ... and the temporary key
values come from the iterable.
Confused yet? :-)
> A couple of examples of input and expected output would have been good
> ;-).
Only if I wanted you to understand the algorithm, which isn't really
important. My question is about swapping between in-place modifications
and external copying. If I wanted to be really mysterious (annoying), I
could have just give pseudo-code :-)
Please don't focus on the algorithm I gave. Focus on the fact that I
could write it like this:
if some condition to do with the computer's available memory:
make modifications in place
else:
make a copy of the data containing the modifications
if only I knew what that condition was and how to test for it.
>> The algorithm looks something like this (simplified):
>>
>> table = sorted([(x, i) for i,x in enumerate(iterable)])
>
> This makes two temporaries when only one is needed, and shows why we
> added generator expressions.
You may be right in this particular case, I don't know I haven't tried
it, but there are cases where list comps are significantly faster than
generator expressions. For example, when passed to str.join, list comps
are (on my computer) consistently 15% faster:
[steve@ando ~]$ python3.3 -m timeit "''.join([chr(n) for n in range(1,
201)])"
10000 loops, best of 3: 100 usec per loop
[steve@ando ~]$ python3.3 -m timeit "''.join([chr(n) for n in range(1,
201)])"
10000 loops, best of 3: 94.1 usec per loop
[steve@ando ~]$ python3.3 -m timeit "''.join(chr(n) for n in range(1,
201))"
10000 loops, best of 3: 116 usec per loop
[steve@ando ~]$ python3.3 -m timeit "''.join(chr(n) for n in range(1,
201))"
10000 loops, best of 3: 109 usec per loop
> table = sorted((x, i) for i,x in enumerate(iterable)) is equivalent to
> the table; table.sort lines below.
>
> The following (untested) should be faster as it avoids tuple unpacking
> and repacking.
I'm not terribly fussed about micro-optimizations here. I'm concerned
about *macro-optimizing* the case where creating two (or more) lists
forces the computer to page memory in and out of virtual memory. Saving a
few milliseconds? I don't care. Saving 5 or 6 seconds? That I care about.
[...]
> I expect the list comp be faster than in-place as long as the result
> list can be allocated and held in memory without paging. (This of course
> depends on system memory and other memory uses.)
Exactly!
> List iterators have a
> __length_hint__ method giving the length of the underlying list, so the
> list comp result list can potentially be allocated once and then filled
> in by enumeration and replacement, but in C rather than Python code.
I don't want to pre-allocate the list comp. I want to avoid having to
have two LARGE lists in memory at the same time, one containing the
decorated values, and one not. I know that this is a good optimization
for large enough lists. On my computer, ten million items is sufficient
to demonstrate the optimization, and with sufficient testing I could
determine a rough cut-off value, below which list comps are more
efficient and above which in-place modifications are better.
But I don't know how to generalize that cut-off value. If I buy extra
RAM, the cut-off value will shift. If I run it on another computer, it
will shift.
P.S. The algorithm I'm working on is a way of generating index and rank
tables. Not that it really matters -- what matters is determining whether
or not to shift from "make a copy of the list" to "modify the list in
place".
--
Steven
--
https://mail.python.org/mailman/listinfo/python-list
