Chinaunix

标题: finding the first set bit in a machine word can all be O(lg(n)) [打印本页]

作者: luckysir 时间: 2012-03-27 21:34
标题: finding the first set bit in a machine word can all be O(lg(n))
这是从小工到专家这本书里边在说到二分法的时间复杂度时说的
如果是你的话，你会咋实现？

有个问题不明白，作者在这里是仅就二分法举一个例子呢，还是在实际应用中都这么用，因为一个机器字好像也不会太长，

作者: 塑料袋 时间: 2012-03-27 21:40
阿贝尔大师说过：应该阅读大师的而不是他们的门徒的著作

那本书的作者好像连门徒都算不上吧

作者: luckysir 时间: 2012-03-27 21:59
回复 2# 塑料袋

说的在理，可是门徒也比俺要高大诶，门徒离俺比较近，所以完全遮挡住了大师，

哎老了，我觉得我现在的进步速度像蜗牛

作者: OwnWaterloo 时间: 2012-03-27 22:02
回复 1# luckysir

应该仅仅是作为二分的一个例子。

实际使用上可以将这个作为保底的手段。对机器、编译器(暂时)不知情时至少有一段可以工作的C代码。

然后当必要时去找更好的手段。
比如如果知道机器是x86，就可以用bsr指令。
如果知道机器使用ieee754浮点格式，就可以利用它的指数部分。
如果知道编译器是vc或者gcc，就可以利用它们提供的扩展，名字我忘了……

作者: fanasy 时间: 2012-03-27 22:41
回复 2# 塑料袋

级别不到，看看门徒写的好书也不错，不过楼主这本书，我翻了一下就没兴趣了，没有阅读快感

作者: 塑料袋 时间: 2012-03-27 23:09
回复 5# fanasy

其实我灰常不明白，学习那些O(1),O(2)......O(100)之类的算法有个鸟用，包括哪些什么语言的窍门，编程的技巧.....都是雕虫小技而已，上不得台面。一句话：耍小聪明。

上的了台面的东西，一定是系统的，有组织的，能产生积累效应。而且越上的了台面的东西，一定是越需要基础强大的。

哥们大概4，5年前，去google面过一次，上来那边扯淡什么怎么有效率的算32bit里有多少个1，哥们直接一句话打回去：hweight64,hweight32，kernel这俩函数就是算这个的，现成的死路子；然后接着又问什么咬疯狗，说谎话的，越来越不着边，我就日的。我巨恶心这种面试，耍小聪明。

作者: 三月廿七 时间: 2012-03-27 23:16
本帖最后由三月廿七于 2012-03-27 23:19 编辑

回复 6# 塑料袋
我也是特别恶心这样的题目，
我第一次面试时遇到都是这类题目，结果那家公司现在已经灭了
而我后来去的公司，就问了一个简单的结构体问题，反而却是最大的xxx公司

我发现越是牛B的公司，题目出的越是简单~
就是那种山寨货特别喜欢装B～～

作者: 塑料袋 时间: 2012-03-27 23:20
回复 7# 三月廿七

哥们现在也面了不少人了，两项最重要：

1) 性格：坐得住，塌的下心
2) 基础：只要不太差强人意就可。

作者: 塑料袋 时间: 2012-03-27 23:23

三月廿七发表于 2012-03-27 23:16
回复 6# 塑料袋
我发现越是牛B的公司，题目出的越是简单~.

某些时候，你要真是以为简单，那就上套了。

哥们一个同事，面试别人时，总是问一个问题，memcpy，自己实现。

就这个问题，肯定地说，水要多深就有多深。

作者: 三月廿七 时间: 2012-03-27 23:46
本帖最后由三月廿七于 2012-03-27 23:47 编辑

回复 9# 塑料袋

你说说怎么个深的？我觉得这是个特别浅的问题啊

作者: 塑料袋 时间: 2012-03-27 23:49

三月廿七发表于 2012-03-27 23:46
回复 9# 塑料袋

你说说怎么个深的？我觉得这是个特别浅的问题啊

涉及architecture的太多东西，诸如边界对齐，预读，lockup-free cache.....................

作者: alexhak2004 时间: 2012-03-28 15:26
回复 11# 塑料袋

还可以包含一些汇编层面的东西。。。

作者: fanasy 时间: 2012-03-28 16:41
回复 6# 塑料袋

算法还是有用的，像 fgrep 对字符串的查找就用到了很好的算法，对fixed string 有很高的效率。前几天还在啃它用到的算法，可惜还没搞懂。
算法主要用在处理大数据中吧，当需要分析30G以上的数据时，没有好的算法，就只能找老板去买好机器了。（算法体现价值了，呵呵）
面试的话：我之前参加一个电话面试，问我一个现在觉得挺简单的算法问题，我没答好，就没下文了。
（不怕大家笑话：就是两个已序数列，再合成排序的算法）

作者: edshea 时间: 2012-03-28 18:13

fanasy 发表于 2012-03-28 16:41
回复 6# 塑料袋

合并两个有序数组，用归并排序不就行了

作者: starwing83 时间: 2012-03-28 22:43
本帖最后由 starwing83 于 2012-03-28 22:44 编辑

回复 11# 塑料袋

只要不用所谓word copy的那种tricks，单纯实现一个还是蛮简单的吧？char没有对齐问题的。cache的话，既然是copy，肯定是免不了的吧……如果有要求“尽可能快”，那………………

作者: starwing83 时间: 2012-03-28 22:46
回复 13# fanasy

归并能不能in-place？我只知道链表可以……

作者: fanasy 时间: 2012-03-30 10:47
回复 16# starwing83

可以，有原地归并算法。

作者: fanasy 时间: 2012-03-30 12:31
回复 14# edshea

对的，更好的是原地归并排序。

作者: 三月廿七 时间: 2012-03-30 12:35
回复 13# fanasy

/* 算法还是有用的，像 fgrep 对字符串的查找就用到了很好的算法，对fixed string 有很高的效率。前几天还在啃它用到的算法，可惜还没搞懂。*/

搞懂还好，搞不懂就亏了，

作者: 三月廿七 时间: 2012-03-30 12:37
本帖最后由三月廿七于 2012-03-30 12:38 编辑

edshea 发表于 2012-03-28 18:13
合并两个有序数组，用归并排序不就行了

是用归并，而不是归并排序，
归并排序是针对无序数组的，合并有序数组，还排序什么呀，？

作者: fanasy 时间: 2012-03-30 13:08
回复 19# 三月廿七

惰性来了，等过几天再看。

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)