程序设计导论（Python）读书笔记

参考链接： 用于查找文件哈希的Python程序

Python语言实践 

函数和模块 

程序设计基本元素 常见错误： Python2中默认的编码格式是 ASCII 格式，在没修改编码格式时无法正确打印汉字，所以在读取中文时会报错。 解决方法为只要在文件开头加入 # -- coding: UTF-8 -- 或者 #coding=utf-8 就行了 通过在命令行上提供参数来定制程序行为。如最小批次、周期数、学习率。 1.ImportError：No module name nltk常见错误： 解决办法：上Stack Overflow或github查询相关模块安装方法，在虚拟环境一般用pip 2.SyntaxError：invaild syntax 解决办法：程序中包含错误，查看参数设置或修改语法错误 3.版本冲突：keras会出现版本问题，老的代码需要降低keras版本，tensorflow与cudnn需对应 在python中，所有的数据都表示为对象及对象之间的关系，python对象是特定数据类型的值在内存中的表现方式。每个对象由其标志、类型和值三者标识。 数据类型是一系列值及定义在这些值上的一系列操作，python内置数据类型包括bool、str、int和float 布尔表达式可以用于控制程序的行为 使用数值类型、内置函数、python标准模块、扩展模块中的函数可实现python的超级数学计算器功能，如大数据分析。 python典型结构： 1.一系列import语句 2.一系列函数定义 3.任意数量的全局代码，即程序的主体 针对程序流程控制而言，函数的影响力与选择结构和循环结构一样深远。函数允许程序的控制在不同的代码片段之间切换。函数的意义在于可以在程序中清晰地分离不同的任务，而且还为代码复用提供了一个通用的机制。如果程序中包含多个函数，则可将这些函数分组包含在模块中，将计算任务分解为大小合理的子任务。 借助函数，我们可以实现如下功能： 1.把一长系列的语句分解为独立的部分 2.代码重用，而不需复制代码 3.在更高的概念层面上处理任务 模块化程序设计的优越性： 1.可编写合理规模或超大系统的程序 2.调试可限制在少量的代码范围 3.维护以及改进代码会更容易 递归：函数调用本身。证明技术：数学归纳法 

 成为优秀程序员：当需要某个软件工具时，有足够的信心创建所需要的软件工具，而且必须要有足够的智慧懂得何时适合从现有的模块中寻求参考解决方案！！！ 

面向对象的程序设计 

方法：将大型和复杂的程序分解为一系列交互的元素或对象 思想：对现实世界的实体进行建模 

方法与函数的区别：方法与特定的对象关联。我们可以认为这个特定的对象是传递给函数的除了通常方法参数外的一个额外参数。代码中体现为函数调用使用模块名，方法调用使用变量名。 

理念一：使用一个数据类型时无须理解其具体实现 str（字符串）的API中运算操作三类别： 1.内置运算符：+、+=、[]、[:]、in、not in以及比较运算符，其特征是使用特别的符号和语法。 2.内置函数：len()，使用标准函数调用语法 3.方法：upper()、startwith()、find()等，在API中使用变量名跟点运算符区分。 用户自定义数据类型：应用程序编程接口、文件命名规则、创建对象、调用方法、字符串表示 

在概念层面上，一个数据类型是一系列值及定义在这些值上的一系列操作的集合。在具体层面上，我们使用数据类型来创建对象。一个对象具有三个基本属性：标识、类型和值（或状态）。 标识（identity）：一个对象的标识是其在计算机内存中的存储位置，用于唯一标示该对象； 类型（type）：一个对象的类型完全指定对象的行为，即该对象支持的一系列运算操作； 值（value或状态state）：一个对象的值是对象当前表示的数据类型的值。 区分用户自定义数据类型和内置数据类型之间的异同点。 自定义数据类型文件需放置在与客户端代码相同的目录中或使用操作系统的路径环境变量进行设置。 内存管理：在python中，通过调用构造函数创建对象，每次创建一个对象时，python为该对象预留一段内存，何时创建何时销毁对象，使其占用的内存可以释放并重用。 孤立对象：一个程序创建的对象不再被引用。 内存管理：一种机制创建对象并分配内存，当对象成为孤立对象时销毁对象并释放内存，系统无法预测一个程序的运行操作，需监控系统的运行从而采取相应的措施。 内存泄漏：程序员忘记去释放孤立对象所占据的内存空间。 垃圾回收：自动内存管理，解放程序员管理内存的责任，通过跟踪孤立对象，并返回其占用的内存到空闲的内存池。 创建一个数据类型： 1.设计其API。API的目的是把客户端与实现分离开，从而促进模块化程序设计。设计API时有两个目标：客户端代码清晰和正确，必须能够实现这些运算操作。 2.实现一个Python类以满足其API规范。首先编写构造函数以定义和初始化实例变量。其次，编写方法处理实例变量以实现所需要的功能。在python中通常需要实现三种类型的方法： ～.为实现一个构造函数，实现一个特殊方法__init__()，其第一个参数变量为self，随后跟构造函数的普通参数变量。 ～.为实现一个方法，实现一个指定名称的函数，其第一个参数变量为self，随后跟构造函数的普通参数变量。 ～.为实现一个内置函数，实现一个函数名的前后均带双下划线的特殊方法，其第一个参数变量为self。 3.编写一个测试客户端，以验证和测试前两步的设计和实现是否正确。 方法包含的三种类型变量：self对象的实例变量、方法的参数变量、局部变量 

设计数据类型 设计理念：在计算任务中，任何时候只要可以清晰地分离数据和相关操作，则建议分离数据和相关操作。 数据类型的API包含若干方法和这些方法所提供功能的简介描述。 注意：标准、规范问题、宽接口、从客户端代码开始、避免对表示方法的依赖、陷阱{为客户端提供其所需的方法，仅此而已） 将客户端和实现分离开从而隐藏信息的过程称为封装。封装实现模块化设计、提高调试效率、使代码更加清晰简洁。封装允许我们独立开发客户端和实现代码、替换使用改进的实现版本而不会影响客户端、支持尚未编写的客户端，封装可以进行分离数据类型的操作，在实现的代码中增加一致性检查和其他调试工具，使客户端代码更加清晰。 注意：模块化程序设计、修改API（客户端量多不随意改）、改变实现持续改进软件、私有性（客户端没有理由直接访问一个实例变量）、规划未来（封装数据类型）、限制潜在的错误、代码清晰度（精确地指定数据类型） 不可变对象优点：容易使用不会误用、容易调试。代价：必须为每一个值创建一个新的对象。强制不可变：保持一个数据类型不可变，并确保在实现代码中不修改任何对象的值。防御拷贝：实现代码拷贝实例变量。 元组：在元素无需改变的情况下必须使用元组。 多态性：可带不同类型参数的方法或函数。最好与最坏的多态性：非预期类型。 鸭子类型：无需显式声明一个变量的类型。原则：方法/函数无需关心一个对象的类型，只需了解客户端是否可以在一个对象上执行需要的操作。不足：无法准确判断客户端和实现之间的契约，特别是一个需要的方法以间接方式提供的时候。信息缺失倒置运行错误、语义错误。 运算符重载注意：特殊方法、算术运算符、等性运算符（引用相等和对象相等）、哈希法（条件是一个对象可以通过==运算符与其他对象比较相等性、当两个对象比较的结果为相等时，其哈希码相同、一个对象的哈希码在其生存期内保持不变）通过实现两个特殊方法_hash_()和_eq_()可以使一个用户自定义的数据类型可哈希。、比较运算符须定义一种全序关系（属性有反对称性、传递性、完全性）、其他运算符、内置函数。 函数是对象，意味着函数可以作为函数的参数和结果返回值。 继承：定义类之间关系的语言支持。优点;代码重用、可扩展。缺点：与封装违背、脆弱的基类问题、子类代码可以访问实例变量。 应用：数据挖掘 文档关联摘要向量、抽象文档、计算文档摘要、哈希法、比较文档摘要、比较所有的文档对、查找相似文档 语言机制：契约式设计 异常：程序运行时发生的破坏性事件，通常表示为一种错误。相应采取的措施称为抛出异常。 断言：是在程序中某个位置确定应该为true的一个布尔表达式。如果表达式为false则程序会在运行时抛出异常AssertionError。程序员使用断言来测试错误并确保程序的正确性。断言还有描述程序意图的作用。 

算法和数据结构 

性能 原则：关注成本 科学方法五步骤： 1.观察自然界的某些特征 2.假设一个与观测结果相一致的模型 3.预测使用该假说的事件 4.通过进一步的观察来验证预测 5.通过反复验证直到确认假说和观察结果一致。 科学方法的一个关键原则是设计的是雅安是可重复的，因此其他人可以证明假说的有效性。此外我们置顶的假说必须可以被伪证，即我们可以确定一个假说是错误的。 观察：对程序运行时间的定量测量，第一个定性观察是如何刻画计算任务的问题规模。另一个定性观察是程序运行时间与输入本身的关系不大，而主要取决于问题规模的大小。 唐纳德 克努特证明了如下观点：尽管在理解程序的运行时间上存在各种复杂的因素，但从原则上而言，可以建立准确的模型帮助我们精确地预测一个特定程序的运行时间。对这类问题的正确分析包含如下内容： 透彻理解程序、透彻理解系统和计算机、数学分析的高级工具。 程序运行的总时间取决于以下两个主要因素：每条语句的执行时间成本、每条语句的执行频率。 增长量级分类 

函数类型增长量级示例框架常量型1count +=1语句（整数递增1）对数型log nwhile n>0: // n = n//2 // count += 1除半（二进制表示的位）线性型nfor i in range(n): // if a[i] == 0: // count +=1单循环线性对数型nlog n递归和分而治之合并排序算法二次型n^2for in range(n): // for j in range (i+1, n): // if (a[i]+a[j])==0: //count +=1两重嵌套循环（检查所有两对数）三次型n^3for i in range(n): // for j in range(i+1, n): // for k in range(j+1, n): // if (a[i]+a[j]+a[k])==0: //count +=1三重嵌套循环（检查所有三对数）指数型2^n格雷码穷举搜索（检测所有子集）

关于程序运行时间增长量级的验证假说方法： 1.评估解决大型问题的可行性 2.评估使用更快计算机的价值 3,。比较程序 分析程序性能注意事项：指令时间、非主导地位的内循环、系统考虑、势均力敌 、对输入值的强烈依赖、多个问题参数。原则上我们可以通过充分使用这些方法来实现详细准确的预测。 性能预测：在最坏的情况下运行时间是多少？ 算法分析家的任务是发现关于算法尽可能多的信息，应用程序员的任务是应用这些知识来开发程序，以有效地解决手头的问题。理想情况下，我们希望实现算法的代码紧凑且清晰，能够对甘心去的输入不仅提供最好的情况保障，而且得到良好的性能。 python的内置列表数据类型表示一个可变对象序列，列表支持数组的四种基本运算：创建、索引访问、索引赋值和迭代，相对数组列表允许插入项目和删除项目更通用。 可变数组是一个存储一系列数据项的数据结构，可以通过索引下标访问各项数据。python使用一个固定长度的数组存储各项数据的引用，第一部分依次存储各项数据项，第二部分保留用于后续插入操作。大小表示数据项个数，容量表示内部数组长度。 摊销分析：python列表操作的总成本除以操作的次数为一个常量。 python的字符串数据类型与python列表类似，主要区别是字符串是不可变对象。一个字符串包含一个指向字符串中自服务连续存储的内存地址的引用和字符串的长度。性能：拼接一个字符到一个字符串需要线性型运行时间，而拼接两个字符串所需的时间正比于结果字符串的长度。 内存被划分为字节，每个字节包含8位，每个位是单个二进制位。 整数和浮点数：16字节用于对象开销和8个字节用于数值表示（尾数、指数和标志） 布尔值：原则上可使用内存单独一个二进制位表示一个布尔值，实际上把布尔值表示为整数，对象Ture和False都使用24字节表示，是最小需要量的192倍，浪费会因缓存两个布尔对象而部分抵消。 缓存：为节省内存，Python为一个值仅创建一个对象拷贝。 字符串：40个字节用于对象开销，另外每个字符占一个字节。 数组：72字节用于对象开销（包括数组长度），另外每个对象引用（数组的每个元素）占用8个字节。一般而言包含n个整数或浮点数的数组占用的内存为72+32n个字节。保留字节占用额外的n个字节。 二维数组和对象数组：m行n列的二维数组每一行占用72+32n个字节的数组，总数为72（对象开销）+8m（对行的引用）+m（72+32n）（m行所占用的内存） 。 对象：表示一个用户自定义的对象至少需要数百字节。72字节对象开销加上280个字节绑定实例对象到对象的字典，加上指向每个实例变量的24个字节，再加上实例变量本身占用的内存。 关注成本：在（至少大多数）程序设计过程中，过度的优化是一切错误的根源。最常犯的错误就是过度关注性能特征，程序设计的最优先任务是保证代码的清晰性和正确性。 排序和查找 快速算法之二分查找算法 线性-对数之间的鸿沟 暴力算法 二分查找算法的程序运行时间为对数型，当程序的运行时间为参数n的线性函数时，其运行时间正比于n的值，一个对数运行时间仅正比与n的二进制位数。反相递增函数，物体称重法，排序数组，异常过滤器 插入排序算法：运行时间对输入值敏感。运行时间为二次型，可处理任何可比较的数据类型。 归并排序算法：运行时间为线性对数 二次-线性对数之间的鸿沟 理解差异的巨大性是理解算法设计和分析重要性的另一个关键步骤。 Python系统排序方法：归并排序算法版本，冯 诺依曼关于应用程序编程观点： 1.排序是许多应用程序的基本组成部分。 2.二次型算法对于许多实际目的显得太慢。 3.分而治之的方法十分有效。 4.证明程序的正确性和了解程序的开销都十分重要。 经验总结：重视计算成本、分而治之的算法、利用排序简化问题、了解底层工具。 栈和队列 删除规则：队列先进先出，栈后进先出。 下堆栈（后进先出栈）：基于Python列表（可变数组）实现栈、基于链表实现栈（链表是一个递归数据结果，定义为链表要么是空/null，要么是一个指向节点/node的引用，而节点包含指向链表的引用） FIFO队列：基于链表实现队列基于可变数组实现队列、随机队列。 栈、队列和随机队列的API本质上是相同的，不同之处仅仅在于类和方法名的选择。 符号表：一种数据类型，用于关联键和值。 API：关联数组（Associative array）、替换旧值策略（Replace-the-old-value policy）、不存在（Not found）、空键和空值、可迭代的（Itreable）、移除（Remove）、不可变值（Immutable key）、变种（Variation）、可比较键（Comparable key）。 客户端：1.字典查找：电话簿（黄页）、字典、账户信息、基因组学、实验数据、程序设计语言、文件、互联网域名系统。2.索引：书籍索引、程序设计语言、基因组学、Web搜索、账户信息。 实现：哈希表、二叉搜索树（BST）。 图：由一组顶点和一组边组成。每条边表示两个顶点之间的连接。如果两个顶点通过一条边连接，则它们是邻居（neighbor），一个顶点的度（degree）是其邻居的数量。 理解各系统结构体系：交通系统、人类生物学、社交网络、物理系统、通信系统、资源配置、机械系统、软件系统、金融系统。 API：无向图、字符串顶点类型、隐含顶点生成、自环和平行边、客户端查询方法。 客户端：单源客户端、分离度、其他客户端、最短路径距离、最短路径树、广度优先搜索算法、性能、邻接矩阵表示法。 小世界图特征：稀疏性，顶点的数量远远小于边的数量（规定平均顶点度小于20lgV）；平均路径长度短，如果随机选择两个顶点，它们之间的最短路径长度比较短（小于10lgV）；局部聚类性，如果两个顶点都是第三个顶点的邻居，则这两个顶点很可能彼此也是邻居（规定一种称为聚类系数的量值应该大于10%）。 经验总结：仔细设计你的数据类型、增量开发代码、在解决未知问题之前先解决你能理解的问题、持续测试并检查结果、使用现实世界的数据、重用软件、性能影响。