为什么在 Erlang/OTP 20 上评估这个列表理解需要太长时间？

Question

找到总和 = 100 的任何 5 个数字。这可以在循环中完成，但我向朋友展示了列表理解，结果发现这在我的 Mac Book Pro、酷睿 i7、2.2GHz 上需要 30 多分钟

[[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]

如果将问题更改为连续的 5 个数字，则构建的列表理解甚至需要更长的时间。如果我要使用列表理解来解决这个问题，我做得对吗？如果是，为什么需要太长时间？请提供一个可能更快的解决方案，也许使用循环。

Answer 1

多个生成器的行为类似于列表上的嵌套循环，并且每次调用lists:seq() 都会被完全评估。这需要很长时间，并且大部分时间都花在分配列表单元和再次垃圾收集它们上。但由于它们都计算为相同的常量列表，因此您可以将其重写为 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]。此外，在 shell 中运行它会比在编译模块中慢很多。在我的 macbook 上，编译代码在大约 2 分 30 秒内完成。这只是使用单个内核。使用 [native] 编译使其运行时间为 60 秒。

Answer 2

因为它在创建过滤器之前“创建”了 5 个元素列表的 100^5 列表的所有元素，这表示 50000000000 个元素。

[编辑] 我回顾了 RichardC 和 Alexey Romanov 的回答，并决定进行一些测试：

-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}}.

结果：

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}}

在列表理解之外准备列表会产生很大的影响，但在过滤器工作之前大幅限制生成的无用中间列表的数量会更有效。所以这是一个平衡来评估。在这个例子中，这 2 个增强可以一起使用（感谢 Alexey），但没有太大区别。