一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1162|回复: 7
收起左侧

[二分/排序/搜索] 问一个关于Binary Search的问题

[复制链接] |试试Instant~ |关注本帖
dorota 发表于 2016-6-13 20:47:08 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
例如
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int l = 0, r = n;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (this.isBadVersion(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
这里 int mid = l + (r - l) / 2;
是否每次都声明了新的mid,消耗了额外的空间。是否应该把int mid的声明挪到while外边?
多谢!

blackrose 发表于 2016-6-13 22:11:03 | 显示全部楼层
如果非要计算cpu cycle的话,放外面合适。 但是一般code 的原则是 用variable 时候再allocate。
回复 支持 反对

使用道具 举报

lzlindy 发表于 2016-6-13 23:03:15 | 显示全部楼层
我觉得不会吧,java有自动回收,那此次循环内声明的mid用完了,到下一次循环就被释放了,每次都是这样。所以似乎没有额外的空间? I GUESS。。
回复 支持 反对

使用道具 举报

回到拉萨 发表于 2016-6-13 23:19:26 | 显示全部楼层
实际生活中很少会考虑到这么low level的优化。 如果非要说的话这是一个tradeoff: 你放在while loop外面变量的生命周期长 不需要每次循环分配新的变量;但是分配新的变量不见得会慢(存储在寄存器上), 一般的rule of the thumb就是用到变量的时候分配
回复 支持 反对

使用道具 举报

 楼主| dorota 发表于 2016-6-15 13:40:04 | 显示全部楼层
多谢各位的回复!
回复 支持 反对

使用道具 举报

cptn3m0 发表于 2016-6-30 10:03:19 | 显示全部楼层
这算小细节了, 楼主不用太关注
回复 支持 反对

使用道具 举报

Meetyourmaster 发表于 2016-6-30 10:21:52 | 显示全部楼层
本帖最后由 Meetyourmaster 于 2016-6-30 10:24 编辑

放里面,jvm会自动优化。 而且从scope原则来看,有些变量在loop外不应该可见
回复 支持 反对

使用道具 举报

cptn3m0 发表于 2016-6-30 11:23:34 | 显示全部楼层
Meetyourmaster 发表于 2016-6-30 10:21
放里面,jvm会自动优化。 而且从scope原则来看,有些变量在loop外不应该可见

从代码的可读性方面考虑, 确实应该方法到loop里面, 不容易产生误解
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 13:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表