Why does this List comprehension take too long to evaluate on Erlang/OTP 20?

Question

To find any 5 numbers whose sum = 100. This can be done in a loop but i was illustrating list comprehension to a friend only to realize this takes more than 30 mins on my Mac Book Pro,core i7, 2.2GHz

[[A,B,C,D,E] || A <- lists:seq(1,100),B <- lists:seq(1,100),C <- lists:seq(1,100),D <- lists:seq(1,100),E <- lists:seq(1,100),(A + B + C + D + E) == 100]

And if the question is changed to have the 5 numbers consecutive, the constructed list comprehension even takes much longer. If i am to solve this problem using a list comprehension, am i doing it right ? if yes, why does it take too long ? please provide a solution that may be faster, perhaps using a loop.

Answer 1

The multiple generators behave like nested loops over the lists, and each call to lists:seq() will be fully evaluated each time. This takes a very long time, and spends most of that time allocating list cells and garbage collecting them again. But since they all evaluate to the same constant list anyway, you can rewrite it as L = lists:seq(1,100), [[A,B,C,D,E] || A <- L,B <- L,C <- L,D <- L,E <- L,(A + B + C + D + E) == 100]. Also, running this in the shell will be a lot slower than in a compiled module. On my macbook, the compiled code finished in about 2 min 30 s. And that's just using a single core. Compiling with [native] makes it run in 60 seconds flat.

Answer 2

Because it "creates" all the elements of a 100^5 list of list of 5 elements before it makes the filter, that represents 50000000000 elements.

[edit] I reviewed the answer from RichardC and Alexey Romanov and I decided to make some tests:

-module (testlc).

-export ([test/1]).

test(N) ->
    F1 = fun() -> [{W,X,Y,Z}|| W <- lists:seq(1,N),X <- lists:seq(1,N),Y <- lists:seq(1,N),Z <- lists:seq(1,N), W+X+Y+Z == N] end,
    F2 = fun() ->L = lists:seq(1,N),  [{W,X,Y,Z}|| W <- L,X <- L,Y <- L,Z <- L, W+X+Y+Z == N] end,
    F3 = fun() -> [{W,X,Y,Z}|| W <- lists:seq(1,N-3), X <- lists:seq(1,N-2-W),Y <- lists:seq(1,N-1-W-X),Z <- lists:seq(1,N-W-X-Y), W+X+Y+Z == N] end,
    F4 = fun() -> [{W,X,Y,N-W-X-Y}|| W <- lists:seq(1,N-3),X <- lists:seq(1,N-2-W),Y <- lists:seq(1,N-1-W-X)] end,
    F5 = fun() -> L = lists:seq(1,N), [{W,X,Y,N-W-X-Y}|| W <- L, 
                                                         XM <- [N-2-W],      X <- L, X =< XM, 
                                                         YM <- [N-1-W-X],    Y <- L, Y =< YM] end,
    {T1,L1} = timer:tc(F1),
    {T2,L2} = timer:tc(F2),
    {T3,L3} = timer:tc(F3),
    {T4,L4} = timer:tc(F4),
    {T5,L5} = timer:tc(F5),
    _L = lists:sort(L1),
    _L = lists:sort(L2),
    _L = lists:sort(L3),
    _L = lists:sort(L4),
    _L = lists:sort(L5),
    {test_for,N,{t1,T1},{t2,T2},{t3,T3},{t4,T4},{t5,T5}}.

and the result:

1> c(testlc).      
{ok,testlc}
2> testlc:test(50).
{test_for,50,
          {t1,452999},
          {t2,92999},
          {t3,32000},
          {t4,0},
          {t5,0}}
3> testlc:test(100).
{test_for,100,
          {t1,4124992},
          {t2,1452997},
          {t3,203000},
          {t4,16000},
          {t5,15000}}
4> testlc:test(150).
{test_for,150,
          {t1,20312959},
          {t2,7483985},
          {t3,890998},
          {t4,93000},
          {t5,110000}}
5> testlc:test(200).
{test_for,200,
          {t1,63874875},
          {t2,24952951},
          {t3,2921995},
          {t4,218999},
          {t5,265000}}

Preparing the list outside of the list comprehension has a big impact, but it is more efficient to limit drastically the number of useless intermediate lists generated before the filter works. So it is a balance to evaluate. In this example, the 2 enhancements can be used together (Thanks to Alexey) but it does not make a big difference.