12

I hope to write the join_lists function to take an arbitrary number of lists and concatenate them. For example, if the inputs are 

m = [1, 2, 3]
n = [4, 5, 6]
o = [7, 8, 9]

then we I call print join_lists(m, n, o), it will return [1, 2, 3, 4, 5, 6, 7, 8, 9]. I realize I should use *args as the argument in join_lists, but not sure how to concatenate an arbitrary number of lists. Thanks.

alittleboy
  • 10,616
  • 23
  • 67
  • 107

6 Answers6

18

Although you can use something which invokes __add__ sequentially, that is very much the wrong thing (for starters you end up creating as many new lists as there are lists in your input, which ends up having quadratic complexity).

The standard tool is itertools.chain:

def concatenate(*lists):
    return itertools.chain(*lists)

or 

def concatenate(*lists):
    return itertools.chain.from_iterable(lists)

This will return a generator which yields each element of the lists in sequence. If you need it as a list, use list: list(itertools.chain.from_iterable(lists))

If you insist on doing this "by hand", then use extend:

def concatenate(*lists):
    newlist = []
    for l in lists: newlist.extend(l)
    return newlist

Actually, don't use extend like that - it's still inefficient, because it has to keep extending the original list. The "right" way (it's still really the wrong way):

def concatenate(*lists):
    lengths = map(len,lists)
    newlen = sum(lengths)
    newlist = [None]*newlen
    start = 0
    end = 0
    for l,n in zip(lists,lengths):
        end+=n
        newlist[start:end] = list
        start+=n
    return newlist

http://ideone.com/Mi3UyL

You'll note that this still ends up doing as many copy operations as there are total slots in the lists. So, this isn't any better than using list(chain.from_iterable(lists)), and is probably worse, because list can make use of optimisations at the C level.

Finally, here's a version using extend (suboptimal) in one line, using reduce:

concatenate = lambda *lists: reduce((lambda a,b: a.extend(b) or a),lists,[])
Marcin
  • 48,559
  • 18
  • 128
  • 201
  • Doesn't PEP8 state that though we *can* write a loop on one line, we shouldn't? I'm just being nit-picky. – SethMMorton Sep 05 '13 at 17:44
  • @SethMMorton It also states that a foolish consistency is the hobgoblin of small minds, as I recall. I certainly find this more readable for one single expression. – Marcin Sep 05 '13 at 17:49
  • Haha. That's true too. – SethMMorton Sep 05 '13 at 17:50
  • @AshwiniChaudhary Thanks. I think there's a badge for a certain number of answers with more votes than the accepted answer. – Marcin Sep 05 '13 at 18:08
  • What about adding up the length and doing `[None]*newlen` as in your example then doing `newlist[:] = itertools.chain.from_iterable(lists)` ? C-level optimizations don't get you out of the fact that the list constructor cannot know the final length before iterating through everything. – Random832 Sep 05 '13 at 19:16
  • @Random832 Ah, but by working on the C level, it can make memory allocation more efficient. In particular, it can allocate the memory atomically from the python-level perspective, without allocating a python object and re-allocating. As to the form you give - yes, that would be even better, but the point was to show how to do the job "by hand". If you're going to use itertools, you might as well just call `list`. – Marcin Sep 05 '13 at 19:52
16

One way would be this (using reduce) because I currently feel functional:

import operator
from functools import reduce
def concatenate(*lists):
    return reduce(operator.add, lists)

However, a better functional method is given in Marcin's answer:

from itertools import chain
def concatenate(*lists):
    return chain(*lists)

although you might as well use itertools.chain(*iterable_of_lists) directly.

A procedural way:

def concatenate(*lists):
    new_list = []
    for i in lists:
        new_list.extend(i)
    return new_list

A golfed version: j=lambda*x:sum(x,[]) (do not actually use this).

Talia Stocks
  • 3
  • 3
rlms
  • 10,650
  • 8
  • 44
  • 61
2

You can use sum() with an empty list as the start argument:

def join_lists(*lists):
    return sum(lists, [])

For example:

>>> join_lists([1, 2, 3], [4, 5, 6])
[1, 2, 3, 4, 5, 6]
Andrew Clark
  • 202,379
  • 35
  • 273
  • 306
  • 1
    Why? I think this looks fine. – rlms Sep 05 '13 at 17:32
  • 7
    This solution is only good for very very short lists, it has quadratic complexity. – Frerich Raabe Sep 05 '13 at 17:33
  • Interesting question. Does `sum()` internally use `+` or `+=` to accumulate the result? With one of those this will have quadratic complexity, with the other it is linear. – Duncan Sep 05 '13 at 17:36
  • 2
    ...and to answer my own question, @FrerichRaabe is correct. If `sum()` used inplace addition it would mutate the starting value which could break things, so it has to use ordinary addition with quadratic complexity. – Duncan Sep 05 '13 at 17:40
0

Another way:

>>> m = [1, 2, 3]
>>> n = [4, 5, 6]
>>> o = [7, 8, 9]
>>> p = []
>>> for (i, j, k) in (m, n, o):
...     p.append(i)
...     p.append(j)
...     p.append(k)
... 
>>> p
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>>
Joyfulgrind
  • 2,762
  • 8
  • 34
  • 41
0

This seems to work just fine:

def join_lists(*args):
    output = []
    for lst in args:
        output += lst
    return output

It returns a new list with all the items of the previous lists. Is using + not appropriate for this kind of list processing?

AlexH
  • 111
  • 1
-1

Or you could be logical instead, making a variable (here 'z') equal to the first list passed to the 'join_lists' function then assigning the items in the list (not the list itself) to a new list to which you'll then be able add the elements of the other lists:

m = [1, 2, 3]
n = [4, 5, 6]
o = [7, 8, 9]

def join_lists(*x):
    z = [x[0]]
    for i in range(len(z)):
        new_list = z[i]
    for item in x:
        if item != z:
            new_list += (item)
    return new_list

then

print (join_lists(m, n ,o)

would output:

[1, 2, 3, 4, 5, 6, 7, 8, 9]

xxlovesmilie
  • 1