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

Groups > comp.lang.python > #31140

Re: Insert item before each element of a list

Show key headers only | View raw

On 10/11/2012 6:21 PM, Hans Mulder wrote:
> On 9/10/12 04:39:28, rusi wrote:
>> On Oct 9, 7:34 am, rusi <rustompm...@gmail.com> wrote:
>>> How about a 2-paren version?
>>>
>>>>>> x = [1,2,3]
>>>>>> reduce(operator.add,  [['insert', a] for a in x])
>>>
>>> ['insert', 1, 'insert', 2, 'insert', 3]
>>
>> Or if one prefers the different parens on the other side:
>>
>>>>> reduce(operator.add, (['insert', a] for a in x))
>> ['insert', 1, 'insert', 2, 'insert', 3]
>
> Or, if you don't want to import the operator module:
>
> sum((['insert', a] for a in x), [])

All of the solutions based on adding (concatenating) lists create an 
unneeded temporary list for each addition except the last and run in 
O(n**2) time. Starting with one list and appending or extending (which 
does two appends here) is the 'proper' approach to get an O(N) algorithm.

This does not matter for n=3, but for n = 10000 it would.

expanded = []
expand = expand.append
for item in source:
   expand('insert')
   expand(item)

is hard to beat for clarity and time.

expanded = []
expand = expand.extend
for item in source:
   expand(['insert', item])

might be faster if creating the list is faster than the second expand 
call. Note that a typical lisp-like version would recursively traverse 
source to nil and build expanded from tail to head by using the 
equivalent of
   return ['insert' item].extend(expanded)
Extend would be O(1) here also since it would at worst scan the new list 
of length 2 for each of the items in the source.


def interleave(source):
   for item in source:
     yield 'insert'
     yield item

list(interleave(source))

might also be faster since it avoids the repeated python level call. I 
prefer it anyway as modern, idiomatic python in that it separates 
interleaving from creating a list. In many situations, creating a list 
from the interleaved stream will not be needed.

-- 
Terry Jan Reedy

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

Thread

Insert item before each element of a list mooremathewl@gmail.com - 2012-10-08 12:28 -0700
  Re: Insert item before each element of a list Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-08 13:42 -0600
  Re: Insert item before each element of a list MRAB <python@mrabarnett.plus.com> - 2012-10-08 20:43 +0100
  Re: Insert item before each element of a list Ian Kelly <ian.g.kelly@gmail.com> - 2012-10-08 14:04 -0600
  Re: Insert item before each element of a list Agon Hajdari <agonh@freenet.de> - 2012-10-08 22:12 +0200
  Re: Insert item before each element of a list Peter Otten <__peter__@web.de> - 2012-10-08 23:12 +0200
  RE: Insert item before each element of a list "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-10-08 21:15 +0000
  Re: Insert item before each element of a list Agon Hajdari <agonh@freenet.de> - 2012-10-08 23:39 +0200
  RE: Insert item before each element of a list "Prasad, Ramit" <ramit.prasad@jpmorgan.com> - 2012-10-08 22:12 +0000
  Re: Insert item before each element of a list Paul Rubin <no.email@nospam.invalid> - 2012-10-08 15:24 -0700
  Re: Insert item before each element of a list Nobody <nobody@nowhere.com> - 2012-10-08 23:35 +0100
  Re: Insert item before each element of a list "Alex" <foo@email.invalid> - 2012-10-09 00:08 +0000
  Re: Insert item before each element of a list Terry Reedy <tjreedy@udel.edu> - 2012-10-08 21:58 -0400
    Re: Insert item before each element of a list Roy Smith <roy@panix.com> - 2012-10-08 22:06 -0400
      Re: Insert item before each element of a list rusi <rustompmody@gmail.com> - 2012-10-08 19:34 -0700
        Re: Insert item before each element of a list rusi <rustompmody@gmail.com> - 2012-10-08 19:39 -0700
          Re: Insert item before each element of a list Hans Mulder <hansmu@xs4all.nl> - 2012-10-12 00:21 +0200
            Re: Insert item before each element of a list Terry Reedy <tjreedy@udel.edu> - 2012-10-11 19:38 -0400
            Re: Insert item before each element of a list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-12 02:16 +0000
        Re: Insert item before each element of a list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2012-10-09 12:01 +0000
      Re: Insert item before each element of a list alex23 <wuwei23@gmail.com> - 2012-10-08 20:11 -0700
      Re: Insert item before each element of a list mooremathewl@gmail.com - 2012-10-09 07:03 -0700
  Re: Insert item before each element of a list Duncan Booth <duncan.booth@invalid.invalid> - 2012-10-09 11:40 +0000
    Re: Insert item before each element of a list Peter Otten <__peter__@web.de> - 2012-10-09 14:55 +0200

csiph-web