继续安利
https://ocw.mit.edu/courses/audio-video-courses/#electrical-engineering-and-computer-science
(需要翻墙，里面的视频都是 powered by youtube )
6.042 6.006 6.046sma 6.046j-2015 6.172 6.851 6.854
（6.042还没看，不过是个cs数学基础课，早晚看之,6.854太难看不进去，大概要放到以后了）
多希望自己是大二的时候发现这些啊。。。(而不是垠神的吹B博客，划掉，顺便感谢垠神。。。)其实大二的时候看过网易公开课上的6.046jsma。可是当时太naive了。根本没能理解课程中的精妙之处。最近才发觉这课有多好。我属于看书瞬间走神睡着那种。看公开课记笔记还能多坚持一会。
为什么我没完没了的安利这些课呢？这个要从学算法这个事说起了。我们入门时学的算法往往是基于RAM model的（Random Access Machine）。这个其实非常有道理，相对来说，这个模型很符合“直觉”，内存就是个大数组，操作一下读或写一个内存位置。学组成原理的时候，最开始造出来的东西也大概是这个样子。我们学的大多数算法和数据结构都是在这个模型上的。
可是这个模型真的足够好吗？不见得，6.006第二课整出个词，叫python model，就是拿python来写伪代码。在model里直接可以用O(1)的集合，O(1)的list等等。用起来就比RAM(约等于不考虑其他因素的C)方便许多。6.851最后一课里，集中介绍了各种各样的考虑缓存的model,Disk-Access-Model,Cache-Oblivious-Model 等等。能高效利用缓存的算法比RAM下最快的算法还要快很多。因为RAM里根本没考虑缓存。6.172里介绍了spawn-sync式的并行框架cilkplus，看起来确实非常优雅。还介绍了锁，无锁等高大上的东西。。。再找性能就是分布式了，这方面还没看，说不出话。（6.046j-2015和6.172里有介绍。）
扯上面那一段，就是想说RAM既不是最简单的模型，也不是最能挖掘性能的模型，只是出于历史原因和相对足够好，我们一直在使用它而已。我们不该只满足于RAM下最优的结果。学算法很大程度上就是为了性能，而为了性能，没理由一直无视缓存和并行的存在。
尤其是缓存，要不为啥我们要用B-tree?要不为啥6.172 LEC19里能整出一种写性能比B-tree好得多的结构。也正是因为缓存的存在，数组才会比我们一般认为的快得多。很多我们以为是O(N)的东西。可能其实是O(N/B)。好吧，这俩没区别。。。说不明白啊，看6.046,6.851，6.172吧。。-_-
学东西经常出现一种情况，就是学到一个概念之后，忽然间，之前学的东西都要因为这个引入的新概念刷新一遍。然后之前的知识就进化成亚种了。至少以后再学到一个算法，我会想想能不能并行，访问缓存的时空局部性怎么样。数据结构的话，有没有cache-oblivious版本，有没有succinct版本，有没有加锁的版本，有没有函数式版本。(然后发现最简单的版本都写不出来 (:з)∠) )
拽了这么多专业的词儿，打游戏去了。。。
网友评论