PyFrom0 - 0.简介和前置课程

从零开始的Python

这篇文章包括关于Python的基本信息，以及为了不同深度地理解Python所需要的前置知识，其中有一些会比Python本身难得多。具体学习哪些内容可以视自己的需求取舍。

1. Python 简介

1.1 什么是Python

Python是一种计算机语言，创始人是荷兰的 Guido van Rossum。但是计算机语言的创始人不是很重要，Python成为最流行的编程语言（之一）的主要原因是它的简洁易读性、相对比较快的速度和非常丰富的代码库，这些主要是开源社区贡献的。

Python官网
Anaconda
Github

1.2 Python是一门解释性语言

计算机语言可以有几种分类方法，最粗的一种分法是以人能看得懂/机器能看得懂作为标准，人能看得懂的叫高级语言，机器才能看懂的叫低级语言。我们学的所有语言，包括C, C++, Java, Perl, Matlab, R, Python，几乎都是高级语言，但是机器是看不懂这些东西的。

cpu执行指令是通过很多电容器的充电/放电实现的(计算机组成原理)，本质上是一堆0和1的运算。这意味着无论人们在键盘上敲出什么语言，最后都要变成0/1字符串提交给cpu。这个0/1字符串叫做“机器语言”，在它之上人们还稍微进行了一点点封装，把最基本的加法/赋值/声明变量等操作符号化了，叫做“汇编语言”。汇编语言是和机器语言一一对应的，所以二者可以认为是同一种语言的不同写法。

把高级语言转换成低级语言的过程叫做“翻译”，翻译分为两种：编译和解释。一般来说一门语言只能用其中一种翻译方法，所以用编译来翻译的就叫编译性语言，用解释来翻译的就叫解释性语言。

编译和解释的区别，就类似全文翻译和同声传译的区别。编译器是先拿到整个程序的所有代码，把它整体地转换成二进制文件，再把二进制文件提交给cpu运行。而解释器是不需要看到所有代码，看到一句就翻译一句，看到一段就翻译一段，翻译出来的机器语言直接提交给cpu运行，也不会保存二进制文件。

这个区别导致它们各自有一些优点：

编译的优点：

• 一个程序只需要编译一次，之后直接运行二进制文件就行，运行效率高
• 二进制文件可以直接交付给他人使用，源码保密性好，安全性高
• 编译时能看到全文，所以
  
  • 能知道一些变量后续不会再使用，及时释放内存
  • 能优化省掉多余的运算步骤，提高效率
  • 定义函数可以在调用函数之后，代码主体逻辑更清晰

解释的优点：

• 交互式编程，能随时查看中间结果，及时发现错误或修改后续代码，开发效率高
• 要运行程序必须使用源码，天然有开源属性，因此也拥有更多的代码库
• 一般来说可读性要更好
• 跨平台兼容性好一些

编译性语言和解释性语言的运行效率相差非常大，在一些多层循环的任务里（比如矩阵计算），效率差一万倍都不夸张。不过现实中的任务大部分对效率的要求其实也不高，所以现在的互联网开发和科学计算是以解释性为主流，碰到大运算量任务时嵌入一个C++的子程序，算好了直接把结果返回出来。解释性语言学习和开发难度低，毕竟人力很多时候还是比算力值钱的。

1.3 下载Python解释器和开发环境

Python解释器是把Python代码翻译成机器语言的软件，下载Python解释器可以通过Python官网，可以下载到最新的Python版本，也可以下载之前的版本（有些旧版本代码和新解释器是不兼容的，尤其Python2.x和Python3.x是基本完全不兼容的）。Windows系统下，Python.exe下载回来安装成功后，打开命令提示符输入“python”就能看到当前python版本了。【但是不建议这样下载Python，往后看完这小节再决定】

开发环境(IDE, Integrated Development Environment)是编写、调试和运行Python代码的软件。其实代码都是文本，用记事本或者文本文档就能编辑，但是好的IDE可以实现代码高亮、自动缩进、多平台自动同步、代码自动补全/自动纠错、实时运行代码并观察变量情况等一大堆很有用的功能。常用的IDE有这些：

• Sublime
• Visual Studio Code
• Notepad++

应该说工业上用得最多的IDE是Visual Studio Code，这个平台支持几乎所有的编程语言，也像chrome一样有很多插件。不过对Python初学者来说更方便的是接下来介绍的Anaconda。

Anaconda是一个包含【Python解释器 + 最常用的依赖包(package) + 最全面的package库 + 最方便的package管理系统 + 可能是最好用的Python IDE】的大杂烩。Anaconda本身也是水蟒的意思，它的出生就是为了给Python提供更好的开发环境（但是它也支持R，就很魔幻）。这个东西比较大，但是几乎包含了所有学习Python需要用到的东西，推荐下载。下载链接

1.4 怎么学Python

学习任何一门计算机语言，基本逻辑都是【了解基本语法->了解基本数据类型->熟悉常用依赖库->(理解底层数据结构、编译原理->)结合语言、数据结构和算法知识实现功能->在无尽的debug中逐渐精通】。

学习Python和学习其他计算机语言没有什么本质的差别，不过还是有一点小区别，主要有以下几个：

• Python的语法和自然语言很像，而且灵活多变，不需要花大力气记住
• Python的自动数据类型转换非常方便，变量的格式兼容性很高，不需要花太多功夫去做内存管理、考虑数据结构之类的东西，但是好的程序员要懂这些
• 学习Python最重要的能力应该是搜索代码库，阅读、使用和修改其他人的源码，然后实现自己的需求，不要重复发明轮子
• 只要不涉及并行计算，Python的debug通常非常人性化，体现在报错定位明确、类型多样而且支持自定义报错内容、程序中断后已经算好的中间结果能够保留。所以不需要像其它语言一样学习一大堆debug的奇技淫巧

这些小差别使得Python这门语言非常容易上手，尤其易读性能让没接触过编程的新手也能基本看懂大部分别人写的代码，对自学是很友好的。但是当然也会带来很多缺点，比如运行速度慢，比如不理解底层数据结构的话看一些bug就会怀疑人生，比如有时候程序莫名其妙能运行但是结果是错的。这些问题都可以通过深入理解这门语言来解决。

2. 前置课程

这一章介绍一些和Python相关，但是不属于Python教学大纲的基础知识。这里每一节都至少是一门课，也不需要学太深，稍微看看了解一下就行，不仅对学Python，对所有计算机语言都很有帮助

2.1 计算机组成原理

计算机包括外接设备和内部设备，外接就不说了，鼠标键盘音响显示器那些东西，主要负责输入和输出信号。这章主要介绍一下主机里的东西和它们的运行逻辑。

2.1.1 计算机的基本组成

一台计算机由运算器、储存器、控制器组成，加上输入输出设备构成冯诺依曼体系，也是如今所有计算机的基本体系。

2.1.2 运算器

运算器是用来执行计算任务的，运算任务主要有两类：有先后依赖关系的顺序计算任务和没有依赖关系的并行计算任务。

• 处理器（cpu, Central Processing Unit）
  
  • cpu其实是运算、储存、控制都有，毕竟叫中央处理器，是整个计算机的核心部件。拆开机箱主板上有一个正方形的小方块，就是cpu。
  • cpu适合处理顺序计算任务，现在的cpu一般有4-6个核，也就是能同时计算4-6个任务，但每个核的能力强，数据传输和交换速度也快。
• 显卡（gpu，Graphics Processing Unit）
  
  • gpu也包含了运算和储存两个功能，gpu通常包含几千个核，适合并行计算任务，但高频率的数据、指令交换就不太行。
  • gpu通常是把数据大量读到显存里，计算出结果再返回给cpu进行操作。它叫显卡是因为显示器上每个像素点发光强度、颜色的计算就是典型的相互不依赖的并行任务。
  • gpu一开始是为了实时渲染游戏、视频画面设计的。但是人们后来又发现神经网络、区块链挖矿的运算也是这种高并行任务，所以在码农手里gpu主要是干这两件事。
  • gpu是插在主板上最大的那一坨长方体，通常带有两个大风扇，如果是高级的gpu还需要自己的独立电源（电脑上大部分器件都是由主板供电，主板由电源供电）。独立的gpu不是计算机必须的，主板上一般也会自带一个比较弱的gpu。

2.1.3 储存器

储存器是用来储存数据和运算结果的，由于硬件的读取速度和储存容量之间存在矛盾，计算机中采用了分层储存的结构，即靠近运算端的采用读取快、容量小的模式，靠近储存端的采用读取慢、容量大的模式，现在的计算机一般分三层。注意储存器也是通过电容的充电/放电，或是磁极的南/北来储存数据的，所以所有数据在储存器里也都是以排成一列的0/1字符串的格式存在

• 寄存器（Cache）
  直接集成在cpu里的储存器，容量只有几十KB，一般用来存指令。断电不保存
• 内存（Memory, RAM）
  插在主板上的长条型长方体，一般容量在几到几十GB量级，RAM的意思是它可以随时读写里边的任意位置，所以读取速度快。断电不保存
• 硬盘（Hard Disk, ROM）
  ROM的意思是只读储存器，但是其实也是可以写的，只是这里的写是永久写入，除非再次写入新东西将其覆盖否则不会丢失，因此有断电保护的功能。常用的硬盘叫磁盘，不直接插在主板上，而是架在单独的硬盘架上，通过一条数据线连到主板的边缘。现在比较好的硬盘叫固态硬盘（SSD），不仅读取速度快，而且非常小巧，就半张银行卡那么大，直接插在主板上（这个位置比较难描述，之后看到了再说吧）。

2.1.4 不重要的东西

• 控制器：集成在cpu里的一部分，给计算机的各个部件提供指令，太基础了所以不是很重要。（我也不会啊！）
• 其它东西
  
  • 主板：一块大板子，用来安装和连接所有的部件
  • 散热：cpu有一个独立散热装置，机箱上也有整机的散热风扇
  • 电源：给所有部件供电的
  • 鼠标、键盘、光驱、显示器、USB接口：输入输出设备

好了，现在你已经学会了计算机的组成框架，赶快回家自己造一个吧！

2.2 数据结构

数据在储存器里都是线性（排成一列）存储的，那我们想表示非线性的东西（比如图像、矩阵、网络）怎么办呢？即使是线性的东西，我们如果想将其无限延伸怎么办呢。如果我们想迅速定位到一个复杂数据里的某个位置，怎么做最快？如果我们想在一组数据里搜索某个特定的值，怎么做最快？

数据结构解决的就是这一类问题，即如何储存各类数据，能用更少的储存空间达到更快、更准确、更方便地调用数据的目的。

【要理解任何程序的运行原理，数据结构是重点中的重点】

2.2.0 基本数据类型

数据类型是指一类结构相同的数据，由于同一数据类型在内存里的储存方式相同，设计语言的人可以对它们设计统一的操作。在多数语言中，数据类型大概有这么几类：

• 整数（int）：最基本的数据类型，直接以数字的二进制表示储存在内存里
  
  • 长整数（long int）：在一些语言中，int类型能储存的数字大小有上限，一般是 $2^{32}-1$，也没多大就20亿左右，这是因为一个int变量默认分配32个0/1空间（叫比特）来储存。比这更大的就需要特别声明成长整数。long int 的比特位数比 int 多一倍，即可以表示 $2^{64}-1$ 以下的所有整数
  • python里的整数可以无限大，不存在long int这么一说
• 浮点数（float）：可以理解成有小数点的数，是用科学计数法存在内存里的，有一个符号位、若干个底数位和若干个指数位
  
  • 浮点数的精度：有多少底数位比特决定了浮点数的精确度，一般是十几位有效数字
  • 浮点数有内在误差，比如无限小数它是表示不了的，甚至最简单的 $1/3$ 都会出问题（当然是一般情况下没啥事的小问题）
• 字符（char）：包括字母、符号、汉字等，有一套编码体系，是编码成16进制数字储存的
  
  • python 2.x用的是ascii码编码体系，python 3.x用的是UTF-8体系
  • 不用记这个玩意，但是注意ascii码不包含中文，所以python 2.x不天然支持中文（可以加个插件解决）
• 字符串（string）：字符连在一起构成的串
• 布尔值（boolean）：真/假，True/False
• 空值：表示某个东西不存在，注意不是0，是不存在。None/NULL/NA，python里是None
• 指针（pointer）：这个有点复杂，它本身储存的是内存里的一个地址，那个地址里存了什么东西是另外的事情，对指针的操作可以直接作用于这个地址（前一一位或后移一位），也可以作用于地址上存的变量

底层的数据类型一般就这些，其它数据类型基本都是这些类型的结合/变换/应用。

2.2.1 数组和多维数组

有了数字类型可以表示一个数值，但是很多时候我们想表示很多数值，比如一个班的同学的身高，可能有几十个数值，难道要生成几十个变量来一一表示吗？为了克服这个麻烦，可以使用数组

• 数组（Array）：一些数字变量在内存空间里排成一列构成的数据结构
  
  • 以 int 为例，一个数占4个字节（8个比特 bit 叫一个字节 byte，平时我们说的KB, MB, TB就是Kilobyte, Megabyte, Terabyte），如果有一个向量包含100个数，那当然就占400个字节
  • 计算机从内存里找出一块400字节的空间，给程序返回这块空间的起始位置地址 $n$，那么地址 $n+4*(i-1)$ 到地址 $n+4*i-1$ 这段储存的就是第i个数
  • 数组可以迅速定位到某个指定的位置，这个定位时间不随数组的增大而增大。也叫“索引动作是常数时间复杂度，$O(1)$ 的时间复杂度”，具体见算法和复杂度估计
    
• 多维数组（tensor）：一堆数组排成一列构成二维数组，一堆二维数组排成一列构成三维数组……
  
  • 应该很好理解了，对于二维数组 $Array2$，比如是由5个长度为100的一维数组组成的，我现在想要第2个向量的第25位（也叫第2行第25列，$Array2[2,25]$）。假设$Array2$的起始地址是 $n$，先找到第2行的起始位置 $m=n+400*(2-1)$，然后从 $m$ 出发找到第25个数字，即 $m+4*(25-1)$，就是 $Array2[2,25]$ 的地址了
  • 多维数组也可以在常数时间内定位到某个指定的位置
    

数组的优点是：

• 占用内存小，几乎只占用储存数字必须的内存
• 取出其中某个/某段位置的值非常方便

数组的缺点是：

• 分配内存的时候必须知道具体有多少个数字，而且无法扩展
  
  • 这个缺点通过链表来克服
• 如果想找到符合某些条件的值，比如班里身高大于一米七/等于168cm的同学，要对每个数值逐个检验，如果数组很大就要花费很长时间（也叫“查找动作是 $O(n)$ 的时间复杂度”）
  
  • 要想迅速定位精确等于某个值的位置，用哈希表
  • 要想迅速定位与值的大小有关的位置，用搜索树

2.2.2 链表和动态数组

数组可以解决一些数据联合起来存储的问题，但是需要数据的个数已知，或至少知道一个上限。很多时候数据的个数很难提前知道，比如餐厅想记录今天每笔订单的金额，如果每天都按可能的最高订单数来记录，就很浪费空间，而且有数据溢出的风险。

那么有没有一种使用时可以不断延长的数字列表呢，当~然有啦！它叫做链表

• 链表（linked list）
  
  • 链表顾名思义是由一堆“链”组成的列表，这里的一个链，其实是一个数字和一个指针拼起来的复合结构
  • 数字储存当前链上的值（当然也可以不是数字，是其它任何数据类型都可以），指针储存下一个链的地址
  • 程序拿到一条链表最开始的头部指针，找到第1个链的指针、跳到第2个链，再通过第2个链的指针跳到第3个链，重复 i 次就能到达链表里的第 i 个位置
  • 要延长链表时，向内存申请一个新的链，得到新链的地址，把链表上最后一个指针指向的位置设成这个新地址，整个列表就延长了一位

当然一个链上也不一定只有一个指针，比如可以有两个指针，一个指向下一个链，一个指向上一个链，这样就变成了双向链表。或者也可以有其它的玩法

• 动态数组
  
  • 链表的一个坏处是，每储存一个值就要浪费一个指针的内存空间。如果链表上的值不是数字，而是长度为 n 的数组，那么每储存 n 个值才会浪费一个指针
  • 这样索引也会方便一点，只需要通过指针跳转少数几次
  • python里的列表(list)结构就是动态数组，而且更加智能，有自动内存管理功能、支持每个元素都是不同的数据类型等等

链表的优点是：

• 可以无限延长，灵活多变
• 在表中间插值比较方便
  
  • 可以思考一下链表如何插值，数组如何插值
• 由于上一条的缘故，链表拿来实现栈、队列和排序（这是几种算法）都比较方便

链表的缺点是：

• 索引复杂度和查找复杂度都是 $O(n)$
• 前面说过，浪费空间
• 单链表的操作相当不友好，指针只能单向移动，移到下一个链上一个就丢失了，要回到上一个链只能再从头开始跳转

2.2.3 哈希表

数组和链表的查找复杂度都是 $O(n)$，这意味着当数据量很大，要从中找到某个值是非常费劲的。哈希表利用哈希函数，把一个数据的储存位置和它的值联系起来，这样当我们想查找一个值，就可以直接去某个地址查找，实现 $O(1)$ 的查找复杂度

• 哈希函数（Hash function）
  
  • 哈希函数的定义是：能将任何输入值转换成一个固定范围内的数字的函数。转换出来的这个数字叫哈希值
  • 最容易理解的哈希函数是整除取余数，给任何一个数字，拿去除以另一个数字，比如除以256，得到的余数就一定是0-255区间内的整数。当然一般都会使用更复杂的哈希函数
  • 哈希函数有一个特点，正着算容易，逆着算很难甚至根本不可能，比如给你一个余数和除数，让你解出被除数这几乎不可能。这导致哈希函数很适合用来做加密算法，比特币的核心算法“sha256”就是FBI发明的一个哈希函数（但是这个性质在我们这完全用不到，就是感觉有意思）

• 哈希表 （Hash table）
  
  • 哈希函数为任何值都给出一个哈希值，这个哈希值具有一个范围，于是我们可以向内存申请一块和这个范围等大的空间，把每个值储存在它的哈希值对应的位置
  • 比如我们用整除256取余的哈希函数，向内存申请一块能储存256个整数的空间，那么数据“500”就应该存在这块空间的第 $244(=500\mod 256)$ 个位置上。再来新的数据，再计算新数据的哈希值，把新数据存到它对应的位置上
  • 如果我已经存了很多数据，现在想查找里面有没有499这个值，就可以到这块空间的第243位去看看，如果那个地方没有值，那就说明499在数据中不存在。如果有值，就看看这个值是不是499（数据“755”的哈希值也是243）

申请的空间如果不是256个整数，而是256个指针，哈希表就可以用来储存复杂的数据结构，用来计算哈希值的"key"和要储存的"value"也可以剥离开。比如要储存班里每位同学的身高、体重、年龄、成绩，可以用同学的名字作为key，计算出哈希值后，把指向相应数据的指针储存在哈希值的对应位置。

python里的字典（dict）就是典型的哈希表

【留个思考题】如果出现了两个具有相同哈希值的数据，哈希表该如何处理

哈希表的优点有：

• 索引复杂度和查找复杂度都是 $O(1)$，事实上哈希表的索引就是查找
• 可以直接用各种各样的东西作为索引，比如用字符串做索引，相当于给数据命名了，调用起来就很方便

哈希表的缺点有：

• 非常占空间，如果哈希值重复的数据过多，会影响索引效率，所以一般都要用数据量的两到三倍的空间（但是储存指针就没有这个问题）
• 数据放进哈希表，就没有顺序了

【待续，后面的暂时不在python里出现】

2.2.4 二叉树和搜索树

2.2.4 图和网络

2.3 算法和复杂度估计

数据结构和算法其实是编程的核心能力，会不会用某种语言都是小事（另外一个核心能力是找包调包的能力）。这就真的只能看到一个写一个了

2.4 编译原理

这门课没啥用，就是能理解代码是怎么运行起来的

2.5 正则表达式

介绍字符串的时候再补上