Improve speed for list concatenation?

Question

I have a list called L inside a loop that must iterate though millions of lines. The salient features are:

for line in lines:
    L = ['a', 'list', 'with', 'lots', 'of', 'items']
    L[3] = 'prefix_text_to_item3' + L[3]
    Do more stuff with L...

Is there a better approach to adding text to a list item that would speed up my code. Can .join be used? Thanks.

The example makes it look like string concatenation rather than list concatenation. Can you fix it to be more like the true problem, or fix the description? — Mark Ransom, Jul 29 '11 at 19:02
I don't understand the question. What do you do with `line`. Do you want to concatenate lists or strings ? — log0, Jul 29 '11 at 20:11
Sorry my example was unclear. Basically, I am trying to prefix a string to the beginning of a list item. Take a string 'dog' and prefix onto a list item L[2]. In my example, this would produce the list item 'dogwith'. — drbunsen, Jul 29 '11 at 21:18

Cédric Julien · Accepted Answer · 2011-07-29T19:14:04.730

2

In a performance oriented code, it is not a good idea to add 2 strings together, it is preferable to use a "".join(_items2join_) instead. (I found some benchmarks there : http://www.skymind.com/~ocrow/python_string/)

edited Jul 29 '11 at 19:14

answered Jul 29 '11 at 19:00

Cédric Julien

78,516
15
127
132

2

Why would that be? I'd think they would be the same, unless you're joining more than 2 strings. – Mark Ransom Jul 29 '11 at 19:03
You are wrong. `''.join()` will be much slower then concatenation while working with two strings. See http://pastebin.com/6jWmpRs8 – Roman Bodnarchuk Jul 29 '11 at 19:28
I was confused by the wording of your answer - first you say "add 2 strings" then you say "items2join" which made me think you were comparing two ways of appending 2 strings. The larger point you were trying to make is not clear. – Mark Ransom Jul 29 '11 at 19:37
1

That source (http://www.skymind.com/~ocrow/python_string/) uses 20k and 500k for its benchmarks. For two strings, there's absolutely zero advantage. For a few (more than two) strings, there's probably no reason to. Only for really large strings you should avoid repeated concatenation. – Jul 29 '11 at 19:50
Well, the conclusion of this (and this http://stackoverflow.com/questions/376461/string-concatenation-vs-string-substitution-in-python) is that you should try the different solutions and benchmark them to find the most efficient solution in your case. :-). – Cédric Julien Jul 29 '11 at 20:42

score 1 · Answer 2 · edited May 23 '17 at 10:34

1

Since accessing an element in a python list is O(1), and appending a list to another is O(1) (which is probably the time complexity of concatenating strings in python), The code you have provided is running as fast as it can as far as I can tell. :) You probably can't afford to do this, but when I need speed I go to C++ or some other compiled language when I need to process that much information. Things run much quicker. For time complexity of list operations in python, you may consult this web site: http://wiki.python.org/moin/TimeComplexity and here: What is the runtime complexity of python list functions?

edited May 23 '17 at 10:34

Community

1
1

answered Jul 29 '11 at 18:47

djhaskin987

9,741
4
50
86

1. Appending a list to another is not O(1)... O(1) is for appending a single item. List concat should be equivalent to set slice - O(k+n). 2. He's not concatenating lists, he's concatenating strings. (prefix + l[i]) – Jeremy Brown Jul 29 '11 at 18:54

score 1 · Answer 3 · answered Jul 29 '11 at 18:56

Don't actually create list objects.

Use generator functions and generator expressions.

def appender( some_list, some_text ):
    for item in some_list:
        yield item + some_text

This appender function does not actually create a new list. It avoids some of the memory management overheads associated with creating a new list.

score 0 · Answer 4 · answered Jul 29 '11 at 22:18

There may be a better approach depending on what you are doing with list L.

For instance, if you are printing it, something like this may be faster.

print "{0} {1} {2} {3}{4} {5}".format(L[0], L[1], L[2], 'prefix_text_to_item3', L[3], L[4])

What happens to L later in the program?

Improve speed for list concatenation?

4 Answers4