LG g pro有折腾的可能么？ - 未名空间MITBBS历史存档

LG g pro有折腾的可能么？# PDA - 掌中宝

t*a2013-08-09 07:08

1 楼

我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。

t*e2013-08-09 07:08

2 楼

Att升级想换lg g pro . 我就想root 一下，装个CM10.1。从古狗的信息看cm没有Att版
本的支持，好像
bootloader也不好弄。有折腾过的分享下经验吧

n*n2013-08-09 07:08

3 楼

为什么不写在global var上面？？tail call和global效率不一样？

a*n2013-08-09 07:08

4 楼

不好弄
换别的吧

【在 t*******e 的大作中提到】

: Att升级想换lg g pro . 我就想root 一下，装个CM10.1。从古狗的信息看cm没有Att版
: 本的支持，好像
: bootloader也不好弄。有折腾过的分享下经验吧

d*e2013-08-09 07:08

5 楼

可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行

【在 t****a 的大作中提到】

: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。

t*e2013-08-09 07:08

6 楼

刚刚入手了LG optimus g pro
屏幕和CPU真是没说的，感觉比iphone 5的屏幕还细致（在屏幕面积是iphone好几倍的
情况下），而且边框面积很小
折腾方面只有root可以折腾一下，xda上没有任何其他的ROM, CM更是别想了，折腾空间
为0，不过目前也没感觉有什么折腾的必要
最重要的是79块钱超值啊，G pro不愧为性价比之王

【在 a******n 的大作中提到】

: 不好弄
: 换别的吧

y*g2013-08-09 07:08

7 楼

有些就是不能转
不过你确定memorize比iteration差一大截？举个例子？

【在 t****a 的大作中提到】

: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。

f*e2013-08-09 07:08

8 楼

你们确定要root么
我的G Pro刚决定要寄出去修
原因是屏幕自己click，抖屏
LG还不肯出运费

t*a2013-08-09 07:08

9 楼

分成3类也不见得合适，见谅
例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
话，就需要存储range(x)*range(y)*range(z)三维
例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
如找前面中间最小的之类
例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)

【在 d**e 的大作中提到】

: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行

t*e2013-08-09 07:08

10 楼

root吧，unroot也很容易
目前使用良好，costco好像还有半年保修

【在 f**e 的大作中提到】

: 你们确定要root么
: 我的G Pro刚决定要寄出去修
: 原因是屏幕自己click，抖屏
: LG还不肯出运费

t*a2013-08-09 07:08

11 楼

memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。

【在 y*******g 的大作中提到】

: 有些就是不能转
: 不过你确定memorize比iteration差一大截？举个例子？

t*a2013-08-09 07:08

12 楼

不懂。这是回答这个问题吗？是什么意思？

【在 n******n 的大作中提到】

: 为什么不写在global var上面？？tail call和global效率不一样？

p*22013-08-09 07:08

13 楼

什么是尾递归呀？

n*n2013-08-09 07:08

14 楼

tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

【在 t****a 的大作中提到】

: 不懂。这是回答这个问题吗？是什么意思？

d*e2013-08-09 07:08

15 楼

....这是作业的证明题？

【在 t****a 的大作中提到】

: 分成3类也不见得合适，见谅
: 例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
: 话，就需要存储range(x)*range(y)*range(z)三维
: 例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
: 如找前面中间最小的之类
: 例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)

d*e2013-08-09 07:08

16 楼

你说的有理
但跟他想问的有点不对口

【在 n******n 的大作中提到】

: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

y*g2013-08-09 07:08

17 楼

用指针的话没什么区别吧

【在 n******n 的大作中提到】

: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

n*n2013-08-09 07:08

18 楼

lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。

t*a2013-08-09 07:08

19 楼

个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。

,.

【在 n******n 的大作中提到】

: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。

w*22013-08-09 07:08

20 楼

尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话）

【在 t****a 的大作中提到】

: 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
: 回复，长知识，这就转包子给你。
:
: ,.

t*a2013-08-09 07:08

21 楼

http://en.wikipedia.org/wiki/Tail_call

【在 p*****2 的大作中提到】

: 什么是尾递归呀？

D*d2013-08-09 07:08

22 楼

例三不是可以直接计算吗:
[1 -1;0 1] [f; g]_x = [1 0; 1 1] [f; g]_{x-1}
==>
[f; g]_x = [1 1;0 1] [1 0; 1 1] [f; g]_{x-1} = [2 1; 1 1] [f; g]_{x-1}
= ... = [2 1; 1 1]^n [f; g]_{0}
而 [2 1; 1 1]^n 可以通过分解用特征值求解

t*a2013-08-09 07:08

23 楼

我不会把任意的递归问题转换成尾递归。比如，
1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
2. 程序依赖多个子递归问题，应该怎么办？
3. 多个子函数相互嵌套递归怎么办？
如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
我只会用memorize function。效率跟iteration还是差一大截。

n*n2013-08-09 07:08

24 楼

为什么不写在global var上面？？tail call和global效率不一样？

d*e2013-08-09 07:08

25 楼

可以把123各举个例子吗？
应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行

【在 t****a 的大作中提到】

: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。

y*g2013-08-09 07:08

26 楼

有些就是不能转
不过你确定memorize比iteration差一大截？举个例子？

【在 t****a 的大作中提到】

: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。

t*a2013-08-09 07:08

27 楼

分成3类也不见得合适，见谅
例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
话，就需要存储range(x)*range(y)*range(z)三维
例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
如找前面中间最小的之类
例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)

【在 d**e 的大作中提到】

: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行

t*a2013-08-09 07:08

28 楼

memorize仍然是递归，递归就需要将push pop局部变量，这应该是变慢的重要原因吧。
另外memorize有stackoverflow的风险。JVM上似乎1W层就挂了。
由于会记住所有的调用，memroize还会吃掉大量的内存，可能造成out of memory。迭
代的方法可以自己选择保留什么变量所以没有这个问题。

【在 y*******g 的大作中提到】

: 有些就是不能转
: 不过你确定memorize比iteration差一大截？举个例子？

t*a2013-08-09 07:08

29 楼

不懂。这是回答这个问题吗？是什么意思？

【在 n******n 的大作中提到】

: 为什么不写在global var上面？？tail call和global效率不一样？

p*22013-08-09 07:08

30 楼

什么是尾递归呀？

n*n2013-08-09 07:08

31 楼

tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

【在 t****a 的大作中提到】

: 不懂。这是回答这个问题吗？是什么意思？

d*e2013-08-09 07:08

32 楼

....这是作业的证明题？

【在 t****a 的大作中提到】

: 分成3类也不见得合适，见谅
: 例子1, f = function(x, y, z) 其中 x y z为三个参数，如果动态规划表格来表示的
: 话，就需要存储range(x)*range(y)*range(z)三维
: 例子2，f(x) = g(f(x-1), f(x-2), ..., f(1)) 其中g是某个依赖于1..x-1的运算，比
: 如找前面中间最小的之类
: 例子3, f(x) = f(x-1) + g(x); g(x) = g(x-1) + f(x-1)

d*e2013-08-09 07:08

33 楼

你说的有理
但跟他想问的有点不对口

【在 n******n 的大作中提到】

: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

y*g2013-08-09 07:08

34 楼

用指针的话没什么区别吧

【在 n******n 的大作中提到】

: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

n*n2013-08-09 07:08

35 楼

lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
典型DP解法简单。。。。

t*a2013-08-09 07:08

36 楼

个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
回复，长知识，这就转包子给你。

,.

【在 n******n 的大作中提到】

: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。

w*22013-08-09 07:08

37 楼

尾递归和普通递归的区别就是其栈的空间大小是不随着函数的调用而增长的，所以不会
有stack overflow的问题，通过将所需信息直接通过参数传进调用的子函数，这样的过
程很迭代其实没什么区别，对于一些语言，编译器就直接会把尾递归转化成迭代.
对于简单的递归转化成尾递归，可以通过传递参数的方法来保存之前的状态，但是对于
一些多次调用递归，简单的增加传入参数就不行了，可以使用continuation-passing
style(CPS)来实现，此方法仅适用在函数式编程
就执行效率来说，memorization并不迭代差（不考虑空间复杂度的话）

【在 t****a 的大作中提到】

: 个人有点执着的喜欢递归而不是iteration，尾递归像递归却本质上是iteration。谢谢
: 回复，长知识，这就转包子给你。
:
: ,.

t*a2013-08-09 07:08

38 楼

http://en.wikipedia.org/wiki/Tail_call

【在 p*****2 的大作中提到】

: 什么是尾递归呀？

D*d2013-08-09 07:08

39 楼

例三不是可以直接计算吗:
[1 -1;0 1] [f; g]_x = [1 0; 1 1] [f; g]_{x-1}
==>
[f; g]_x = [1 1;0 1] [1 0; 1 1] [f; g]_{x-1} = [2 1; 1 1] [f; g]_{x-1}
= ... = [2 1; 1 1]^n [f; g]_{0}
而 [2 1; 1 1]^n 可以通过分解用特征值求解

p*22013-08-09 07:08

40 楼

这不是违反FP的理念了吗？

【在 n******n 的大作中提到】

: tail call的优势来自于把结果保存在函数的input里面。但如果保存在global变量里面
: ，不也一样么？这些global存在heap里面，不会每次都recursion 的时候都push pop

p*22013-08-09 07:08

41 楼

感觉树的遍历应该可以

【在 d**e 的大作中提到】

: 可以把123各举个例子吗？
: 应该也不是所有递归都可以转化为尾递归的，比如树的遍历就好像不行

p*22013-08-09 07:08

42 楼

我最近也在思考这个问题。

【在 t****a 的大作中提到】

: 我不会把任意的递归问题转换成尾递归。比如，
: 1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
: 自变量为一维的问题。
: 2. 程序依赖多个子递归问题，应该怎么办？
: 3. 多个子函数相互嵌套递归怎么办？
: 如果有解决这方面问题的尾递归的材料，请分享给我，非常感谢。
: 我只会用memorize function。效率跟iteration还是差一大截。

p*22013-08-09 07:08

43 楼

1. 如果做动态规划，依赖的参数是多维的，应该怎么办？我看到过的尾递归只解决了
自变量为一维的问题。
感觉这个可以解决呀。

p*22013-08-09 07:08

44 楼

,.
典型DP利用了mutable变量，这个和FP的理念不符。

【在 n******n 的大作中提到】

: lz在一楼提到了三种方法: tail call, memorization, iteration(典型DP解法？)
: 我不明白LZ的问题，你是说想执着的‘放弃典型DP的方法’来找一种方法专门把‘任何
: 递归化成尾递归’？那这种方法即使存在，尾递归在stack上面的操作也不可能比典型
: DP解法更优。那么这么做的唯一原因就是写成尾递归编码更方便（memorization如果想
: 优化所用到的比tail call多用的内存，还是可以替代掉）。但对于f(x) = g(f(x-1),.
: ..,f(1))，和多函数互相调用的情况，好像能否存在转化成tail call要和g的具体函数
: 有关？还是对于2和3这种情况根本就转化不了？但不论怎么样，在代码方面也看不出比
: 典型DP解法简单。。。。

l*b2013-08-09 07:08

45 楼

嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
牛讲讲

【在 p*****2 的大作中提到】

:
: ,.
: 典型DP利用了mutable变量，这个和FP的理念不符。

p*22013-08-09 07:08

46 楼

top
我刚写了一个尾递归，解决2维dp，你帮我看看。
http://www.mitbbs.com/article_t/JobHunting/32313551.html

【在 l*******b 的大作中提到】

: 嗯，functional里面的lazy evaluation sequence不知道怎么实现的．这个和
: memorization有点像吧，像fibonacci数列那样的．不知道是bottom up的实现还是top
: down的实现，bottom up貌似不需要stack 调用，top down就是递归了，当然这个例子
: 两个是等价的可以互相转化，可以写成尾递归的形式．一般的就不知道了．看看那位大
: 牛讲讲