找到任何5个数字,其总和= 100。这可以在一个循环中完成,但我正在向一个朋友说明列表理解,才意识到这需要超过30分钟在我的Mac Book Pro,核心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]
如果将问题改为5个数字连续,那么构建列表解析甚至需要更长的时间。如果我使用列表解析来解决这个问题,我做得对吗?如果是,为什么需要太长的时间?请提供一个可能更快的解决方案,也许使用循环。
4条答案
按热度按时间koaltpgm1#
多个生成器的行为就像列表上的嵌套循环,每次调用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秒内运行。
7fyelxc52#
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:
and the result:
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.
wmvff8tz3#
Erlang很强,当我们在编程中使用并发时,这样你也可以派生100个进程来处理列表[1,...,100]。这样可以方便你的笔记本电脑计算。例如:
有了上面的解决方案,我的笔记本电脑与i3 2.1GHz可以很容易地计算在1分钟。你也可以产生更多的进程更短的计算。进程在Erlang是轻量级进程,所以它可以很容易地开始,然后很容易停止。
os8fio9y4#
一个选择是
仅仅是不枚举所有可能的
E
,最多只会有一个成功,应该会快100倍(或者更多,因为产生的垃圾更少)。但是这里有一些代码重复。不幸的是,Erlang不允许在列表解析中使用“局部”变量,但是你可以用单元素生成器来模拟它们:
或者避免重复
lists:seq
调用,正如@RichardC指出的: