要实现一个函数,参数是一个list,结果是将list里每个数字都+1,返回一个新的list,会怎么实现呢?
看代码,哪个函数性能最好?(除了add2,因为他的结果是不正确的)
-module(t).
-compile(export_all).
add1([]) -> [];
add1([H|T]) -> [H+1|add1(T)].
add2(R) -> add(R,[]).
add3(R) -> lists:reverse(add(R,[])).
add4([]) -> [];
add4(L) -> lists:map(fun(X) -> X+1 end,L).
add([],R) -> R;
add([H|T],R) -> add(T,[H+1|R]).
t(N) ->
L = lists:seq(1,N),
{T1,_}=timer:tc(a,add1,[L]),
{T2,_}=timer:tc(a,add2,[L]),
{T3,_}=timer:tc(a,add3,[L]),
{T4,_}=timer:tc(a,add4,[L]),
io:format("~p ~p ~p ~p ~n",[T1,T2,T3,T4]).
函数说明:
*add1 是最简单的实现,没有使用尾递归
*add2 使用尾递归,最后没有reverse,结果是不正确的,仅仅用来比较
*add3 使用尾递归
*add4 使用list comprehension
在我的笔记本上运行,在N比较小(N<100000)的情况下,add3几乎总是比add1快,但是N比较大(N>100000)的时候,add1经常比add3快,说明lists:reverse的消耗还是挺大的
这个场景说明了几个问题:
*在list比较大的时候,reverse操作消耗还是很大的(废话)
*erlang的编译器会对类似add1的情况做优化,如果没有优化的话,应该会死的很惨
*当使用尾递归会带来额外的事情的时候,需要权衡一下,是否应该选用
*如果能事先知道程序运行的场景(这里是N的大小),写出来的程序性能才能更好
似乎都是废话,仅当记录。
分享到:
相关推荐
ps:并不是所有的递归都可以改写成尾递归 在js中,尾递归通常会被解释器优化。然而,并不是所有的js解释器都支持尾递归优化。 对于不支持尾递归优化的环境,我们需要手动将递归优化成栈+循环。 这里实现了一个通用的...
如果一个函数中所有递归形式的调用都出现在函数的末尾,我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时,这个递归调用就是尾递归。尾递归函数的特点是在...
但是,Lab2的主题是递归,所以大家这道题目不允许用BFS,必须是递归形式的。 对于每个测试用例,时间限制为1秒,实在不行,2秒也能接受。 规则没有优先级,所有的规则都是平等的,没有优先顺序。 可能会同时出现 ...
本文并不完美,其中递归的部分其实不应该在目前的生产环境中使用。但是我依然坚持认为 JS 引擎应该支持尾调优化,写尾递归和写循环性能没差别。 一,用好 filter,map,和其它 ES6 新增的高阶遍历函数 问题一: 将...
这种非递归毕达哥拉斯树是将整数转换为二进制数并根据简单规则进行跟踪的。 它使用一个接受整数的函数,然后将其首先转换为二进制字符串,然后转换为数组,然后根据简单的规则绘制路径:二进制数的初始“ 1”是第一...
比如Gmail邮箱里有垃圾邮件分 类器,一开始的时候可能什么都不过滤,在日常使用过程中,我人工对于每一封邮件点 选"垃圾"或"不是垃圾",过一段时间,Gmail就体现出一定的智能,能够自动过滤掉一些 垃圾邮件了。...
1)不做随机化处理的递归实现; 2)采用随机化处理的递归实现; 3)用while循环消除尾递归; 4)用栈模拟递归,并证明所需的栈空间为O(logn); 5) 够小时改用插入排序
解压的文件不包括它们的路径部分,因此所有文件都创建到同一个目标目录 中。 如果你要解压完整路径名,请使用 'x' 命令。 例子: rar e -or html.rar *.css css\ 从 html.rar 压缩文件中解压所有 *.css 文件...
在本文中,派生的抽象机(AM)是尾递归的一阶函数。 Coq系统必须能够证明所有递归函数定义的终止。 由于Coq的终止检查器的功能不足以证明某些AM的终止,或者不能期望AM总体上终止(lambda calculi的AM /具有循环的...
因为使用了递归算法,不能用于大数据的排序。归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;...
Lua的每个版本都保持着开放源码的传统,不过各版采用的许可协议并不相同,自5.0版(最新版是5.1) 开始她采用的是著名的MIT许可协议。正由于上述特点,所以Lua在游戏开发、机器人控制、分布式应用、图像处理、生物信息...
若线性表中所有的元素都与被查找元素进行了比较但都不相等,则表示查找失败。 例如,在一维数组[21,46,24,99,57,77,86]中,查找数据元素99,首先从第1个元素21开始进行比较,比较结果与要查找的数据不相等,...
LINQ-教程这是我们高级软件工程师的 LINQ 培训材料。 本教程采用 Visual Studio 解决方案的形式。 使用本教程的最佳方式是克隆此存储库(或下载 zip)并从您的 ... LINQ 到我的对象折:合计内部聚合:累加器和尾递归延
( A ) 6、对一个有向图进行拓扑排序,一定可以将图的所有顶点按其关键码大小排列到一个拓 扑有序的序列中。(B ) 7、图的广度优先搜索算法通常采用递归算法求解。( B ) 8、当从一个小根堆(最小堆)中删除一个元素时...
斐波那契 这是一个简单的程序,可用于比较Java中Fibonacci算法的3种不同实现,以了解计算时间。...尾递归斐波那契 迭代斐波那契 结果表明,迭代一次是最快的,而递归一次是最慢的。 因此,递归并不总是最好的。
若干年前犯过类似错误,二重循环倒序,因为完全背包不限次数,加了个三重循环 638大礼包 : 明确告诉你我就是完全背包;每种商品的数量作为状态,一维数组表示 221最大正方形 : 你只盯着左上角的那个正方形;3小加1 337强盗...
该项目的目标 拥有良好的错误并清除解析器错误,这些错误会为您指明正确的方向 拥有强大的标准库,使其实用 具有良好的性能和垃圾回收影响力JavaScript 长生不老药哈斯克尔已知错误/问题 由于某种原因,非尾递归不起...
因为尾指定文件名,假设为所有文件 (*)。 3) 作为一个特别的例外,如果目录名被作为参数指定并且目录名不包 含文件掩码和以反斜线结尾,即使指定了 -r 开关,目录和子目录的所 有内容都会被添加到压缩文件中。 ...
如果能使用算术比较的话,或许能简单地解决这个问题,但是正则表达式中并不提供关于数学的任何功能,所以只能使用冗长的分组,选择,字符类来描述一个正确的IP地址:((2[0-4]\d|25[0-5]|[01]?\d\d?)\.){3}(2[0-4]\d|...
对于每一个专题,作者都试图提供目前最新的研究成果及样例解答,并通过清晰的图示来说明算法的执行过程。. 本书是原书的第2版,在第1版的基础之上增加了一些新的内容,涉及算法的作用、概率分析和随机化算法、线性...