我正在阅读的关于 Erlang 的书的后面有练习,其中之一是重新创建 lists:append 函数。
我可以简单地使用++ 运算符来做到这一点,但这真的很慢吗?而且我认为练习的重点是使用我编写的列表操作来完成它。
到目前为止,我能想到的唯一方法是执行以下操作:
concat([], _, Results)->
Results;
concat(_, [], Results)->
Results;
concat([Ah|At],B,Results) ->
concat(At,B,[Ah|Results]).
但我知道这是不正确的......
有关如何执行此操作的任何建议?
编辑:为了澄清这个问题,这里是一个示例输入和输出:
输入:[[1,2,3],[],[4,5],[6]]
输出:[1,2,3,4,5,6]
工作一段时间后,我也想出了这段代码:
append([A|[B|[T|[]]]]) ->
append([A++B|T]);
append([H|T]) ->
H++T.
但是,这只适用于列表大小为 3 的情况。如何修改它以使其适用于任何给定数量的随机大小的列表?
最佳答案
++ 仅在错误使用时会很慢,小心使用它与您可以手工制作的任何东西一样快。您必须确保以正确的方向处理列表,否则结果追加为 O(N^2)。当我们执行 X++ Y 时,我们必须制作 X 的副本,然后将其添加到未复制的 Y 之前。
在此函数中,累加器出现在++ 的左侧,因此追加效率不高。
concatl(Lst) ->
concatl(Lst, []).
concatl([], Acc) ->
Acc;
concatl([H|T], Acc) ->
concatl(T, Acc ++ H).
这个函数的性能要好得多,即使它不是尾递归的。
concat([]) -> [];
concat([H|T]) ->
H ++ concat(T).
在这种情况下,重写为尾递归只是一个适度的改进:
concat2(Lst) ->
concat2(lists:reverse(Lst), []).
concat2([], Acc) -> Acc;
concat2([H|T], Acc) ->
concat2(T, H ++ Acc).
大型输入列表上的时间显示了改进的巨大程度。 (时间以微秒为单位。)
41> Time(fun() -> test:concatl([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
14539061
40> Time(fun() -> test:concat([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
245356
42> Time(fun() -> test:concat2([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
211571
关于list - 如何在不使用列表模块的情况下编写 Erlang 的列表连接?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1131127/