Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder7.xlned.com!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Date: Thu, 12 Dec 2013 00:59:42 +0000
From: MRAB <python@mrabarnett.plus.com>
User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:24.0) Gecko/20100101 Thunderbird/24.1.1
MIME-Version: 1.0
To: python-list@python.org
Subject: Re: Optimizing list processing
References: <52a8fb2d$0$29992$c3e8da3$5496439d@news.astraweb.com>
In-Reply-To: <52a8fb2d$0$29992$c3e8da3$5496439d@news.astraweb.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Precedence: list
Reply-To: python-list@python.org
Newsgroups: comp.lang.python
Message-ID: <mailman.3942.1386809980.18130.python-list@python.org>
Lines: 56
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:61632

On 11/12/2013 23:54, 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. The algorithm
> looks something like this (simplified):
>
> table = sorted([(x, i) for i,x in enumerate(iterable)])
> table = [i for x,i in table]
>
> The problem here is that for large iterables, say 10 million items or so,
> this is *painfully* slow, as my system has to page memory like mad to fit
> two large lists into memory at once. So I came up with an in-place
> version that saves (approximately) two-thirds of the memory needed.
>
> table = [(x, i) for i,x in enumerate(iterable)]
> table.sort()

This looks wrong to me:

> for x, i in table:
>      table[i] = x

Couldn't it replace an item it'll need later on?

Let me see if I can find an example where it would fail.

Start with:

 >>> table = [('b', 0), ('a', 1)]

Sort it and you get:

 >>> table.sort()
 >>> table
[('a', 1), ('b', 0)]

Run that code:

 >>> for x, i in table:
	table[i] = x

	
Traceback (most recent call last):
   File "<pyshell#18>", line 1, in <module>
     for x, i in table:
ValueError: need more than 1 value to unpack

Why did it fail?

 >>> table
[('a', 1), 'a']

The 2 methods give different results anyway: the first returns a list
of indexes, and the second returns a list of items from the iterable.

[snip]