V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  Heartwork  ›  全部回复第 1 页 / 共 2 页
回复总数  26
1  2  
Crosswalk或者Cordova。
2015-06-16 15:45:27 +08:00
回复了 Tiande 创建的主题 Python python3 对 尾递归 优化的 解释器 有推荐的吗?
不是,我是想看看对尾递归优化的算法是什么样的,有文章的话我看看能不能用在我的解释器上。
2015-06-16 15:33:27 +08:00
回复了 Tiande 创建的主题 Python python3 对 尾递归 优化的 解释器 有推荐的吗?
正想做这个,分享一下呗?:)
@binux 堆的那个恐怕不行吧。怎么处理插入一个比该层元素都小的值?
@binux 恩,不错,是这样
1 因为malloc在分配的内存是16字节补齐的。所以就算你访问了后面的几个字节,也还是在有效内存范围内。

2 即使你访问了多于16字节的非法空间,还是需要根据brk或sbrk查看数据段末端的地址,如果超过这个值,就会有内存访问异常了。
@binux
对了,你说的2的“调整”如果满足a和b,就是一个快速排序。
@binux
n层大于n-1层(a)与右孩子大于左孩子(b)是两个独立的条件,写两个例子。
a成立b不成立:
a
c b
b成立a不成立:
b
a c
这两个条件共同约束下只能是有序序列。
@woai110120130
所以底层用数组就行了
@binux

我是这样理解的。就是一颗有序的完全二叉树。
后排序会导致插入过程中树无法保持有序的条件,这个题目就退化为给一个数组排序了。

底层如果使用二叉树的话,需要维护每一个元素的“前驱”和“后继”,前驱和后继指value的前一个和后一个。

这样插入时需要遍历插入位置之后的元素,复杂度和数组的相同。
有序的完全二叉树为一有序序列,在插入过程中插入位置之后的节点都需要向后移动,所以这个题目等同于求一个有序数组的插入算法…

这样应该没问题了。
@binux
说反了,应该是 无法避免a的兄弟节点的孩子比a小的状况

这样:

a
b z
c d
c和d是b的孩子,但是比z小。
@wodesuck
不是,我的方案是使用有序数组。
@binux
无法避免a的兄弟节点的孩子比a大的状况
@binux

不是堆,堆的性质只能保证parent的value比child小。
@binux

英雄所见略同:)

顺序插入的话,直接把元素放到末尾就好。

不过考虑如果数据为随机插入的话,整个算法就退化为有序数组的插入算法了。

整个过程还是O(log n^2)
2015-06-15 23:14:21 +08:00
回复了 mvj3 创建的主题 程序员 为什么很多人理解不了 Max Howell 通不过白板编程面试
@mvj3

BuildYourOwnLisp

就是这个教程,因为教程里用C写的比较繁琐,我的项目用C++实现的。

支持了high order function, lexical scope之后没什么动力了。
2015-06-15 23:09:46 +08:00
回复了 mvj3 创建的主题 程序员 为什么很多人理解不了 Max Howell 通不过白板编程面试
@mvj3 @binux

3、如果你连用栈模拟递归都需要「顿悟」的话,说明你根本不理解递归,甚至不理解函数是怎么执行的。

再罗嗦一下,二者的空间复杂度是一样的(在满足平衡二叉树的条件下,为O(logn)),但是因为使用了手工的栈来模拟系统栈,所以效率上不如递归版本。

非递归版本就是让学生通过动手来理解递归过程及栈帧状态。
@Heartwork 恩,果然不行。

树的底层使用数组表示,插入算法使用普通的数组插入,可以保证最后的树为符合条件的完全树。

不过整体算法复杂度为O(n^2)。

你有更好复杂度的算法没?
1  2  
关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   923 人在线   最高记录 6679   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.5 · 17ms · UTC 21:28 · PVG 05:28 · LAX 14:28 · JFK 17:28
Developed with CodeLauncher
♥ Do have faith in what you're doing.