珞珈山水BBS -- 单文区文章阅读

搜索

单文区文章阅读 [返回]
发信人: tyw (Inter&Ronnie), 信区: C.S 标题: [合集] 对学生朋友的一点建议[zz] 发信站: 珞珈山水BBS站 (Wed Jul 25 16:05:13 2007), 站内 ☆─────────────────────────────────────☆ bewithu (36.2℃沸点o0 和你在一起) 于 (Mon Jun 11 13:47:10 2007) 提到: 对学生朋友的一点建议 2007年6月1日上午 11:09:00 发表者：Google（谷歌）中国工程研究院工程师方坤自去年春天加入谷歌，我曾多次随公司校园招聘团队一起走访各地院校，帮助公司发掘人才。利用这样的出差机会到处走走看看，饱览祖国大好河山，是我一点小小的私心。但更具挑战性、更激动人心的，还是和我未来的同事们过招，不打不相识嘛。一想到马上就要和这样优秀的黄鸸ぷ鳎揖托朔懿灰眩婧薏坏孟衷诰吐蛞徽诺コ袒卑阉�/她拽回北京。然而，在面试过程中，我也相当惋惜地看到，由于种种主客观原因的限制，很多青春韶华的学子未能充分发挥出他们应有的潜力。这里我不讲成绩，只把我遇到过的一些普遍的问题归纳一下，希望对即将踏入社会的学生朋友们能有些许帮助。实战！实战！纸上得来终觉浅，绝知此事要躬行。对于一个未来的软件工程师来说，实际编程经验是相当重要的。我们会要求应聘者在紧凑的时间内编写大量的代码，从中考察应聘者的分析能力，编码速度，代码可读性，对所用编程语言的掌握程度，对边界条件与异常状况的处理，数据结构与涌诘亩ㄒ澹绦蛟诵械男屎陀ζ刚卟榇砭来淼哪芰Φ鹊取� 一口气列出这么多要求，听上去似乎过于苛刻，其实只要积累了足够的实战经验，每一个应聘者都完全可以满足这些最低限度的要求。我记得开复对于青年学子们有一个建议，大学四年，至少要编写 10 万行代码。不是每一个人都期望进入谷歌这样的顶级技术公司，但即使对开复的建议打个三折，也还有 3 万行呢，不努力，能行嘛。前来应聘的学生们在编写代码时暴露出这样那样的问题，大都可以归结到同一� ：锻炼太少。比如"for (int i = 0; i < strlen(s); ++i)"，没有实战经验的人，怎么可能意识到暗藏其间的效率陷阱。再比如内存泄漏，就和初恋一样，没有亲身经历过的人，不会有刻骨铭心的感受，而一旦经历，终身难忘，根本用不着你有多聪明。遗憾的是，我看到许多相当聪� 生写出来的代码只能用惨不忍睹来形容，真让我怀疑这是不是就是他们的第一次。大家不要怪谷歌要求高，恕我直言，如果不能持之以恒，下点儿苦功夫，不光谷歌一家，其它公司恐怕也是进不去的。北京、上海等地的学生，往往有更多实习、兼职机会，接受锻炼之余，还能攒下一笔小钱作零用之资。其它一些地区的学生也许就没有这么幸运，这就尤其需要积极主动，寻找机会，创造机会，把握机会。世界正在变平，互联网的发展改变着地球的面貌，让不发达地区的学生也能菀椎亟哟サ椒⒋锏厍淖试础Ｇ安痪梦以谖靼灿龅揭桓鲅肽昀匆恢奔岢衷诒本┐笱У� ACM 网站上参赛、做题，我看他写出来的程序就确实比他大多数同学都要好一些。我相信，只要他能够持之以恒，还会取得更大的进步。我听说浙江大学的 ACM 网站、TopCoder 网站也都是慕逃试矗行巳さ耐Р环烈豢矗凰渌底鼍喝饩嗬胝嬲娜砑⒒褂凶畔灾畋穑膊皇桓霾淮淼某龇⒌恪� 在积累一定编码量的基础上，我建议大家总结经验教训，不断提高自我。如果几万行代码写下来，学 C++ 的不知道 const 怎么用，学 python 的没听说过 GIL，我看也没什么意思。到了这个阶段，我推荐大家读一些经典的进阶书籍，例如《Effective C++》、《Effective Java� 即使地处偏远地区，也可通过网上书店买到。（我建议编码量太少的同学就先不要读了，会走火入魔的。我见过有学生连引用和指针都没搞清楚，就在那里重载操作符的。）交流也很重要，如果能够与网上网下志同道合的朋友互相帮助，共同进步，当收事半功倍之效。在这一方面，各 Google Camp 也许能够起到一定作用。 "我会写代码呀，为什么谷歌不要我？" 一家外包公司或许会满足于雇佣仅能从事简单的、机械性的重复劳动的软件蓝领，而让谷歌苦苦寻觅的，乃是最优秀的软件工程师兼计算机科学家——是的，在谷歌，研究与开发融为一体，软件工程师与计算机科学家当然也合二为一。计算机这几年算是比较热的，能够得偿所愿挤慊蒲喙刈ㄒ档难际侨泄ゼ獾娜瞬牛绻笱哪昊奈哐б担茨苋〉秸婢朔蚜苏庖焕粗灰椎难盎幔遣皇翘上Я四亍� 遍历一个数组或链表的时间复杂度是多少？对于这样一个不是问题的问题，竟然各地都有相当数量的学生回答说是 O(logN)！有一次我实在 ×耍崾居ζ傅难担�"你是如何理解'遍历'一词的涵义呢？"他立刻做恍然大悟状，回答说："哦，对，应该是 O(NlogN)"。我当时失望得一句话都说不出来。类似的例子还有很多。坊间一直传说谷歌的面试题有多难，其实大多数学生都卡在最基础的问题上。少数人费尽气力要收集 霉拿媸蕴猓涫滴颐谴蠖嗍饽慷祭醋曰蚋谋嘧跃浼扑慊蒲Ы滩牡南疤狻� 顺便提一句，上面提到的那个答错的学生乃是一流大学中成绩名列前茅的优秀生，门门功课（包括所有计算机专业课）均在 90 分以上。反差何其大也！诚信为本我曾服务于多家公司，注意到不同的公司之间，乃至同一公司内不同的面试官之间，对应聘者的要求都会有所差别，或看重潜质，或偏好经验，或强调态度。但有一点大家是共同的：如果应聘者在诚信上有疑问，谁也不敢要。总体而言，现在的学生其诚信还是相当不错的，大大� 我们的期望。然而，不和谐音也还是有的。我们曾在某著名高校进行笔试，就发现有学生严重作弊，他们毁掉自己的机会不说，整个学校的名声也受到拖累。面试中偶尔也能遇到诚信堪忧的学生。有一次我出了一道题，前来应聘的学生明明以前见过这道题，却告诉我说没见过，自以为 伤且蛔菁词诺慕器镆恍δ睦锾拥霉业难劬ΑＡ降阒渲毕咦疃蹋嫡婊白罴虻ァ� 做最好的自己不是每一个人都会加入某一家具体的公司，但每一个人都可以成功，成为最好的自己。我这里所谈，既不系统亦欠简练，但确实是我在几次校园招聘之旅中发现的一些具有共性的问题，故不避好为人师之讥，罗列于此。我当然知道，本文的首要目标读者——大一新生 暗模歉敢獍阉械拇砦笄鬃灾胤敢槐椤；八淙绱耍灰芄欢砸桓鲅兴舻希业氖奔渚筒凰惆追选� ※ 修改:·Crimkura 于 Jun 11 18:30:29 修改本文·[FROM: 222.20.237.] ※ 来源:·珞珈山水BBS站 http://bbs.whu.edu.cn·[FROM: 222.20.236.] ☆─────────────────────────────────────☆ zaneblue (道行不够\|\|go on working) 于 (Mon Jun 11 14:16:24 2007) 提到: 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指每次循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不是得浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时间效率那么重要啊, 无知了~~~ 【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】 : 对学生朋友的一点建议 : 2007年6月1日上午 11:09:00 : 发表者：Google（谷歌）中国工程研究院工程师方坤 : ................... ☆─────────────────────────────────────☆ bewithu (36.2℃沸点o0 和你在一起) 于 (Mon Jun 11 14:36:27 2007) 提到: 你觉得 strlen(s) 的计算不需要内存的么【在 zaneblue (道行不够\|\|go on working) 的大作中提到: 】 : 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指.. : 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不.. : 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时�.. : ................... ☆─────────────────────────────────────☆ zaneblue (道行不够\|\|go on working) 于 (Mon Jun 11 14:40:34 2007) 提到: 这个应该用完后立即挥手了吧设计strlen的人应该会考虑这些,主要还是时间吧【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】 : 你觉得 strlen(s) 的计算不需要内存的么 ☆─────────────────────────────────────☆ zercal (zercal) 于 (Tue Jun 12 12:06:27 2007) 提到: 【在 zaneblue (道行不够\|\|go on working) 的大作中提到: 】 : 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指.. : 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不.. : 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时�.. : ................... for(int i=0;s[i];i++)... 一般都这样写吧... for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了... ☆─────────────────────────────────────☆ zaneblue (道行不够\|\|go on working) 于 (Tue Jun 12 12:07:35 2007) 提到: 恩【在 zercal (zercal) 的大作中提到: 】 : for(int i=0;s[i];i++)... : 一般都这样写吧... : for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了... ☆─────────────────────────────────────☆ zjq (鉴真) 于 (Tue Jun 12 12:28:49 2007) 提到: 如果在循环里面s的长度在变化，那么这样写就是必需的！【在 zaneblue (道行不够\|\|go on working) 的大作中提到: 】 : 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指.. : 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不.. : 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时?. : ................... ☆─────────────────────────────────────☆ mmd (mmd) 于 (Tue Jun 12 13:33:24 2007) 提到: 就算变化也不能这么写【在 zjq (鉴真) 的大作中提到: 】 : 如果在循环里面s的长度在变化，那么这样写就是必需的！ ☆─────────────────────────────────────☆ zercal (zercal) 于 (Tue Jun 12 13:36:30 2007) 提到: 【在 zjq (鉴真) 的大作中提到: 】 : 如果在循环里面s的长度在变化，那么这样写就是必需的！ ......不管什么时候都不能这样写... 明明可以O(n),你非要O(n^2)... for(i=0;s[i];i++)跟那样的效果是一样的... ☆─────────────────────────────────────☆ zercal (zercal) 于 (Tue Jun 12 13:46:35 2007) 提到: 【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】 : 你觉得 strlen(s) 的计算不需要内存的么 strlen的原型大概上应该是这样的: int strlen(char s[]) { int i; i=0; while(s[i])/等同于s[i]!='\0'/ { i++; } return i; } 这个函数本身就是O(n)的,而子函数内部定义变量占用的内存,会在return时交还给系统的 ... ☆─────────────────────────────────────☆ mmd (mmd) 于 (Tue Jun 12 13:46:44 2007) 提到: 一个变量算不上什么内存开销你这个也不想开销的话就写在for里面【在 zaneblue (道行不够\|\|go on working) 的大作中提到: 】 : 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指每次 : 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不是得 : 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时间效率 : ................... ☆─────────────────────────────────────☆ mmd (mmd) 于 (Tue Jun 12 13:51:15 2007) 提到: 赞不过这样写还是有点慢因为编译器会进行加法&&转换还是直接开个len的好 for(int i=0,len=strlen(s);i<len;++i); 【在 zercal (zercal) 的大作中提到: 】 : for(int i=0;s[i];i++)... : 一般都这样写吧... : for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了... : ................... ☆─────────────────────────────────────☆ mmd (mmd) 于 (Tue Jun 12 13:58:00 2007) 提到: 用strlen还是会多算一点东西最快的还是这样: for(char p=s;p;++p); 【在 mmd (mmd) 的大作中提到: 】 : 赞 : 不过这样写还是有点慢 : 因为编译器会进行加法&&转换 : ................... ☆─────────────────────────────────────☆ zercal (zercal) 于 (Tue Jun 12 13:58:08 2007) 提到: 【在 mmd (mmd) 的大作中提到: 】 : 赞 : 不过这样写还是有点慢 : 因为编译器会进行加法&&转换 : ................... 恩,每一次循环都要计算一次s+i,不过这些差距就不大了,理论上...真正的要写一下试试才知道... strlen真正的实现是很复杂的,速度很快,但是复杂度上O(n)是没错的... ☆─────────────────────────────────────☆ zercal (zercal) 于 (Tue Jun 12 14:00:38 2007) 提到: 【在 mmd (mmd) 的大作中提到: 】 : 用strlen还是会多算一点东西 : 最快的还是这样: : for(char p=s;p;++p); 果然是大牛~这样这是没得说了...虽然可读性相对差了点...不过效率才是王道阿
[返回单文区目录]

单文区文章阅读 [返回]

发信人: tyw (Inter&Ronnie), 信区: C.S
标  题: [合集] 对学生朋友的一点建议[zz]
发信站: 珞珈山水BBS站 (Wed Jul 25 16:05:13 2007), 站内

☆─────────────────────────────────────☆
   bewithu (36.2℃沸点o0 和你在一起) 于  (Mon Jun 11 13:47:10 2007)  提到:

对学生朋友的一点建议

2007年6月1日上午 11:09:00
发表者：Google（谷歌）中国工程研究院工程师方坤

    自去年春天加入谷歌，我曾多次随公司校园招聘团队一起走访各地院校，帮助公司发掘人才。利用这样的出差机会到处走走看看，饱览祖国大好河山，是我一点小小的私心。但更具挑战性、更激动人心的，还是和我未来的同事们过招，不打不相识嘛。一想到马上就要和这样优秀的
黄鸸ぷ鳎揖托朔懿灰眩婧薏坏孟衷诰吐蛞徽诺コ袒卑阉�/她拽回北京。

    然而，在面试过程中，我也相当惋惜地看到，由于种种主客观原因的限制，很多青春韶华的学子未能充分发挥出他们应有的潜力。这里我不讲成绩，只把我遇到过的一些普遍的问题归纳一下，希望对即将踏入社会的学生朋友们能有些许帮助。

    实战！实战！

    纸上得来终觉浅，绝知此事要躬行。对于一个未来的软件工程师来说，实际编程经验是相当重要的。我们会要求应聘者在紧凑的时间内编写大量的代码，从中考察应聘者的分析能力，编码速度，代码可读性，对所用编程语言的掌握程度，对边界条件与异常状况的处理，数据结构与
涌诘亩ㄒ澹绦蛟诵械男屎陀ζ刚卟榇砭来淼哪芰Φ鹊取�

    一口气列出这么多要求，听上去似乎过于苛刻，其实只要积累了足够的实战经验，每一个应聘者都完全可以满足这些最低限度的要求。

    我记得开复对于青年学子们有一个建议，大学四年，至少要编写 10 万行代码。不是每一个人都期望进入谷歌这样的顶级技术公司，但即使对开复的建议打个三折，也还有 3 万行呢，不努力，能行嘛。前来应聘的学生们在编写代码时暴露出这样那样的问题，大都可以归结到同一�
：锻炼太少。比如"for (int i = 0; i < strlen(s); ++i)"，没有实战经验的人，怎么可能意识到暗藏其间的效率陷阱。再比如内存泄漏，就和初恋一样，没有亲身经历过的人，不会有刻骨铭心的感受，而一旦经历，终身难忘，根本用不着你有多聪明。遗憾的是，我看到许多相当聪�
生写出来的代码只能用惨不忍睹来形容，真让我怀疑这是不是就是他们的第一次。大家不要怪谷歌要求高，恕我直言，如果不能持之以恒，下点儿苦功夫，不光谷歌一家，其它公司恐怕也是进不去的。

    北京、上海等地的学生，往往有更多实习、兼职机会，接受锻炼之余，还能攒下一笔小钱作零用之资。其它一些地区的学生也许就没有这么幸运，这就尤其需要积极主动，寻找机会，创造机会，把握机会。世界正在变平，互联网的发展改变着地球的面貌，让不发达地区的学生也能
菀椎亟哟サ椒⒋锏厍淖试础Ｇ安痪梦以谖靼灿龅揭桓鲅肽昀匆恢奔岢衷诒本┐笱У� ACM 网站上参赛、做题，我看他写出来的程序就确实比他大多数同学都要好一些。我相信，只要他能够持之以恒，还会取得更大的进步。我听说浙江大学的 ACM 网站、TopCoder 网站也都是
慕逃试矗行巳さ耐Р环烈豢矗凰渌底鼍喝饩嗬胝嬲娜砑⒒褂凶畔灾畋穑膊皇桓霾淮淼某龇⒌恪�

    在积累一定编码量的基础上，我建议大家总结经验教训，不断提高自我。如果几万行代码写下来，学 C++ 的不知道 const 怎么用，学 python 的没听说过 GIL，我看也没什么意思。到了这个阶段，我推荐大家读一些经典的进阶书籍，例如《Effective C++》、《Effective Java�
即使地处偏远地区，也可通过网上书店买到。（我建议编码量太少的同学就先不要读了，会走火入魔的。我见过有学生连引用和指针都没搞清楚，就在那里重载操作符的。）交流也很重要，如果能够与网上网下志同道合的朋友互相帮助，共同进步，当收事半功倍之效。在这一方面，各
Google Camp 也许能够起到一定作用。

    "我会写代码呀，为什么谷歌不要我？"

    一家外包公司或许会满足于雇佣仅能从事简单的、机械性的重复劳动的软件蓝领，而让谷歌苦苦寻觅的，乃是最优秀的软件工程师兼计算机科学家——是的，在谷歌，研究与开发融为一体，软件工程师与计算机科学家当然也合二为一。计算机这几年算是比较热的，能够得偿所愿挤
慊蒲喙刈ㄒ档难际侨泄ゼ獾娜瞬牛绻笱哪昊奈哐б担茨苋〉秸婢朔蚜苏庖焕粗灰椎难盎幔遣皇翘上Я四亍� 遍历一个数组或链表的时间复杂度是多少？对于这样一个不是问题的问题，竟然各地都有相当数量的学生回答说是 O(logN)！有一次我实在
×耍崾居ζ傅难担�"你是如何理解'遍历'一词的涵义呢？"他立刻做恍然大悟状，回答说："哦，对，应该是 O(NlogN)"。我当时失望得一句话都说不出来。类似的例子还有很多。坊间一直传说谷歌的面试题有多难，其实大多数学生都卡在最基础的问题上。少数人费尽气力要收集
霉拿媸蕴猓涫滴颐谴蠖嗍饽慷祭醋曰蚋谋嘧跃浼扑慊蒲Ы滩牡南疤狻�

    顺便提一句，上面提到的那个答错的学生乃是一流大学中成绩名列前茅的优秀生，门门功课（包括所有计算机专业课）均在 90 分以上。反差何其大也！

    诚信为本

    我曾服务于多家公司，注意到不同的公司之间，乃至同一公司内不同的面试官之间，对应聘者的要求都会有所差别，或看重潜质，或偏好经验，或强调态度。但有一点大家是共同的：如果应聘者在诚信上有疑问，谁也不敢要。总体而言，现在的学生其诚信还是相当不错的，大大�
我们的期望。然而，不和谐音也还是有的。我们曾在某著名高校进行笔试，就发现有学生严重作弊，他们毁掉自己的机会不说，整个学校的名声也受到拖累。面试中偶尔也能遇到诚信堪忧的学生。有一次我出了一道题，前来应聘的学生明明以前见过这道题，却告诉我说没见过，自以为
伤且蛔菁词诺慕器镆恍δ睦锾拥霉业难劬ΑＡ降阒渲毕咦疃蹋嫡婊白罴虻ァ�

    做最好的自己不是每一个人都会加入某一家具体的公司，但每一个人都可以成功，成为最好的自己。我这里所谈，既不系统亦欠简练，但确实是我在几次校园招聘之旅中发现的一些具有共性的问题，故不避好为人师之讥，罗列于此。我当然知道，本文的首要目标读者——大一新生
暗模歉敢獍阉械拇砦笄鬃灾胤敢槐椤；八淙绱耍灰芄欢砸桓鲅兴舻希业氖奔渚筒凰惆追选�
※ 修改:·Crimkura 于 Jun 11 18:30:29 修改本文·[FROM: 222.20.237.*]
※ 来源:·珞珈山水BBS站

http://bbs.whu.edu.cn·[FROM: 222.20.236.*]

☆─────────────────────────────────────☆
   zaneblue (道行不够||go on working) 于  (Mon Jun 11 14:16:24 2007)  提到:

很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指每次
循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不是得
浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时间效率
那么重要啊,
无知了~~~

【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】
: 对学生朋友的一点建议
: 2007年6月1日上午 11:09:00
: 发表者：Google（谷歌）中国工程研究院工程师方坤
: ...................

☆─────────────────────────────────────☆
   bewithu (36.2℃沸点o0 和你在一起) 于  (Mon Jun 11 14:36:27 2007)  提到:

你觉得 strlen(s) 的计算不需要内存的么
【在 zaneblue (道行不够||go on working) 的大作中提到: 】
: 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指..
: 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不..
: 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时�..
: ...................

☆─────────────────────────────────────☆
   zaneblue (道行不够||go on working) 于  (Mon Jun 11 14:40:34 2007)  提到:

这个应该用完后立即挥手了吧
设计strlen的人应该会考虑这些,主要还是时间吧
【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】
: 你觉得 strlen(s) 的计算不需要内存的么

☆─────────────────────────────────────☆
   zercal (zercal) 于  (Tue Jun 12 12:06:27 2007)  提到:

【在 zaneblue (道行不够||go on working) 的大作中提到: 】
: 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指..
: 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不..
: 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时�..
: ...................

for(int i=0;s[i];i++)...
一般都这样写吧...
for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了...

☆─────────────────────────────────────☆
   zaneblue (道行不够||go on working) 于  (Tue Jun 12 12:07:35 2007)  提到:

恩
【在 zercal (zercal) 的大作中提到: 】
: for(int i=0;s[i];i++)...
: 一般都这样写吧...
: for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了...

☆─────────────────────────────────────☆
   zjq (鉴真) 于  (Tue Jun 12 12:28:49 2007)  提到:

如果在循环里面s的长度在变化，那么这样写就是必需的！

【在 zaneblue (道行不够||go on working) 的大作中提到: 】
: 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指..
: 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不..
: 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时?.
: ...................

☆─────────────────────────────────────☆
   mmd (mmd) 于  (Tue Jun 12 13:33:24 2007)  提到:

就算变化也不能这么写

【在 zjq (鉴真) 的大作中提到: 】
: 如果在循环里面s的长度在变化，那么这样写就是必需的！

☆─────────────────────────────────────☆
   zercal (zercal) 于  (Tue Jun 12 13:36:30 2007)  提到:

【在 zjq (鉴真) 的大作中提到: 】
: 如果在循环里面s的长度在变化，那么这样写就是必需的！

......不管什么时候都不能这样写...
明明可以O(n),你非要O(n^2)...
for(i=0;s[i];i++)跟那样的效果是一样的...

☆─────────────────────────────────────☆
   zercal (zercal) 于  (Tue Jun 12 13:46:35 2007)  提到:

【在 bewithu (36.2℃沸点o0 和你在一起) 的大作中提到: 】
: 你觉得 strlen(s) 的计算不需要内存的么

strlen的原型大概上应该是这样的:
int strlen(char s[])
{
  int i;
  i=0;
  while(s[i])/*等同于s[i]!='\0'*/
  {
    i++;
   }
  return i;
}
这个函数本身就是O(n)的,而子函数内部定义变量占用的内存,会在return时交还给系统的
...

☆─────────────────────────────────────☆
   mmd (mmd) 于  (Tue Jun 12 13:46:44 2007)  提到:

一个变量算不上什么内存开销

你这个也不想开销的话就写在for里面

【在 zaneblue (道行不够||go on working) 的大作中提到: 】
: 很弱智的问下: for (int i = 0; i < strlen(s); ++i)"，这句的效率陷阱是不是指每次
: 循环都计算strlen(s)所产生的时间开销啊...如果不这样而提前获得strlen的话那不是得
: 浪费一个变量么,会影响程序可读性以及内存开销啊,这两个比起来,前者所强调的时间效率
: ...................

☆─────────────────────────────────────☆
   mmd (mmd) 于  (Tue Jun 12 13:51:15 2007)  提到:

赞
不过这样写还是有点慢
因为编译器会进行加法&&转换
还是直接开个len的好
for(int i=0,len=strlen(s);i<len;++i);

【在 zercal (zercal) 的大作中提到: 】
: for(int i=0;s[i];i++)...
: 一般都这样写吧...
: for(i=0;i<strlen(s);i++)把O(n)的复杂度提升到O(n^2)了...
: ...................

☆─────────────────────────────────────☆
   mmd (mmd) 于  (Tue Jun 12 13:58:00 2007)  提到:

用strlen还是会多算一点东西
最快的还是这样:
for(char *p=s;*p;++p);

【在 mmd (mmd) 的大作中提到: 】
: 赞
: 不过这样写还是有点慢
: 因为编译器会进行加法&&转换
: ...................

☆─────────────────────────────────────☆
   zercal (zercal) 于  (Tue Jun 12 13:58:08 2007)  提到:

【在 mmd (mmd) 的大作中提到: 】
: 赞
: 不过这样写还是有点慢
: 因为编译器会进行加法&&转换
: ...................

恩,每一次循环都要计算一次s+i,不过这些差距就不大了,理论上...真正的要写一下试试才
知道...
strlen真正的实现是很复杂的,速度很快,但是复杂度上O(n)是没错的...

☆─────────────────────────────────────☆
   zercal (zercal) 于  (Tue Jun 12 14:00:38 2007)  提到:

【在 mmd (mmd) 的大作中提到: 】
: 用strlen还是会多算一点东西
: 最快的还是这样:
: for(char *p=s;*p;++p);

果然是大牛~这样这是没得说了...虽然可读性相对差了点...不过效率才是王道阿

[返回单文区目录]