Crash Course Computer Science(21-30)

P21 压缩

前面提到,位图文件存储的是RGB数据,有时候一张图片很大,而我们想更快地把它发给朋友,这时候就需要用到 压缩(compression),一种简单的压缩方法是游程编码,例如连续7个像素点都是黄色,与其用7个一样的RGB数据,不如在前面加个7代表7个,再接1个RGB数据即可。这种压缩方法适合经常出现相同值的文件,并且可以轻易地复原,叫做 无损压缩。1950年代,麻省理工学院学生哈夫曼发明了一种高效编码方式,叫做 哈夫曼树(Huffman Tree),将出现频率高的块用短编码,频率低的用长编码,用树结构和字典来映射。

可以看到,上面两种方法的思路分别是消除冗余和用更紧凑的表示方法。几乎所有的无损压缩都用了这两种方法,如 gif、png、pdf、zip

然而,并不是所有的数据都需要无损。像音频文件,有些超声波部分完全可以抛弃,因为人类听不到,图像和视频也是,有时候我们并不追求超清画质,只要能看到图片是什么就够了。这时候太过细致的细节会被模糊化处理,这就是 有损压缩 。著名的例子是 mp3 和 jpeg 。

P22 命令行界面

早期计算机都是通过纸带和插线板一次性获取输入数据,计算完成后一次性输出到纸带。到了1950年代开始,小型机开始出现,大型机也慢慢有了多任务和分时系统的概念,于是 交互式 产生了。当时人们就借助了键盘来输入数据,通过电传,计算机能很快接收到键盘的输入然后显示,再根据输入的内容做出文字反馈,这种人类与计算机交流的方式叫做 命令行,用于交互的键盘和屏幕叫做 终端

虽然命令行只能显示文字,十分原始,但由于其性能高,即便是在今天,也有很多程序员喜欢用命令行,尤其是访问远程计算机时。

P23 屏幕&2D 图形显示

屏幕显示技术最早最有影响力的是 阴极射线管(CRT),原理是把带电粒子发射到涂层上,通过磁场来控制方向。在屏幕上显示清晰的点叫做 像素(pixel),液晶显示器就是通过改变每个像素的颜色来显示图像的。

前面提到 ASCII 码通过把二进制数字映射成英文符号显示在屏幕上,映射的过程是由 字符生成器 来完成的,基本上算是第一代显卡。为了让屏幕可以显示任意画面,而不仅仅是字符,同时为了节省内存,人们用矢量画图的方式来绘制图形,屏幕上所有的一切都是由线组成。

1960年代,出现了真正内存中的一个位对应一个像素的图形界面,叫 位图显示。图形就是一个巨大的像素值矩阵,计算机把像素数据存在特殊的区域,叫做 帧缓冲区,一开始缓冲区在内存里,后来存在 高速视频缓冲(VRAM) 里,VRAM在显卡里面,而不是内存,这样访问更快。程序员预先写好了一些例如画直线、画圆、文字等函数,然后再在此基础上调用,从而绘制出丰富的图形界面。

P24 冷战和消费主义

1940年代,美国和苏联开始冷战,科技成了不可小觑的力量,而计算机是科技的中流砥柱,但由于其高成本,只有政府才负担得起。当时两个美苏都在争第一,所以在计算机研发上投入了大量的资金和人力,这促进了计算机科学的发展。之后,由于苏联宇航员抢先登上太空,不甘落后的美国发起了“阿波罗登月计划”,阿波罗的导航是首次使用集成电路的典例,且这个计划投入了40万人力,计算机技术借此得以飞跃发展。1950年代美国成立了国家科学基金会,该机构至今都在给美国科学研究提供政府资金,美国的科技之所以领先,主要原因之一就是这个机构。

1950年代,消费者开始购买晶体管设备。此时战后的日本开始寻找新的工业机会,日本公司很快取得了晶体管的授权,开始振兴日本的半导体和电子行业,其中就包括收音机,日本设备以低利润为特点开始大量售出,而美国企业一开始就是跟政府签订高利润的合同,忽略了消费者市场,因此在消费者领域人们更愿意购买便宜好用的日本产品。

到了1970年代,冷战和太空竞赛褪去,美国企业失去了高利润的政府合同,变得更难竞争了,这导致了美国公司规模的缩小、裁员,甚至倒闭,其中就包括英特尔1974年大裁员,1979年仙童半导体濒临倒闭而被收购。美国公司的无力最终导致了日本公司如夏普、卡西欧等的崛起,以至于1970年代随处可见日本的电子产品。

在消费的刺激下,集成电路的成本越来越低,出现了各种各样的产品,电视、街机、手持计算器,最终催生了家用个人计算机。

P25 个人计算机革命

计算机成本的下降和性能的提升,让个人计算机成为可能。第一台取得成功的商业个人计算机是 MITS 公司的 Altair 8800 ,需要自己组装,而且编写的是机器码。彼时19岁的比尔盖茨和22岁的艾伦保罗向 MITS 公司提议在 8800 上运行 BASIC 程序,并答应为其编写 BASIC 的 **解释器(Interpreter)**,解释器是一种将 BASIC 语言转换成机器码的程序,解释器跟编译器的区别是,前者是在程序运行时转换,而后者是在运行前。后来他们真的做出来了,于是 Altair BASIC 成了微软公司的第一款产品。

Altair 8800的问世聚集了很多计算机爱好者的聚会,一次聚会上24岁的斯蒂夫·沃兹尼亚克突发奇想说要设计自己的计算机,它的设想是把计算机连接到电视显示并提供文本界面,沃兹的大学朋友斯蒂夫·乔布斯建议说不如直接出售组装好的主板,于是,Apple-I 问世了。

个人计算机的发展引起了行业大佬IBM的注意,IBM让十二名精干的工程师从零设计了 IBM PC,立马获得了成功。它提供了开放式架构,叫做 IBM Compatible (IBM兼容),使得第三方可以提供硬件或外设,包括显卡、声卡、硬盘等。很快,康柏和戴尔也开始卖PC了,而且采用的就是 IBM 兼容的架构,微软也很乐意给他们提供 MS-DOS 操作系统,IBM硬件+微软软件 的生态很快建立起来。

然而,苹果还是坚持采用封闭式架构,自己做机器,自己做系统,甚至卖得还不错。为了在IBM+微软的夹攻中体现竞争力,1984年,Macintosh 问世了,这是第一款采用了图形界面的个人计算机!

P26 图形用户界面

尽管第一台消费者可以购买到的图形界面个人计算机 Macintosh 是 1984 年才发布的,但图形界面的研究1960年代就开始了。恩格尔巴特算是对图形界面贡献比较大的人,尽管他的尝试在商业上失败了,但还是获得1997年的图灵奖。他在施乐公司工作,他们的研发团队将2D屏幕当作桌面,就像今天我们在用的一样,每一个程序都有一个窗口,窗口和窗口之间可以堆叠。然后用鼠标操作指针移动,用键盘输入内容。程序窗口有许多可复用的元素,文本框、按钮、滑动条、标签页等,GUI程序就是由这些小组件构成,而且是 事件响应驱动 的,并非顺序执行。

1979年,乔布斯参访了施乐公司,看到了他们如此酷的设计,决定跟施乐合作,后来他说,就像拨开了眼前的一层迷纱,我可以看到计算机产业的未来。之后,乔布斯回到苹果,开始图形界面的开发,并在1984年的 Macintosh 上大获成功。但没过多久,其他个人计算机的图形界面也赶了上来,加上当时苹果公司内部的混乱,乔布斯被赶出了苹果公司,给微软有机可乘,微软随即发布了 Windows 1.0,并在10年的时间里吃掉了95%的个人计算机的操作系统份额,其中就包括微软的第一个图形操作系统 Windows 95。

P27 3D图形

投影和多边形

将 3D 的物体通过投射的方式,显示在 2D 的屏幕上,就是 3D 投影。如果正方体各个边在投影中也互相平行,叫做 正交投影,如果会在远处收敛于一点,则叫做 透视投影。在复杂的场景中,通常用三角形来绘制图案,三角形在图形学中称为 多边形,一堆多边形的集合叫做 网格。网格数量和精细度呈正比。

渲染

线框绘制好后需要填充,经典的填充算法是 扫描性渲染,它会找到三角形最大和最小的Y值,然后从上往下逐行填充颜色,如果像素不高,就会产生很多锯齿。一种解决办法是 抗锯齿,原理很简单,即边缘部分用较浅的颜色来渲染。

在 3D 场景中,经常有画面堆叠的情况。这叫 遮挡。常用 画家算法 来计算遮挡。先画远的,再画近的。再用扫描性渲染来填充。但是这种算法需要先对多边形的远近进行排序。

还有一种算法叫 深度缓冲(Z-buffering),是通过数值来记录多边形的远近,如果更远的部分被更近的遮挡,就不渲染。这种算法因为不用排序,所以会更快。但是这种算法有个有趣的现象,如果两个多边形距离一样,谁画在上面?而且浮点数计算往往不够准确,导致结果不可预测,因此在一些 3D 游戏中,经常出现 Z-Fighting 现象,同一个地方画面颜色变来变去。此外,在一些 3D 游戏中,往往会忽略多边形背面的渲染,来加快渲染速度,但坏处是如果遇到bug进入了多边形内部,会看到消失的画面。

在 3D 场景中,同样也需要明暗处理,最简单的是用 平面着色 照明算法,后来又开发了其他优化算法。此外,3D 中还需要 纹理化 让网格得到特殊外观。此处就不展开讲了。

GPU

总而言之,在 3D 渲染中需要用到大量的计算,CPU不是专门为此设计的,因此工程师们做了专门的处理器—— GPU ,图形处理单元,放在显卡上面,能够进行大规模并行计算,现代GPU每秒能处理上亿个多边形!

P28 计算机网络

局域网

计算机网络的诞生是为了方便信息交换和共享物理资源。计算机近距离构成的小型网络称为 局域网(LAN),最广泛使用的局域网技术是 以太网,用一条电缆连接多台电脑,用电信号传输,由于以太网不会区分信号是要传给谁的,大家都能接收到相同的信号,所以需要每台计算机都有一个物理地址(mac),只监控传给自己的电信号。像共享电缆这样,多台电脑共享一个传输媒介,称为 载波侦听多路访问(CSMA),以太网的载体是铜线,Wi-Fi的载体是空气。载体传输数据的速度叫做 带宽(bandwidth)。共享载体带来的一个弊端是容易冲突,大家都有数据要发,产生信号混乱,解决办法是 指数退避,当有冲突时按指数时间递增延迟发送。即便如此,在较大的局域网中还是很容易产生冲突,于是人们使用 交换机 来减少冲突域。

路由和IP协议

在大型局域网中,计算机之间的通路可能有多条,这就产生了 路由(routing)。两台相隔较远的计算机通信,最开始是使用专用电路线路,叫做 电路交换,缺点是价格昂贵且不灵活。另一种方法是 报文交换,途中会经过好几个站点,就像邮局送信一样,好处是可以使用不同的路由,提升容错且更可靠,坏处是如果报文过大会阻塞路由。于是人们把将大的报文分成多个小块,叫做 数据包(packets),这种方法称为 分组交换。报文和分组的格式由互联网协议(Internet Protocol,IP)定义,每台联网的计算机都需要一个 IP 地址。路由器 会平衡与其他路由器的负载,叫做 拥塞控制。同一个报文的不同数据包,可能会经过不同的路由线路,最后到达目的地后再按顺序拼接起来,顺序问题由 TCP/IP 协议来解决。分组交换的好处是它是去中心化的,没有中心权威机构,也没有单点失败问题。

如今,不仅仅是PC、手机接入计算机网络世界,形成互联网,一些智能家电也有了网络功能,构成了 物联网

P29 互联网

UDP

互联网是一个巨型分布式网络,大数据会被拆分成一个一个数据包传输。数据包的格式遵循IP协议,即在数据包的头部加上元数据注明要发给谁,但如果只有IP协议,对方不知道这是哪个应用程序需要的数据,于是人们在IP协议之上开发了更高级的协议。例如 用户数据报协议(UDP) 在数据前加UDP头,指明了端口号,端口号是应用程序访问网络时,需要向操作系统申请的识别号。总而言之,IP协议负责把数据包发给正确的计算机,UDP协议负责发给正确的应用。

TCP

UDP头里还有 checksum 检验和,用来检查数据是否正确,如果不正确,UDP通常会把数据包丢弃,加之UDP并不能确认对方已经收到数据包,所以它其实并不太可靠。但是由于其简单性,一些应用并不在乎丢失数据,例如视频通话最多也就是丢帧,影响不大,所以UDP的使用还是非常广泛的。不过到了邮件发送,文件传输等场景,要求所有数据必须准确无误地送达,就不得不使用 传输控制协议(TCP) 了,其原理跟UDP一样,但提供了更高级的功能,如数据包排序、确认码(ACK)、超时重传、滑窗、拥塞控制,从而保证数据完整无误地传输。

DNS

应用程序想从网络上的另一台计算机上的应用程序获取数据,需要知道对方的IP地址和端口号,事实上,因为 172.217.7.238 是谷歌服务的ip地址,而80是其端口号,我们在浏览器上输入 http://172.217.7.238:80 即可直接访问谷歌。但记下一串数字总归是很烦的,我们还是喜欢输入 www.google.com 的方式,这叫做域名。互联网上有一种专门的服务,负责把域名和ip地址对应起来,这种服务就是 域名系统(Domain Name System,DNS)

OSI七层模型

线路里的电信号或者Wi-Fi里的无线信号,这些是物理层。mac地址,碰撞检测,指数退避等用来操控物理层的方法叫做数据链路层,IP协议等负责各种报文交换和路由转发的叫做网络层,TCP和UDP负责如何点到点传输的叫做传输层,操纵TCP、UDP进行连接、传递信息、关闭连接的叫做会话层,例如socket,最后像浏览器、Skype、微信等具体的应用程序如何展现数据,就是展示层和应用层了。

P30 万维网(world wide web)

万维网建立在互联网之上,通常我们用浏览器访问一个页面,会输入如 www.bilibili.com/video/av21376839 这样的链接,前缀www就是万维网的缩写。其最基本的单位是单个页面,页面上会有跳转到其他页面的链接,叫做 超链接,每个页面都需要一个唯一的地址,叫做 统一资源定位符(URL)。当我们输入一个 URL,DNS首先会找到域名 www.bilibili.com 对应的ip地址,然后我们的计算机会向对方(通常是web服务器,默认80端口)发起一个 tcp 连接,连接建立后,会继续向服务器请求对应的页面 /video/av21376839,这里面用到的协议是 超文本传输协议(HTTP)。服务器返回的内容为了更好地展示,如标题、内容、列表,通常会用 超文本标记语言(HTML) 来显示,如今最新的 HTML5 标准,加上 CSS、JavaScript 可以做出丰富多彩的网页效果。

如果我们知道一个域名,可以直接输入,但如果我们事先不知道呢?最开始网页服务还比较少的时候,人们可以维护一个黄页目录,有专门提供这种服务的网站,例如 Yahoo,后来随着万维网的网站越来越多,人工维护变得困难起来,于是又出现了搜索引擎,如Google。