Warn against quadratic list summation

[hauntsaninja]

I can't find a linter that warns me about sum(list_of_lists, []). Basically any time the default arg of sum is a list literal, I think something slow could happen. Maybe ruff could warn me about this? :-)

[konstin]

Is the correct replacement for this list(itertools.chain(*list_of_lists)) or is there a better solution? I've been following https://stackoverflow.com/a/953097/3549270 so far

[hauntsaninja]

Yup, that'll work!

I don't have strong opinions on the replacement, they all seem to be a constant factor off.

• list(itertools.chain.from_iterable(list_of_lists)) looks to be a shade faster than list(itertools.chain(*list_of_lists)) on my machine
• Looking at your StackOverflow link I see mention of functools.reduce(operator.iadd, list_of_lists, []), which is fastest for me
• The most straightforward is probably just [x for lst in list_of_lists for x in lst]

λ python3.11 -m timeit -n 10000 -r 20 -s 'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools,functools,operator' '[x for y in l for x in y]'
10000 loops, best of 20: 25.5 usec per loop
λ python3.11 -m timeit -n 10000 -r 20 -s 'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools,functools,operator' 'list(itertools.chain(*l))'
10000 loops, best of 20: 18.5 usec per loop
λ python3.11 -m timeit -n 10000 -r 20 -s 'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools,functools,operator' 'list(itertools.chain.from_iterable(l))'
10000 loops, best of 20: 17.5 usec per loop
λ python3.11 -m timeit -n 10000 -r 20 -s 'l=[[1,2,3],[4,5,6], [7], [8,9]]*99;import itertools,functools,operator' 'functools.reduce(operator.iadd, l, [])'
10000 loops, best of 20: 11.7 usec per loop

Repro using the nice perfplot code from your StackOverflow link:

[hauntsaninja]

Saw a "needs decision" label got added. I'd vote the best replacement is functools.reduce(operator.iadd, l, []). If we don't want to add imports, then [x for y in l for x in y].

[charliermarsh]

I'm cool with adding this as long as the ecosystem checks look okay (that is: no major false positives).

[evanrittenhouse]

You can assign this to me. I should have a fix out soon.

[arogozhnikov]

funny enough, if I use sum(l, []), it is slow

But when I reimplement the same code in a very naive way:

def sum_lists(x):
    res = []
    for i in x:
        res += i
    return res

it is on par with proposed solutions (or even faster)

[hauntsaninja]

Yes, that's the magic of iadd instead of add.