benben's Blog

1、分立元件与数字暴政

一开始，计算机都有独立组件构成，叫"分立元件"，然后不同组件再用线连在一起，这会导致计算机的构成很复杂，这个问题就叫做"数字暴政"。

2、集成电路与仙童半导体

封装复杂性：与其把多个独立部件用电线连在一起，拼装出计算机，不如把多个组件包在一起，变成一个新的独立组件。这种新的独立组件就叫集成电路(IC)，仙童半导体(用硅做成)让继承电路变成了现实。为了不用焊接或用一大堆线，发明了印刷电路板(PCB)，他通过用蚀刻金属线的方式把零件连接在一起。

3、光刻

即用光把复杂图案印到材料上。我们把一片薄片状的硅叫做晶圆，通过一系列生产步骤，将晶圆表面播磨的特定部分除去的工艺叫做光刻。
光刻组件示意图

光刻成品示意图

4、摩尔定律

每两年左右，得益于材料和制造技术的，同样大小的空间，能塞进两倍数量的晶体管。

5、进一步小型化会碰到的问题

1. 由于光的波长限制，精度已达到极限。
2. 量子隧穿效应：当晶体管非常小，电极之间可能只距离几个原子，电子会跳过间隙，会产生漏电问题。

1、对象

当任务庞大，函数太多，我们需要把函数打包成层级，把相关代码都放一起，打包成对象。对象可以包括其他对象、函数和变量。把函数打包成对象的思想叫做"面向对象编程"，面向对象的核心是隐藏复杂度，选择性的公布功能。

2、面向对象编程

把函数打包成对象的思想叫"面向对象编程"。

3、API

当团队接收到子团队编写的对象时，需要文档和程序编程家口(API)来帮助合作。API控制哪些函数和数据让外部访问，哪些仅供内部。

4、集成开发环境(IDE)

程序员用来专门写代码的工具。

5、调式(debug)

IDE帮你检查错误，并提供信息，帮你解决问题，这个过程叫调试。

6、文档与注释

文档一般放在一个叫做README的文件里，文档也可以直接写成"注释"，放在源代码里，注释是标记过的一段文字，编译代码时，注释会被忽略。注释的唯一作用是帮助开发者理解代码。

7、版本控制

版本控制，又称源代码管理。大型软件公司会把代码放在一个中心服务器上，叫"代码仓库"，程序员可以把想修改的代码借出，修改后再提交回代码仓库。版本控制可以跟踪所有变化，如果发现bug，全部或部分代码，可以"回滚"到之前的稳定版。

8、质量控制

测试可以统称"质量保证测试"(QA)，作用是找bug

9、beta alpha

beta版软件，即是软件接近完成，但没有完全被测试过，公司有时会向公众发布beta版，以帮助发现问题。alpha是beta前的版本，一般很粗糙，只能在内部测试。

0、可判断性问题

是否存在一种算法，输入正式逻辑语句 输出正确的"是"或"否"答案？

1、阿隆佐邱奇，Lambda算子

美国数学家 阿隆佐·丘奇，开发了一个叫"Lambda 算子"的数学表达系统，证明其不存在。

2、图灵机

只要有足够的规则，状态和纸带，图灵机可以解决一切计算问题。和图灵机一样完备，叫做图灵完备。

3、停机问题

证明图灵机不能解决所有问题。

4、图灵测试

向人和机器同时发消息，收到的回答无法判断哪个是人，哪个是计算机，则计算机达到了只能程度。

1、数组 下标

数组(Array)，也叫列表(list)或向量(Vector)，是一种数据结构。为了拿出数组中某个值，我们要指定一个下标(index)，大多数编程语言里，数组下标都从0开始，用方括号[]代表访问数组。注意：很容易混淆"数组中第5个数"和"数组下标为5的数"，数组下标为5的数是数组里面的第6个数。

2、字符串

即字母、数组、标点等组成的数组，字符串在内存里以0结尾。

3、矩阵

可以把矩阵看成数组的数组。

4、结构体

把几个有关系的变量存在一起叫做结构体。

5、指针

指针是一种特殊变量，指向一个内存地址，因此得名。

6、节点

以指针为变量的结构体叫节点。

7、链表

用节点可以做链表，链表是一种灵活数据结构，能存很多个节点(node)，灵活性是通过每个节点 指向 下一个节点实现的。链表可以是循环的也可以是非循环的，非循环的最后一个指针是0.

8、队列

"队列"就像邮局排队，谁先来就排前面，这叫先进先出(FIFO--first in first out)，可以把"栈"想成一堆松饼，做好一个新松饼，就堆在之前上面，吃的时候，是从最上面开始。

9、栈

栈是后进先出(LIFO)。

10、树

11、图

如果数据随意连接，有循环，我们称之为图

0、基本概念

算法：解决问题的基本步骤

1、选择排序：

数组：一组数据
选择排序的复杂度为O(n²)

2、大O表示法

大O表示法(算法)的复杂度：算法的输入大小和运行步骤之间的关系，来表示运行速度的量级。

3、归并排序

归并排序的算法复杂度为O(n*log n)，n是需要比较+合并的次数，和数组大小成正比，log n是合并步骤所需的次数，归并排序比选择排序更有效率。

4、Dijkstra算法

一开始复杂度为O(n²)，后来复杂度为O(nlog n + l)，n表示节点数，l表示有多少条线。

1、变量、赋值语句

如a=5，其中a为可赋值的量，叫做变量。把数字5放a里面，这叫"赋值语句"，即把一个值赋给另一个变量

2、if判断

可以想成是"如果x为真，那么执行y"，反之则不执行"y"，if语句就像岔路口，走哪条路取决于条件的真假。

3、while循环

当满足条件时进入循环，进入循环后，当条件不满足时，跳出循环。

4、for循环

for循环不判断执行条件，判断次数，会循环特定次数，不判断条件。for的特点是，每次结束，i会+1。

5、函数

当一个代码很常用的时候，我们会把它包装成一个函数(也叫方法或者子程序)，其他地方想用这个代码，只需要写函数名即可。

0、概念梳理

伪代码：用自然语言(中文、英语等)对程序的高层次描述，称为"伪代码"。
助记符：是便于人们记忆、并能描述指令功能和指令操作数的符号，助记符是表明指令功能的英语单词或其缩写。

1、早期二进制写代码

先前都是硬件层面的编程，硬件编程非常麻烦，所以程序员想要一种更通用的编程方法，就是软件。
早期，人们先在纸上写伪代码，用"操作码表"把伪代码转成二进制机器码，翻译完成后，程序可以喂入计算机并运行。

2、汇编器&助记符

背景：1940~1950s，程序员开发出一种新语言，更可读、更高层次(汇编码)。每个操作码分配一个简单名字，叫"助记符"。但计算机不能读懂"助记符"，因此人们写了二进制程序"汇编器"来帮忙。
作用：汇编器读取用"汇编语言"写的程序，然后转成"机器码"。

3、最早高级编程语言"A-0"

汇编只是修饰了一下机器码，一般来说，一条汇编指令对应一条机器指令，所以汇编码和底层硬件的连接很紧密，汇编器仍强迫程序员思考底层逻辑。
1950s，为释放超算潜力，葛丽思·霍普博士，设计了一个高级编程语言，叫"Arithmetic Language Version 0"，一行高级编程语言，可以转成几十条二进制指令。但由于当时人们认为计算机只能做计算，而不能做程序，A-0未被广泛使用。
过程：高级编程语言→编译器→汇编码/机器码

4、开始广泛应用的高级编程语言FORTRAN

1957年由IBM1957年发布，平均来说，FORTRAN写的程序，比等同的手写汇编代码短20倍，FORTRAN编译器会把代码转成机器码。但它只能运行于一种电脑中。

5、通用编程语言——COBOL

1959年，研发可以在不同机器上通用编程语言。
最后研发出来一门高级编程语言："普通面向商业语言"，简称COBOL
每个计算机架构需要一个COBOL编译器，不管是什么电脑都可以运行相同的代码，得到相同结果。

6、现代编程语言：1950s-2000

1960s起，编程语言设计进入黄金时代。
1960：LGOL，LISP和BASIC等语言
70年代有Pascal，C和Smalltalk
80年代有：C++，Object-C和Perl
90年

1、早期，程序如何进入计算机

程序必须人为地输入计算机。早期，电脑无内存概念，人们通过打孔纸片等物理手段，输入数据(数字)，进入计算机。

2、早期计算机的编程

• 打孔纸卡/纸带：在纸卡上打孔，用读卡器读取连同电路，进行编程。原因，穿孔纸卡便宜，可靠也易懂。62500张纸卡=5MB数据
• 插线板：通过插拔线路的方式，改变器件之间的连接方式，进行编程。
• 面板开关(1980s前)：通过拨动面板上的开关，进行编程。输入二进制操作码，按存储按钮，推进至下一个内存位，直至操作完内存，按执行键执行操作。(内存式电脑)

3、现代计算机基础结构——冯诺依曼计算机

冯诺依曼计算机的标志是，一个处理器(有算术逻辑单元)+数据寄存器+指令寄存器+指令地址寄存器+内存

0、概念梳理

• 缓存：在CPU中的小块RAM，用于存储批量指令。
  
  • 缓存命中：想要的数据已经在缓存里
  • 缓存未命中：想要的数据不在缓存里
  • 赃位：缓存里每块空间，有个特殊标记，叫赃位，用于检测缓存内的数据是否与RAM一致。
• 多核处理器：一个CPU芯片中，有多个独立处理单元。

1、现代CPU如何提升性能：

早期通过加快晶体管速度，来提升CPU速度。但很快该方法到达了极限。
后来给CPU设计了专门除法电路+其他电路来做复杂操作：如游戏、视频解码。

2、缓存

为了不让CPU空等数据，在CPU内部设置了一小块内存，称为缓存，让RAM可以一次传输一批数据到CPU中。(不加缓存，CPU没位置放大量数据)
缓存也可以当临时空间，存一些中间值，适合长/复杂的运算。
赃位：储存在缓存中与RAM不一致的数据。
空等原因：从RAM到CPU的数据传输有延迟(要通过总线，RAM还要时间找地址、取数据、配置、输出数据)。

3、缓存同步：

缓存同步一般发生在CPU缓存已满，但CPU仍需往缓存中输入数据。此时，被标记的赃位数据会优先传输回RAM，腾出位置以免被覆盖，导致计算结果有误。

4、指令流水线：

作用：让取址→解码→执行三个步骤同时进行。并行执行指令，提升CPU性能。
原本需要3个时钟周期执行1个指令，现在只需要1个时钟周期。
设计难点：数据具有依赖性 跳转程序

数据依赖性解决方法：
乱序运行、预测分支(高端CPU)

5、一次性处理多条指令

6、同时运行多个指令流(多核CPU)

多核处理器：一个CPU芯片中，有多个独立处理单元。但因为它们整合紧密，可以共享一些资源。

7、超级计算机(多个CPU)

在一台计算机中，用无数个CPU，做怪兽级的复杂运算，如模拟宇宙形成。

1、概念梳理

• 指令：指示计算机要做什么的代码(机器码)，多条指令共同组成程序。如数学指令，内存指令。
  
  • 注：指令和数据都是存在同一个内存里的。
• 指令集：记录指令名称、用法、操作码以及所需RAM地址位数的表格。
  
  程序

2、指令的执行

• 原则：
  
  • RAM每一个地址中，都存放0或1个数据。
  • 特定的数字组合，就表示一个指令，否则表示一个值。
• LOAD指令：
  
  • 计算机会按地址的顺序，读取RAM中所记录的指令/数据。
  • 计算机接收到指令后，如LOAD_A，则通过数据线将数据传至寄存器A。
    
• ADD指令：
  
  • ADD B A指令告诉ALU，把寄存器B和寄存器中的数字加起来，存到寄存器A中。
• JUMP指令：
  
  • 遇到JUMP指令，程序会跳转至对应的RAM地址读取数据。
  • JUMP指令可以有条件跳转(如JUMP-negative)，也可以无条件跳转。

3、计算机指令长度

由于长期计算机每个字只有8位，指令只占4位，意味着只能有16个指令，这远远不够。

现代计算机有两种方式解决指令不够长的问题：

最直接的是用更多位来表示指令，如32位或64位。
采用“可变指令长度”，令不同的指令的长度不同，尽量节约位数。

假设1个字为16位，如果某指令不需要操作内存，则可以省去寻址的位数。
该情况下，部分指令后面需要跟数据，如JUMP，称为立即值。