Clone elements of a list

Let's say I have a Python list that looks like this:

list = [ a, b, c, d开发者_如何学Go]

I am looking for the most efficient way performanse wise to get this:

list = [ a, a, a, a, b, b, b, c, c, d ]

So if the list is N elements long then the first element is cloned N-1 times, the second element N-2 times, and so forth...the last element is cloned N-N times or 0 times. Any suggestions on how to do this efficiently on large lists.

---

Note that I am testing speed, not correctness. If someone wants to edit in a unit test, I'll get around to it.

pyfunc_fastest: 152.58769989 usecs
pyfunc_local_extend: 154.679298401 usecs
pyfunc_iadd: 158.183312416 usecs
pyfunc_xrange: 162.234091759 usecs
pyfunc: 166.495800018 usecs
Ignacio: 238.87629509 usecs
Ishpeck: 311.713695526 usecs
FabrizioM: 456.708812714 usecs
JohnKugleman: 519.239497185 usecs
Bwmat: 1309.29429531 usecs

Test code here. The second revision is trash because I was rushing to get everybody tested that posted after my first batch of tests. These timings are for the fifth revision of the code.

Here's the fastest version that I was able to get.

def pyfunc_fastest(x):
    t = []
    lenList = len(x)
    extend = t.extend
    for l in xrange(0, lenList):
        extend([x[l]] * (lenList - l))

Oddly, a version that I modified to avoid indexing into the list by using enumerate ran slower than the original.

---

>>> items = ['a', 'b', 'c', 'd']

>>> [item for i, item in enumerate(items) for j in xrange(len(items) - i)]
['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'd']

First we use enumerate to pull out both indexes and values at the same time. Then we use a nested for loop to iterate over each item a decreasing number of times. (Notice that the variable j is never used. It is junk.)

This should be near optimal, with minimal memory usage thanks to the use of the enumerate and xrange generators.

---

How about this - A simple one

>>> x = ['a', 'b', 'c', 'd']
>>> t = []
>>> lenList = len(x)
>>> for l in range(0, lenList):
...     t.extend([x[l]] * (lenList - l))
... 

>>> t
['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'd']
>>> 

---

Lazy mode:

import itertools

l = ['foo', 'bar', 'baz', 'quux']

for i in itertools.chain.from_iterable(itertools.repeat(e, len(l) - i)
    for i, e in enumerate(l)):
  print i

Just shove it through list() if you really do need a list instead.

list(itertools.chain.from_iterable(itertools.repeat(e, len(l) - i)
  for i, e in enumerate(l)))

---

My first instinct..

l = ['a', 'b', 'c', 'd']
nl = []

i = 0

while len(l[i:])>0:
    nl.extend( [l[i]]*len(l[i:]) )
    i+=1

print nl

---

The trick is in using repeat from itertools

from itertools import repeat

alist = "a b c d".split()
print [ x  for idx, value in enumerate(alist) for x in repeat(value, len(alist) - idx) ]

>>>['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'd']

---

Use a generator: it's O(1) memory and O(N^2) cpu, unlike any solution that produces the final list which uses O(N^2) memory and cpu. This means it'll be massively faster as soon as the input list is large enough that the constructed list fills memory and swapping starts. It's unlikely you need to have the final list in memory unless this is homework.

def triangle(seq):
    for i, x in enumerate(seq):
        for _ in xrange(len(seq) - i - 1):
            yield x

---

To create that new list, list = [ a, a, a, a, b, b, b, c, c, d ] would require O(4n) = O(n) time since for every n elements, you are creating 4n elements in the second array. aaronasterling gives that linear solution.

You could cheat and just not create the new list. Simply, get the index value as input. Divide the index value by 4. Use the result as the index value of the original list.

In pseudocode:

function getElement(int i)
{
     int trueIndex = i / 4;
     return list[trueIndex]; // Note: that integer division will lead us to the correct index in the original array.
}

---

fwiw:

>>> lst = list('abcd')
>>> [i for i, j in zip(lst, range(len(lst), 0, -1)) for _ in range(j)]
['a', 'a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'd']

---

def gen_indices(list_length):
    for index in range(list_length):
        for _ in range(list_length - index):
            yield index

new_list = [list[i] for i in gen_indices(len(list))]

untested but I think it'll work