finding the first set bit in a machine word can all be O(lg(n))

塑料袋

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

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

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

alexhak2004

回复 11# 塑料袋


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

fanasy

回复 6# 塑料袋


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

edshea

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

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

starwing83

回复 11# 塑料袋


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

starwing83

回复 13# fanasy


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

fanasy

回复 16# starwing83


    可以，有原地归并算法。

fanasy

回复 14# edshea


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

三月廿七

回复 13# fanasy


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

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

三月廿七

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

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