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函数存在性能优化的空间,其他函数可能也同样存在这个问题,这对小列表不存在什么问题,
对大列表的处理如果内存足够也没什么问题,但总会让人觉得不爽。同时也说明编写尾递归函数的重要性,如果是自定义函数,写成尾递归的形式总是对的。
分享到:
相关推荐
Lists-Lists-Lists
proxy-lists 一个Node.js模块,用于从公开可用的代理列表中获取代理
Lists.pas 提供了很多个TList的扩展类,是学习很研究TList的好东西。 Calendar.pas 公历与农历换算和时间处理的函数单元,具体看里面的说明。 Clipboards.pas 提供一个剪贴板增强类,可支持保存和载入剪贴板,...
理工科必备的Journal Term Lists,使用EndNote导入,可以使得插入参考文献时更加的准确。。。
filelists.xml.gz filelists.xml.gz filelists.xml.gz
com.google.common.collect.Lists的jar包
有一份中文版的,一份英文版的。 C++ Information Documentation Reference Articles Sourcecode Forum Reference C Library IOstream Library ...C++ Lists ...全部的 C 函数 全部的 C++ 函数
Merge two lists of ordered numbers
该模块包含一个属性,用于测试lists模块的delete操作。 通过运行: cd(priv). readspec:suite(simple_eqc, prop_simple). 您将获得一个?MODULE.feature文件,其中包含一些用?MODULE.feature在测试属性时将运行的...
本资源包下载后可以得到两本电子书:《C/C++ 语言参考.chm》和《C语言函数大全(语法着色版).chm》。《C/C++ 语言参考.chm》内容预览: 基本C/C++ ------------------------- 预处理命令 操作符优先级 转义字符 ...
A SMALL JavaScript control widget I wrote to move items between two unordered lists with sorting function.
access lists are built, and give examples of how to apply those access lists in different situations. Along the way, there are a number of sidebars and notes about concepts and information important...
工程学期刊缩写Endnote Term Lists 来自哥大图书馆,7000多条。可以Endnote直接导入。
七千多种工程类论文期刊简称,用于endnote导出。但是有些时候还会存在一些问题,最为常见的就是有些期刊仍旧不能显示缩写的问题,这时候就需要我们在“journal term lists”进行手动添加即可。
Awesome Lists
Coq Lists.v 答案 Coq Lists.v 答案 Coq Lists.v 答案
在Python中,python给我们提供了很多已经定义好的函数,这里列出常用的内置函数,分享出来供大家参考学习,下面话不多说,来一起看看详细的介绍吧。 一、数学函数 abs() 求数值的绝对值 min()列表的最下值 max()...
前端项目-angular-drag-and-drop-lists,Angular directives for sorting nested lists using the HTML5 Drag and Drop API
Python手撕算法Lists
jquery-sortable-lists, 用于排序列表的jQuery插件还包括树结构 jquery-sortable-lists用于排序列表的插件还包括树结构。$('#myList').sortableLists( options );你可以通过鼠标对html列表的项进行排序。 创建树结构...