如何在erlang中创建一个非常大的列表

Question

我们使用list:seq(1,100)来创建一个包含100个元素的列表,并且创建速度是可以接受的

但是如果我们用1000w元素创建一个列表呢？列表:seq(1,10000000)非常慢.

你有什么想法创建一个没有任何datacopy的大型列表？

Answer 1

实际上,lists:seq/2不执行任何复制.这是实际的实现:

seq(First, Last)
    when is_integer(First), is_integer(Last), First-1 =< Last -> 
    seq_loop(Last-First+1, Last, []).

seq_loop(N, X, L) when N >= 4 ->
    seq_loop(N-4, X-4, [X-3,X-2,X-1,X|L]);
seq_loop(N, X, L) when N >= 2 ->
    seq_loop(N-2, X-2, [X-1,X|L]);
seq_loop(1, X, L) ->
    [X|L];
seq_loop(0, _, L) ->
    L.

因此,它以递归方式调用自身,在每次调用(第三个参数)中向累加器添加最多4个元素.将元素预先添加到列表中不涉及任何复制,并且调用是尾递归的,因此堆栈具有恒定的大小.

编辑:为了完整起见,我在评论中粘贴了一些说明:Erlang列表是链接列表.在内部[H | T],创建元素H并添加指向T. T永远不会被复制.你可以这样做,因为T是不可变的,它永远不会改变,即使你创建[H1 | T],[H2 | T]和[H3 | T] - T在他们之间共享.

使用list作为参数调用函数也不涉及复制:)包括列表在内的较大数据结构存储在进程堆上.您只存储指向堆栈上第一个元素的指针.只将消息发送到另一个进程实际上会复制该列表.

创建非常大的列表可能会很慢,因为您可能会耗尽物理内存并开始使用swap.编辑结束

关于迭代,我想建立在Nicolas Talfer的答案上 - 你有时想要将参数传递给循环中调用的函数,你可以使用更高阶的函数和闭包来做到这一点:

main(_) ->
    InitialArgs = 6,
    InitialFun = fun() -> do_stuff(InitialArgs) end,
    Ret = forloop(InitialFun, 5),
    io:format("~p", [Ret]).

forloop(Fun, 1) ->
    Fun();
forloop(Fun, Count) ->
    RetVal = Fun(),
    NewFun = fun() -> do_stuff(RetVal) end,
    forloop(NewFun, Count-1).

do_stuff(Args) ->
    Args + 2.