《吴军-Google方法论》 DSA、教育、思维、逻辑、智慧

1. 计算机数据结构

  1. 专业绘画的都会先素描框(使用基本的几何图形、结构和组成),画好框架骨骼,在细化绘画元素(画鱼思考)
  2. 大的艺术家有时候未打稿,原因是相关草稿已了然于胸了
  3. 计算机科学完成一个程序,有两种方式(一种是一行行代码去写,另一种是提前做好相关集合图像的规划,这些几何图形的规划在计算机科学中就是数据结构)
  4. 程序=数据结构+算法,数据等同于点,数据结构等同于数据中的具体关系(比如队列、栈、二叉树等都有自己的特定)
  5. 常用线性表数据结构:
    • 数组(插入需要移动大量元素,寻找容易,只需要提供数组下标)
    • 链表(插入方便,但寻找需要基于链表的首地址开始,元素很大时候效率很低)
  6. 对比数组和链表,凡事有一列也有一弊

专业和业余人士做东西的一个重要区别,前者掌握了使用基本的几何图形、结构、组合来构建复杂的设计和系统的方法,后者只是根据自己脑子里面的构思和直觉,直接构建最终的产品和设计

2. 二叉树

  1. 计算机科学中,相对的大小比绝对的数量更重要(真实世界是具体数值重要还是,数值间的相对大小(或次序)更重要?)
  2. 有什么样的问题就有什么样的工具,测量的重要性(时间上面的钟、测量长度尺子、化学中的反应当量等)
  3. 二叉树:首先是一颗树,且每个节点至多有两个子节点;
  4. 检索二叉树:二叉树的子类,数上的任一节点,比该节点左子树都大,比右子树都小
  5. 二叉树浓缩了很多概念:分叉、层层递进、有序

3. 锦标赛排序算法(N个选手中选K个选手)

  1. 算法说明:
    1. 将所有数字放入二叉树的叶子节点,按比赛规则,两两比较选出最大的
    2. 对于第二大的,从所有被最大的数字淘汰的数字中选择
  2. 算法复杂度:第一名的只需要N,第二名的增加LogN次计算,第三名也是增加LogN
  3. 25人短跑比赛,有5个赛道,单轮淘汰赛,如何最快角逐金银铜前3名?
    1. 前5轮:25人分5组(A1~A5,…E1~E5),角逐每组第1
    2. 第6轮:每组第1再赛一轮(假定A1,B1,C1,D1,E1),角逐冠军(假定为A1)
    3. 第7轮:由于只要前3,故D、E两组已被淘汰(如果还继续比较则为无用功),因此亚军、季军候选只需要从A、B、C组挑选(A2、A3、B1、B2、C1),再一起赛一轮可知
  4. 归纳起来:
    1. 少做无用功
    2. 善用信息

4. Google地图最短路径算法

  1. 假如你再开发一款地图应用,如何找到离你最近的5个加油站
  2. 很重要的第一步,解题之前,先读懂题目
    • 人和开车找位置的差别,对人来说200m都可能很远,但对开车来说,2.3公里和2.5公里没有太大差别,可能还有堵车的问题
    • 搞清楚每一个加油站和汽车的位置,以及行车方向,汽车是移动的通过GPS导航,是基于坐标、还是房屋门牌
    • 搞清楚行车方向
    • 距离不是欧几里得直线距离,两点之间的路可能有很多种,基于动态规划可以获取两点间的最短距离
    • 按距离排序,找到最近的5个加油站距离(排序是一类解决方式,但效率不是最高的)
  3. 回到问题原点:
    • 没有必要针对很远的加油站排序,浪费资源
    • 基于二叉树的细类堆数据结构,可以满足N个数据排序前K个的数据算法复杂度:第1的只需要N,第2的增加LogN次计算,第3的也是增加LogN)次计算(这里就差了一个工程数量级,淘宝求全年销售top10差距就更大)
  4. 继续回到问题原点:
    • 考虑到地图被很多人使用,在求解路径过程时候,A到E点、B到E点、C到E点,其中可能很多复用的线路,我们可以提前计算好存储起来,在求解某条最短路径时候,只需要通过服务调取出来即可,会降低很大的重复计算量
  5. 大数据思维,很重要一条就是是将所有事件统一起来,全局性的优化
  6. 归纳起来:
    1. 少做无用功
    2. 很多事情遵循统一个规律(最短路径、N中TopK、堆),学习理论需要思考理论提出的时候,要解决的应用问题是什么,搞清楚这块才有可能一通百通
    3. 解决问题时候,我们不知不觉做了很多前提假设,适当回到原点,重新读懂问题(产品思维也是强调从不同用户角度看问题,跳出局限性)
    4. 好的面试官会引导,不怕刷题的

5. 好算法对效率影响

  1. 计算机科学做事原则:构建理想环境,确定比较标准(事先讲好游戏规则,再做研究,确定基线)
  2. 计算机思维本质是翻译,解决问题共性地方形成了算法,构成了计算机科学的基础
  3. 吴军大学实习,财务系统数据量级问题
  4. 计算机是要处理大数的,工程师需要对计算资源数量有概念
  5. 评判算法好坏,高德纳思想:
    • 考虑接近极限的情况(计算机用于处理大数)
    • 算法快慢两类决定性因素:不随数量变化的因素,随数量变化的因素(10N^2之前的系数,可以忽略)
    • 计算机科学中,两类算法量级一样,则认为他们速度一致
  6. 回顾科学发展史,将问题抽象,过滤次要因素,构建理想环境(但并非不考虑现实)

6. 高效率的本质

  1. 对比冒泡,插入排序,都是同量级O(n^2)
  2. 提高算法效率本质是让计算机少做事,做有效率的事情,减少对比次数,归并排序(先自顶向下细分,再自底向上合并),O(NlogN)
  3. 效率=产出/所做的事情,人的产出很难提高,但做的事情可以减少
  4. 自己苦思冥想一个月或者一年,可能一周或者一个月,学习并练习,就可能足够了
  5. 今天常用的快速排序,是计算机诞生13年后产生的,是自己冥想,还是学习?

7. 谈快速排序:少做事情

  1. 最好的算法,是考虑一般情况,还是最差的极限情况
  2. 吴军从东三环去机场选路问题
  3. 世上没有绝对的最好
  4. 目前通常情况下,最好算法是快速排序,其思想还是少做事:
    • 从一堆无序数字中,随机挑选一个数字(称为枢值),以枢值为界限,将数字分成大于和小于的两部分(总共两堆)
    • 在大于和小于的数字堆中,再随机挑选一个枢值,继续以该枢值为界限,将数字分成大于和小于的两部分(总共四堆)
    • 依次上面的戏法,直至最后都排序好
    • 算法复杂度:O(NlogN),科学上和归并排序一样好,但工程上面一般情况比归并排序块两倍
  5. 归并排序:2万学生分10个学习,每个学校2000人按成绩挑学习好的学生
  6. 快速排序:2万学生,划几分数线,学生成绩和分数比较,挑学习好的学生
  7. 计算机和组织的管理,乃至社会的管理,想要提高效率就是少做事情(学生成绩从0~100教,老师也很难办)
  8. 每个底层员工要做的事情,就是快速进入更高层

8. 计算机科学和工程的差别

  1. 计算机科学是方向,工程则是沿着方向建设道路
  2. 关注是事情不同,环境也有差异;科学不过分考虑资源的边界效应,抽象出理想环境,算法上面几倍的提升,没有太多意义,而工程哪怕20%的效率也是值得的
  3. 中国大学制造超级计算机,只能说明工程比较厉害
  4. 和钱的距离
  5. 思维转变,现实到理想,吴军经历科学、工程、再到科学的道路
  6. 机器学习模型,20兆到3兆的意义
  7. Google工程上面2%的计算资源优化,足矣让一个工程师花一个季度时间投入优化
  8. 优化的价值和意义,在工程和科学上面是不一样的
  9. 计算机科学关注在量级上面,而不太在意细小成本;在计算机工程上面,必须先使用科学上面最优方法,再做细节改进

9. 做减法

  1. 首先要对一个学科,一个整体的知识体系有完整而深刻的理解,抓住主干
  2. 抽象不容易,如果一些概念抽象不了,不要勉强
  3. 认识是不断进步的,早先理解的本质,以后看来可能会很浅显,随着见识不断攀升,对一个问题的理解会越来越透彻
  4. 事物的本质应该是简单的
  5. 抽象是筛选的过程,抓大放小,突出主要,过滤次要,寻求本质的过程:
    • 明确抽象的目的
    • 明确抽象的结构
    • 检验抽象的效果:见识、视野、实战,洞悉本质
  6. 按一定原则分类,有助于提高效率,但过分强调公平,效率就提升不上去
  7. 做减法不等于不做事,职场中稍微有经验的领导,都不会指望新人可以挑重担,和臭棋篓子下棋,会越下越臭
  8. 做事情,做得多,5个50分,不如一个100分
  9. 送礼品,宁可送一个让她记住一辈子的东西
  10. 《算法导论》
  11. 软实力:看透钱;学会服从、合作、当助手和领导;认清边界;成为健全的人;树立信仰;

10. 计算机思维

  1. 计算机思维:智能时代,学会计算机思维方式
  2. 工程师的直觉:一个房间可以装多少高尔夫球,没有数据之前不要轻易给答案
  3. 工程师的极限:尝试永动机、水发电,遵循科学理论和极限,不为不可能的事情浪费时间
  4. 在边界内做事:在极限内寻找答案,不浪费时间做超越极限事情(不要动不动就超越极限)
  5. 量级思维:芝麻、西瓜、大象、地球、太阳、银河,成就=成功率x事情的量级x做事的速度
  6. 把事情做好的三条边:基线、极限、阶梯,认清当下,明确目标方向,找到持续前进的道路
  7. 粗调和精调:显微镜的目镜和物镜螺旋按钮、100层楼丢球,不用粗调只用精调,不仅做事效率会低,而且可能由于方向不对,导致最后放弃

11. 发明的逻辑

  1. 早期飞行的发明:
    1. 有条件可以将目标定得高远一些
    2. 模仿不可耻,可耻是走不出模仿
    3. 违背常理的,很多源于我们感性的认知和做法
    4. 勇于承认错误,不至于在错误道路上滑得太远
    5. 成功需要等到风云汇聚,天时地利人和
  2. 莱特兄弟对飞机贡献:实验和测试的重要性,不要莽撞的推出产品;成功最重要的是走出模仿;
  3. 计算机发明过程:
    1. 人们总是根据不断的增加需求,增加系统的复杂性,等待系统非常复杂,就需要有人能够从更高的层次维度思考,搞清楚系统的本质,然后用简单办法解决
    2. 世界的奥秘在于搞清楚他们的基本单元和他们之间的关系
    3. 东西越做越复杂,就是化繁为简的时候了
    4. 大的目标需要拆解成简单的一个个解决,一个复杂问题拆解成两个简单问题,成功解决可能性就大了很多(这个不等同于做了两个收益很小的事情,就等于做了一件大事情)

12. 教育和学习

  1. 学好语文、数学、历史,科学:培养好沟通、个人素养,思维逻辑,看清楚自己位置,以及科学看待问题和讲道理的人
  2. 上好大学目的:提升自己格局,让自己可以在社会养活自己,从社会消费者到贡献者的必要训练
  3. 大学五训练:看透钱、学会服从和合作、认清边界、成为健全的人、树立信仰

13. 人生和商业智慧

  1. 上帝喜欢笨人:事情一件件的做,不要并行处理;善始善终,做很多半途而废的事情,不如完成一两件小事;
  2. 一生要做的五件事:恋爱结婚生子、做自己喜欢的事情做到极致、回馈、有一个信仰、给社会留下遗产
  3. 超越免费:稀缺性、时效性、个性化、可用性、可靠性、粘性(数据、用户)
  4. APRU(Average Revenue Per User): 平均用户收入,抛弃不值钱的关注,有这些时间不如找一些真正可以帮组我们的朋友,为他们提供一些价值
  5. 中美生活习惯差异:家庭观念(中国人家族、美国家庭)、做事方式(计划性和随意性)、任何人直接的距离(对隐私的看重)、父母和孩子的关系(成人即独立)、公私分明(下班私人时间看重)、主动性(很早就找到老板说明自己的职业发展计划,希望老板支持和配合)

14. 走出死循环

  1. 不要让孩子继承自己的焦虑(有欲望追求,满足不了或者凡事自己想把控);麦糠中的两粒谷子,不听也罢(GIGO,机器学习中的噪音数据);隔断或差异化地生活;
  2. 不要把上名校当成中进士,目光所及,即人生的境界;所谓的终生学习,是不断超越自己,超越别人;
  3. 多了解孩子,树立榜样(家长的懒惰,孩子会模仿);以后不在孩子面前玩手机,多一些高质量的陪伴(多陪陪孩子,了解具体情况,看看出了什么问题,多和孩子一起看看书,比上培训班要好很多了)
  4. 学习不是中彩票(相信自己的运气,不想通过努力),将教育当成人生的必须品,不用囫囵吞枣的学完,而是根据自己的兴趣一点一点的学下去,长期效应
  5. 学会生活,学会花钱(不要将钱投在阻碍在自己上升的地方),走不出贫困的人(时间和钱投入在哪了?)
  6. 不要迷恋公务员(高风险也不一定意味着高回报,但低风险一定没有高回报)