如何在不使用列表模块的情况下编写 Erlang 的列表连接？

发布于 2024-07-26 23:35:21 字数 643 浏览 8 评论 0原文

我正在读的关于 Erlang 的书后面有练习，其中一个是重新创建列表：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 的情况。我如何修改它，以便它适用于任意给定数量的随机大小的列表？

原文

The book I'm reading about Erlang has exercises in the back of it and one is to re-create the lists:append function.

I could do this simply using the ++ operator, but isn't this really slow? And I think the point of the exercise is to do it using list operations that I write.

So far the only approach that I could think of is to do something like:

concat([], _, Results)->
  Results;
concat(_, [], Results)->
  Results;
concat([Ah|At],B,Results) ->
  concat(At,B,[Ah|Results]).

But I know this is incorrect...

Any suggestions on how to go about doing this?

EDIT: To clarify the question, here is an example input and output:

Input: [[1,2,3],[],[4,5],[6]]
Output: [1,2,3,4,5,6]

After working a while, I came up with this code as well:

append([A|[B|[T|[]]]]) ->
  append([A++B|T]);
append([H|T]) ->
  H++T.

However, this only works for when the list is size 3. How can I modify this so that it works for any given amount of randomly sized lists?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

音盲 2024-08-02 23:35:21

++ 只有在使用错误时才会很慢，小心使用它会和你手工制作的任何东西一样快。您必须确保以正确的方向处理列表，否则结果追加的时间复杂度为 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

++ is only slow when used wrongly, used carefully it is as fast as anything you could craft by hand. You have to make sure you work through the list in the correct direction, otherwise the resulting append is O(N^2). When we do X ++ Y, we must make a copy of X and then prepend it to Y which is not copied.

In this function, the accumulator appears on the left hand side of the ++, so the append is not efficient.

concatl(Lst) ->
    concatl(Lst, []).
concatl([], Acc) ->
    Acc;
concatl([H|T], Acc) ->
    concatl(T, Acc ++ H).

This function performs much better, even though it's not tail recursive.

concat([]) -> [];
concat([H|T]) ->
    H ++ concat(T).

In this case rewriting to be tail recursive is only a modest improvement:

concat2(Lst) ->
    concat2(lists:reverse(Lst), []).
concat2([], Acc) -> Acc;
concat2([H|T], Acc) ->
    concat2(T, H ++ Acc).

The timings on a big input list show just how huge the improvement is. (Times are in microseconds.)

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

回复收藏 0 原文

耳钉梦 2024-08-02 23:35:21

您的 concat 函数只需要两个参数，因为您将附加到其中一个参数，这就是您最终将返回的内容。类似于（未经测试）：

concat(L,[]) ->
   L;
concat(L,[H|T]) ->
   concat(L ++ [H],T).

++ 是追加运算符，您必须这样做才能提高效率。

（上面的想法是，如果我们没有剩下的参数，则返回 left 参数，或者在将其中一个元素从右向左移动后再次调用）。反向执行附加操作，然后最终反转答案，可能会更有效率，但是嘿...）

（刚刚看到您的编辑，我的当然只适用于要附加的两件事，但您可以通过上述函数对每个进行递归列表列表中的元素...）

You only need two parameters to your concat function, as you'll be appending to one of the parameters and that's what you'll eventually return. Something like (untested):

concat(L,[]) ->
   L;
concat(L,[H|T]) ->
   concat(L ++ [H],T).

The ++ is the append operator, you're going to have to do that to be efficient.

(The idea of the above is to return the left parameter if we've no more left, or call again after moving one of the elements from the right to the left). There's probably more efficiencies around doing the append in reverse and then finally reversing the answer but hey...)

(Just saw your edit, and mine of course only works for two things to append, but you can recurse through the above function for each element in your list of lists...)

回复收藏 0 原文

一绘本一梦想 2024-08-02 23:35:21

一种巧妙的方法是使用lists:foldr，

concat(A,B) ->
    lists:foldr(fun(X,XS) -> [X|XS] end, B, A).

concat(XS) ->
    lists:foldr(fun concat/2, [], XS).

这也是编写自己的foldr函数的一个很好的练习......

One neat approach is to use lists:foldr,

concat(A,B) ->
    lists:foldr(fun(X,XS) -> [X|XS] end, B, A).

concat(XS) ->
    lists:foldr(fun concat/2, [], XS).

It's also a good excercise to write your own foldr function...

回复收藏 0 原文

失去的东西太少 2024-08-02 23:35:21

    -module(functional).
    -export([my_append/2,helper/2]).

    my_append(L1,L2) ->
      % concatenates lists L1 and L2
        functional:helper(lists:reverse(L1),L2).
    helper(L1,L2) ->
        if
            L1 == [] -> L2;
            L2 == [] -> L1;
            true     -> [H1|T1] = L1,
                        functional:helper(T1,[H1|L2])
        end.

    -module(functional).
    -export([my_append/2,helper/2]).

    my_append(L1,L2) ->
      % concatenates lists L1 and L2
        functional:helper(lists:reverse(L1),L2).
    helper(L1,L2) ->
        if
            L1 == [] -> L2;
            L2 == [] -> L1;
            true     -> [H1|T1] = L1,
                        functional:helper(T1,[H1|L2])
        end.

回复收藏 0 原文

~没有更多了~