lists模块中delete函数的调优

Erlang中删除列表元素在标准模块lists中可以找到delete/2函数，

比如调用lists:delete(2, [1,2,3,4,5])后将返回新的列表[1,3,4,5]
笔者在翻阅lists模块源码中发现，一些函数实现成BIF，比如reverse就是一个BIF，在注释中发现

%% reverse(L) reverse all elements in the list L. Is now a BIF!

由此确定reverse是一个BIF。
但对delete函数的实现没找到类似的注释，怀疑其不是一个BIF，其实现存在性能问题，其实现代码如下：

delete(Item, [Item|Rest]) -> Rest;
delete(Item, [H|Rest]) ->
    [H|delete(Item, Rest)];
delete(_, []) -> [].

 

这个实现没使用尾递归，对大表的操作将会导致堆栈上的内存消耗严重。
测试程序如下：

test1() ->
    {ok,Bin} = file:read_file("file1.txt"),
    L = binary_to_list(Bin),
    R = lists:delete($a,L),
    io:format("~p~n",[length(R)]).

 

 

文件file1.txt有近30M大小，运行时内存高值1G以上。
笔者对delete重新用尾递归的方式改写一遍：

delete(E, [E|T], R) -> lists:reverse(R) ++ T;
delete(E, [H|T], R) -> delete(E, T, [H|R]);
delete(E, [], R) -> lists:reverse(R).

 

 

再运行测试程序：

test2() ->
    {ok,Bin} = file:read_file("file1.txt"),
    L = binary_to_list(Bin),
    R = delete($a,L,[]),
    io:format("~p~n",[length(R)]).

发现内存占用在800M以内。
由此可以推测标准模块中lists的delete函数存在性能优化的空间，其他函数可能也同样存在这个问题，这对小列表不存在什么问题，
对大列表的处理如果内存足够也没什么问题，但总会让人觉得不爽。同时也说明编写尾递归函数的重要性，如果是自定义函数，写成尾递归的形式总是对的。

评论

7 楼 sw2wolf 2008-10-13  

Trustno1 写道

stworthy 写道

出一个题目：假设需要对一个文件中的某个字进行删除，这个文件可能很大，这时用set，dict是用不上了。list将会是有效的存储方案，涉及对list的操作将不可避免，操作效率也会是很重要的。

请用binary/bitstring(only or r12)

binary/bitstring如何用？谢谢！

6 楼 Trustno1 2008-02-03  

stworthy 写道

出一个题目：假设需要对一个文件中的某个字进行删除，这个文件可能很大，这时用set，dict是用不上了。list将会是有效的存储方案，涉及对list的操作将不可避免，操作效率也会是很重要的。

请用binary/bitstring(only or r12)

5 楼 stworthy 2008-02-03  

出一个题目：假设需要对一个文件中的某个字进行删除，这个文件可能很大，这时用set，dict是用不上了。list将会是有效的存储方案，涉及对list的操作将不可避免，操作效率也会是很重要的。

4 楼 mryufeng 2008-02-01  

小量数据可以用list 大量的就用set 或者dict之类的专门数据结构 不需要调优的 在这点上。

3 楼 Trustno1 2008-02-01  

lichray 写道

Trustno1 写道

我认为，如果需求中存在需要随机访问的庞大线性表，那么用List本身就是一个糟糕的注意.

delete 不使用尾递归写那是在教育你，就像 Haskell 的 Prelude 库没有几个函数是用尾递归写法的。
教育你 1. 理解函数式编程中有趣的数学归纳法注明的方法；2. 长效需求就用长效数据结构，例如用二叉树实现的 Array。

我觉得倒是因为够用就好.

2 楼 lichray 2008-02-01  

Trustno1 写道

我认为，如果需求中存在需要随机访问的庞大线性表，那么用List本身就是一个糟糕的注意.

delete 不使用尾递归写那是在教育你，就像 Haskell 的 Prelude 库没有几个函数是用尾递归写法的。
教育你 1. 理解函数式编程中有趣的数学归纳法注明的方法；2. 长效需求就用长效数据结构，例如用二叉树实现的 Array。

1 楼 Trustno1 2008-02-01  

我认为，如果需求中存在需要随机访问的庞大线性表，那么用List本身就是一个糟糕的注意.