分享 关于算法, 我们该学什么?

luikore · 发布于 2014年1月12日 · 最后由 mal5338 回复于 2014年3月05日 · 10928 次阅读
2880
本帖已被设为精华帖!

如果给你一个改进算法的任务, 你是盲头苍蝇的 google 又 google 试了又试, 还是利用算法知识一下找到问题所在? 以我浅薄的经验, 觉得应该学的是这些:

  • 寄存器, 内存, 硬盘, IO 操作速度的不同之处
  • 时间/空间复杂度, 大 O 记法, 多项式复杂度的基本概念
  • 单/多递归函数的时间/空间复杂度
  • 工作语言中的常用操作的复杂度 (例如 array.index? 的最佳和最差情况)
  • 二分和排序等常见的 log(n) 或者 n log(n) 的算法 (进阶: 大 L 记法, 其他复杂度类别).
  • 给一个简单问题知道该用/搜什么算法或者API去解决 (这是经验), 不知道算法名称但能直接写代码搞定其实更好 (这是能力)...

 

如果要求底层算法:

  • 文件 IO 和 mmap
  • 几种基本内存管理的实现 (malloc, memory pool, arena, reference counting, trace GC 等)
  • CPU 架构: 高级缓存, page fault, cache miss, cache line, cache oblivion 等概念和应用
  • CPU 架构: 流水线, 分支预测, 超向量指令等概念和应用

 

如果关心计算并行化:

  • task parallel 和 data parallel 的基本概念
  • 差分方程和母函数法的应用
  • 把简单的算术运算转换成矩阵运算
  • 认出可以优化成 c 倍快或者 log(c) 倍快的代码模式 (其中 c 是核的数目)

 

如果是数据分析, 暂时只想到这些:

  • PAC learning 评价选择适合业务的算法 (关于这个数学框架 Tom Mitchell 的 Machine Learning 有详述)
  • 反向传播算法(在神经网络, SGD, 各种数值系统都有广泛应用)和 viterbi 算法(在RCG语法解析, 隐马尔可夫模型, 条件随机场, 和电子方面都有广泛应用)
共收到 59 条回复
3
lgn21st · #1 · 2014年1月12日

大赞,新年伊始,吕哥给我们挖了这么大一个坑,加精,沙发坐等吕哥填坑。

2880
luikore · #2 · 2014年1月12日

#1楼 @lgn21st 已经写完了... 等楼下补充和删除...

96
hxtheone · #3 · 2014年1月12日

感觉算法这个话题能深入挖掘的太多了,坐等补充~~

2466
rasefon · #4 · 2014年1月13日

确实太多了,基本分类的大概有,程序语言方面的,体系结构方面的,图形图像方面的,网络方面的,近期比较热门的是关于数据处理的内容。

2880
luikore · #5 · 2014年1月13日

#4楼 @rasefon 加起来说不定有有几千种算法, 有些是谁都写得出的根本不用记, 有些记了也没用, 需要的时候就搜好了... 但只要有了基础, 不管要掌握和应用哪种都很快, 所以才列了那些...

1289
pepsin · #6 · 2014年1月13日

啊,矩阵,永远的痛,CSS里的矩阵直接绕着走。。。必须学了

681
sevk · #7 · 2014年1月13日

整体结构设计也很重要。数据库IO和网络IO算不算?

157
raven · #8 · 2014年1月13日

收藏先,等以后要用到的时候再来看。。 用不到的时候学了也很难记住。。

4482
tuliang · #9 · 2014年1月13日

我觉得大部分算法不用了解细节,但是必须知道什么问题需要用什么算法。楼主部分解决了这个问题

3930
fengkuok · #10 · 2014年1月13日

一说算法头晕犯迷糊,一问三不知。。。咋办好

29
mvj3 · #11 · 2014年1月13日

#2楼 @luikore 赞"给一个简单问题知道该用/搜什么算法或者API去解决 (这是经验), 不知道算法名称但能直接写代码搞定其实更好 (这是能力)...",我怎么感觉你不去做云计算方面的工作真是可惜了。。。

1031
zw963 · #12 · 2014年1月13日

......

96
bhuztez · #13 · 2014年1月13日 1 个赞

有用么,能通过面试么?

7263
assassinpig · #14 · 2014年1月13日

大神,文件 IO 和 mmap 这些是系统编程层面的,不是算法吧?

96
mykay · #15 · 2014年1月13日

个人感觉算法是个很神奇的东西

1289
pepsin · #16 · 2014年1月13日

#14楼 @assassinpig 算法就是用来针对性弥补硬件性能缺憾的啊

29
mvj3 · #17 · 2014年1月13日

#14楼 @assassinpig 用算法解决问题有三个角度,1, CPU组织, 2, IO组织, 3, CPU和IO互换。

2880
luikore · #18 · 2014年1月13日

#13楼 @bhuztez 大概不能...

#14楼 @assassinpig 其实有根据磁盘的 buffer 大小来做优化的, 还有针对 raid 磁盘和 mmap 写的数据结构... 帮助理解数据库源代码应该挺有用

96
bhuztez · #19 · 2014年1月13日

#18楼 @luikore 不能学个屁啊 ...

2622
jjym · #20 · 2014年1月13日
2880
luikore · #21 · 2014年1月13日

#19楼 @bhuztez 那是面经和面试官心理学要解决的问题...

1232
tony612 · #22 · 2014年1月13日

话说,ruby的matrix运算有做优化么?

96
jiang_plus · #23 · 2014年1月13日 1 个赞

补充一下:

  • 数据库索引的概念和索引设计技巧
  • 状态机的概念和正则表达式
2466
rasefon · #24 · 2014年1月13日

#19楼 @bhuztez 人生最重要的事情,不就是找到你真正喜欢的东西嘛。你喜欢算法么?

3253
cisolarix · #25 · 2014年1月13日

艾玛,巨坑啊。

96
krazy · #26 · 2014年1月13日

划重点了 好high!

96
yaonie084 · #27 · 2014年1月13日

我觉得数据挖掘的话。。。。知道原理和应用就好,基本上都有相关的算法包。比如libsvm什么的。。要是把里面的公式推导都搞通了,读个博士问题不大,顺便还能发几篇SCI。

96
bhuztez · #28 · 2014年1月13日

#27楼 @yaonie084

要是把里面的公式推导都搞通了

有这么简单?

1411
zeeler · #29 · 2014年1月13日

牛啊,都搞明白了没。。。

96
xranthoar · #30 · 2014年1月13日

学好计算机本科大一到大三该学的。。

96
xranthoar · #31 · 2014年1月13日

#27楼 @yaonie084 CS 的谁发 SCI 啊

7895
chrishine · #32 · 2014年1月14日

计算机是应用科学,学习算法其实没太大用,大部分人也无需去学算法.学习算法是应用数学系和CS的某些博士干的事情. 学会应用算法就行了,应用算法上面再加一点点稍微的要求——高效优美的实现算法.拿最简单的倒置数字来说,13倒置成31,不考虑10,100的处理,不考虑溢出.如何算优美写出,而不是反正实现了. 如何学会应用算法?手熟多练.

96
iallai · #34 · 2014年1月15日

#33楼 @bugmenot mark掉

487
blackanger · #35 · 2014年1月15日

慢慢填坑

8893
yanguango · #36 · 2014年1月15日

我先把微积分,线性代数,概率论恶补一遍,深深觉得这是我的瓶颈了

6375
wushexu · #37 · 2014年1月15日

不同领域需要的基础不一样。例如数据挖掘、机器学习、DSP(数字信号处理)、模式识别领域,当然这些领域每一个都很大,有非常多的算法。 在很多AI相关的领域,概率和数理统计的知识是最为重要的。

6375
wushexu · #38 · 2014年1月15日

#36楼 @yanguango 数学好,什么都可以玩;数学不好,什么都玩不起

2466
rasefon · #39 · 2014年1月15日

#37楼 @wushexu 概率和数理统计在AI里重要,是因为AI只能靠这些,没有真正意义上的那种理想化具有思考能力的‘AI’。不要说AI,连真正的随机数,都没法生成。

6375
wushexu · #40 · 2014年1月15日

#39楼 @rasefon AI太复杂,没法建立精确的模型,只能采用概率和统计的办法去解决。而且,计算、推理所依据的信息是有限的,甚至是不准确的,就算有一个精确的模型,也不可能得到精确的结果。实际上人的大脑的运算过程也不太可能是精确的。 真正的随机数是可以生成的,有多种办法。例如电子噪声、宇宙微波辐射,都认为是随机源。

2466
rasefon · #41 · 2014年1月15日

#40楼 @wushexu 你说的随机数生成,我不懂。对随机这个概念我就从来没想清楚过,我潜意识里面觉得跟不上就不存在随机。。。

96
xranthoar · #42 · 2014年1月16日

#39楼 @rasefon AI 和随机数怎么关联上的?

96
xranthoar · #43 · 2014年1月16日

#32楼 @chrishine 也不能说没用,这是某种智力标记吧

5083
xiaoxiao · #44 · 2014年1月16日 1 个赞

望其项背

1289
pepsin · #45 · 2014年1月16日

#42楼 @xranthoar 人的多数灵感,就是随机数碰撞到特定知识结构产生的。其实蛮重要。

96
xranthoar · #46 · 2014年1月17日

#45楼 @pepsin 如果你真的对随机数感兴趣的话,这儿有个量子随机数生成器,至于这是不是真随机我就不分辨了~

4316
pascallijuan · #47 · 2014年1月17日

越看越糊涂

5485
crazyjin · #48 · 2014年1月18日

唉唉。。。暂不提算法。。。

96
qianjigui · #49 · 2014年1月19日 1 个赞

具体业务逻辑的抽象,最后可以归结到纯数学问题. 而针对数学问题的具体处理与分析, 一些好的方法是通过抽象算法进行描述与处理.

从计算机系统的全技术栈,就可以找到很多算法技术. http://www.infoq.com/cn/news/2013/11/Core-algorithms-deployed

96
gamever · #50 · 2014年1月21日 2 个赞

算法还是应该和具体的问题相结合,算法主要还是为了解决问题,分析问题,解决问题。

96
turingbook · #51 · 2014年1月23日

#36楼 @yanguango 别忘了分享过程

11258
asdf · #52 · 2014年1月27日

Great!

709
suffering · #54 · 2014年2月12日

数据结构很重要, 很多算法依赖于数据结构的设计. 推荐看<算法导论>.看完了, 差不多"不惑"了. 算法的标准只有两条, 有效性以及效率. 如果对算法效率的要求深究到CPU底层实现的地步, 那ruby就不合适了, 用C吧.

55楼 已删除
64
linjunhalida · #56 · 2014年2月13日

游戏要的是伪随机,真随机不能用的,不然调试不会重现问题。

11694
a307697028 · #57 · 2014年2月27日

学习了。

9765
unieagle · #58 · 2014年3月03日

大神帖子要顶!!!! 这每一项拆开了都好多内容··

10432
mal5338 · #59 · 2014年3月05日

学习

12224
Guest · #60 · 2014年6月24日

赞 :plus1: 你是盲头苍蝇的 google 又 google 试了又试, 还是利用算法知识一下找到问题所在? 可否举例? 只会Google的求解。怎样可以减少Google之“鱼”,而能“渔”?

需要 登录 后方可回复, 如果你还没有账号请点击这里 注册