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

Groups > comp.lang.python > #61726

Re: Optimizing list processing

Show key headers only | View raw

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()
> for x, i in table:
>     table[i] = x
> 
> For giant iterables (ten million items), this version is a big
> improvement, about three times faster than the list comp version. Since
> we're talking about the difference between 4 seconds and 12 seconds (plus
> an additional 40-80 seconds of general slow-down as the computer pages
> memory into and out of virtual memory), this is a good, solid
> optimization.
> 
> Except that for more reasonably sized iterables, it's a pessimization.
> With one million items, the ratio is the other way around: the list comp
> version is 2-3 times faster than the in-place version. For smaller lists,
> the ratio varies, but the list comp version is typically around twice as
> fast. A good example of trading memory for time.
> 
> So, ideally I'd like to write my code like this:
> 
> 
> table = [(x, i) for i,x in enumerate(iterable)]
> table.sort()
> if len(table) < ?????:
>     table = [i for x,i in table]
> else:
>     for x, i in table:
>         table[i] = x
> 
> where ????? no doubt will depend on how much memory is available in one
> contiguous chunk.
> 
> Is there any way to determine which branch I should run, apart from hard-
> coding some arbitrary and constant cut-off value?

How about using two lists?

keys = list(iterable)
values = range(len(keys))
values.sort(key=keys.__getitem__)
del keys

The intention is to save memory used for the 2-tuples; I don't know if they 
pop up elsewhere.

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

Thread

Optimizing list processing Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-11 23:54 +0000
  Re: Optimizing list processing MRAB <python@mrabarnett.plus.com> - 2013-12-12 00:59 +0000
    Re: Optimizing list processing Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-12 01:43 +0000
      Re: Optimizing list processing MRAB <python@mrabarnett.plus.com> - 2013-12-12 02:09 +0000
  Re: Optimizing list processing duncan smith <buzzard@invalid.invalid> - 2013-12-12 01:02 +0000
  Re: Optimizing list processing Ben Finney <ben+python@benfinney.id.au> - 2013-12-12 12:18 +1100
  Re: Optimizing list processing Terry Reedy <tjreedy@udel.edu> - 2013-12-11 21:26 -0500
    Re: Optimizing list processing Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-12 12:08 +0000
      Re: Optimizing list processing Chris Angelico <rosuav@gmail.com> - 2013-12-12 23:25 +1100
      Re: Optimizing list processing MRAB <python@mrabarnett.plus.com> - 2013-12-12 13:32 +0000
      Re: Optimizing list processing Chris Angelico <rosuav@gmail.com> - 2013-12-13 01:06 +1100
      Re: Optimizing list processing Terry Reedy <tjreedy@udel.edu> - 2013-12-12 13:40 -0500
        Re: Optimizing list processing Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-13 00:14 +0000
          Re: Optimizing list processing Chris Angelico <rosuav@gmail.com> - 2013-12-13 12:01 +1100
  Re: Optimizing list processing Stefan Behnel <stefan_ml@behnel.de> - 2013-12-12 12:09 +0100
  Re: Optimizing list processing Peter Otten <__peter__@web.de> - 2013-12-12 16:08 +0100
    Re: Optimizing list processing Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-12-13 03:01 +0000
      Re: Optimizing list processing rusi <rustompmody@gmail.com> - 2013-12-12 21:35 -0800
  Re: Optimizing list processing Terry Reedy <tjreedy@udel.edu> - 2013-12-12 13:07 -0500

csiph-web