Skip to content

Latest commit

 

History

History
626 lines (405 loc) · 44.4 KB

01.md

File metadata and controls

626 lines (405 loc) · 44.4 KB

一、Python 对象、类型和表达式

数据结构和算法是大型复杂软件项目的两个核心元素。它们是一种在软件中存储和组织数据的系统方法，以便有效地使用数据。Python 具有高效的高级数据结构和有效的面向对象编程语言。Python 是许多高级数据任务的首选语言，这是有充分理由的。它是最容易学习的高级编程语言之一。直观的结构和语义意味着，对于不是计算机科学家，但可能是生物学家、统计学家或初创企业的主管的人来说，Python 是执行各种数据任务的简单方法。它不仅是一种脚本语言，而且是一种功能齐全的面向对象编程语言。

在 Python 中，语言中内置了许多有用的数据结构和算法。此外，由于 Python 是一种基于对象的语言，因此创建自定义数据对象相对容易。在本书中，我们将研究 Python 的内部库和一些外部库，并将学习如何根据第一原理构建自己的数据对象。

在本章中，我们将研究以下主题：

  • 获得数据结构和算法的一般工作知识
  • 了解核心数据类型及其功能
  • 探索 Python 编程语言的面向对象方面

技术要求

本书使用 Python 编程语言（3.7 版）介绍了数据结构和算法。本书假设您了解 Python。然而，如果您有点生疏，来自另一种语言，或者根本不懂 Python，请不要担心，这第一章会让您很快跟上进度。

以下是 GitHub 链接：https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Python-Second-Edition/tree/master/Chapter01 。

If you are not familiar with Python, then visit https://docs.python.org/3/tutorial/index.html, and you can also find the documentation at https://www.python.org/doc/. These are all excellent resources for easily learning this programming language.

安装 Python

要安装 Python，我们使用以下方法。

Python 是一种解释语言，语句是逐行执行的。程序员通常可以在源代码文件中写下一系列命令。对于 Python，源代码存储在一个具有.py文件扩展名的文件中。

Python 是完全集成的，通常已经安装在大多数 Linux 和 Mac 操作系统上。通常，预安装的 Python 版本是 2.7。您可以使用以下命令检查系统上安装的版本：

>>> import sys
>>> print(sys.version)
3.7.0 (v3.7.0:1bf9cc5093, Jun 27 2018, 04:06:47) [MSC v.1914 32 bit (Intel)]

您还可以在 Linux 上使用以下命令安装不同版本的 Python：

  1. 打开终端
  2. sudo apt-get update
  3. sudo apt-get install -y python3-pip
  4. pip3 install <package_name>

Python 必须安装在具有 Windows 操作系统的系统上，因为它与 Linux/macOS 不同，不是预先安装的。可以从以下链接下载 Python 的任何版本：https://www.python.org/downloads/ 。您可以下载软件安装程序并运行它，选择“为所有用户安装”，然后单击“下一步”。您需要指定要安装软件包的位置，然后单击“下一步”。之后，在 CustomizePython 对话框中选择 AddPython 到环境变量选项，然后再次单击 Next 进行最终安装。安装完成后，可以通过打开命令提示符并键入以下命令来确认安装：

python -V

最新的稳定 Python 版本是 Python 3.7.0。可以通过在命令行中键入以下命令来执行 Python 程序：

python <sourcecode_filename>.py

理解数据结构和算法

算法和数据结构是计算中最基本的概念。它们是构建复杂软件的主要构件。对这些基础概念的理解在软件设计中是极其重要的，这涉及以下三个特征：

  • 算法如何操作数据结构中包含的信息
  • 数据在内存中的排列方式
  • 特定数据结构的性能特征是什么

在这本书中，我们将从几个角度来研究这个话题。首先，我们将从数据结构和算法的角度来看 Python 编程语言的基础知识。其次，重要的是我们有正确的数学工具。我们需要理解计算机科学的基本概念，为此我们需要数学。通过采用启发式方法，制定一些指导原则意味着，一般来说，我们不需要高中数学就可以理解这些关键思想的原则。

另一个重要方面是评估。衡量算法的性能需要了解数据大小的增加如何影响对该数据的操作。当我们处理大型数据集或实时应用时，我们的算法和结构必须尽可能高效。

最后，我们需要一个强大的实验设计策略。能够从概念上将现实世界的问题转化为编程语言的算法和数据结构，需要能够理解问题的重要元素以及将这些元素映射到编程结构的方法。

为了更好地理解算法思维的重要性，让我们考虑一个真实的例子。假设我们在一个陌生的市场，我们被损坏的任务是购买一个项目列表。我们假设市场是随机分布的，每个供应商销售一个随机的项目子集，其中一些项目可能在我们的列表中。我们的目标是尽量降低每件商品的价格，同时尽量减少在市场上花费的时间。解决此问题的一种方法是编写如下算法：

1.供应商是否有我们清单上的项目，且成本低于该项目的预计成本？

2.如果是，购买并从列表中删除；如果没有，请转到下一个供应商。

3.如果没有更多的供应商，结束。

这是一个简单的迭代器，包含一个决策和一个操作。如果我们必须使用编程语言实现这一点，我们将需要数据结构来定义我们想要购买的物品列表和供应商正在销售的物品列表，并将其存储在内存中。我们需要确定每个列表中匹配项目的最佳方式，并且需要某种逻辑来决定是否购买。

关于这个算法，我们可以做一些观察。首先，由于成本计算是基于预测，我们不知道实际成本是多少。因此，我们不购买任何商品，因为我们低估了该商品的成本，并且我们到达了市场的尽头，我们的清单上还有剩余的商品。为了处理这种情况，我们需要一种有效的存储数据的方法，以便能够以最低的成本高效地回溯到供应商。

此外，我们需要了解将购物清单上的商品与每个供应商出售的商品进行比较所需的时间。这一点很重要，因为随着我们购物清单上的商品数量或每个供应商出售的商品数量的增加，搜索商品需要花费更多的时间。我们搜索项目的顺序和数据结构的形状会对搜索所需的时间产生很大的影响。显然，我们希望安排我们的名单以及我们访问每个供应商的订单，以尽量减少搜索时间。

另外，考虑一下当我们改变买入条件，以最便宜的价格买入，而不只是低于平均预测价格时会发生什么。这完全改变了问题。我们不需要按顺序从一个供应商到下一个供应商，我们需要遍历一次市场，有了这些知识，我们可以根据我们想要访问的供应商来订购我们的购物清单。

显然，将现实世界的问题转化为抽象结构（如编程语言）涉及到许多微妙之处。例如，当我们在市场中前进时，我们对产品成本的了解会提高，因此我们预测的平均价格变量会变得更加准确，直到最后一个摊位时，我们对市场的了解变得完美为止。假设任何一种回溯算法都会产生成本，我们就有理由回顾我们的整个策略。高价格可变性、数据结构的大小和形状以及回溯成本等条件都决定了最合适的解决方案。整个讨论清楚地表明了数据结构和算法在构建复杂解决方案中的重要性。

用于数据的 Python

Python 有几个内置的数据结构，包括列表、字典和集合，我们使用它们来构建定制对象。此外，还有许多内部库，如集合和数学对象，它们允许我们创建更高级的结构，并对这些结构执行计算。最后，还有一些外部库，比如 SciPy 包中的库。这使我们能够执行一系列高级数据任务，如逻辑和线性回归、可视化和数学计算，如矩阵和向量运算。外部库对于开箱即用的解决方案非常有用。但是，我们还必须意识到，与从头开始构建定制对象相比，通常会有性能损失。通过学习如何自己编写这些对象的代码，我们可以将它们定位到特定的任务中，从而提高它们的效率。这并不是要排除外部库的作用，我们将在第 12 章设计技巧和策略中对此进行探讨。

首先，我们将概述一些使 Python 成为数据编程的最佳选择的关键语言特性。

Python 环境

Python 由于其可读性和灵活性而成为世界上最流行和使用最广泛的编程语言之一。Python 环境的一个特性是其交互式控制台，允许您将 Python 用作桌面可编程计算器，也可以用作编写和测试代码片段的环境。

**控制台的read...evaluate...print循环是与更大的代码库交互的一种非常方便的方式，例如运行函数和方法或创建类的实例。这是 Python 相对于编译语言（如 C/C++或 Java）的主要优势之一，与 Python 的read...evaluate...print循环相比，write...compile...test...recompile循环可以大大增加开发时间。能够输入表达式并获得即时响应可以大大加快数据科学任务的速度。

除了官方的 CPython 版本外，还有一些优秀的 Python 发行版。其中两款最受欢迎的是：Anaconda（https／／www【T18 c】【inuumioo/downooownot5】t5】t5】t5】t5】ds和雨棚https／wwwe【T78houghtcoo【T102 mrotcts/canopy/）。大多数发行版都有自己的开发环境。Canopy 和 Anaconda 都包含用于科学、机器学习和其他数据应用的库。大多数发行版都有编辑器。

除了 CPython 版本之外，还有许多 Python 控制台的实现。其中最值得注意的是 IPython/Jupyter 平台，它基于一个基于 web 的计算环境。

变量和表达式

为了通过算法实现来解决实际问题，我们首先要选择变量，然后对这些变量进行操作。变量是附着到对象的标签。变量不是对象，也不是对象的容器；它们仅作为对象的指针或引用。例如，考虑下面的代码：

在这里，我们创建了一个变量a，它指向一个列表对象。我们创建了另一个变量b，它指向同一个列表对象。当我们将一个元素附加到此列表对象时，此更改同时反映在a和b中。

在 Python 中，变量名在程序执行期间附加到不同的数据类型；不需要首先声明变量的数据类型。每个值都是一种类型（例如，字符串或整数）；但是，指向此值的变量名没有特定类型。更具体地说，变量指向一个对象，该对象可以根据指定给它们的值的类型更改其类型。考虑下面的例子：

在前面的代码示例中，a的类型从int更改为float，具体取决于变量中存储的值。

可变范围

函数内部变量的作用域规则很重要。每当函数执行时，都会创建一个本地环境（名称空间）。此本地命名空间包含由函数指定的所有变量和参数名。每当调用一个函数时，Python 解释器首先查找本地名称空间，如果没有找到匹配项，则该名称空间就是函数本身，然后查找全局名称空间。如果仍然找不到该名称，则会在内置命名空间中搜索。如果没有找到，那么解释器将引发一个NameError异常。考虑下面的代码：

a=15;b=25
def my_function():
  global a 
  a=11;b=21

my_function() 
print(a)  #prints 11 
print(b)  #prints 25

在前面的代码中，我们定义了两个global变量。我们需要使用关键字global告诉解释器，在函数中我们引用的是global变量。当我们将此变量更改为11时，这些更改将反映在全局范围内。但是，我们设置为21的b变量是函数的局部变量，在函数内部对其所做的任何更改都不会反映在全局范围内。当我们运行函数并打印b时，我们看到它保留了它的全局值。

另外，让我们考虑另一个有趣的例子：

>>> a = 10
>>> def my_function():
...     print(a)
>>> my_function ()
10

代码正常，输出为10，但见以下代码：

>>> a = 10 
>>> def my_function():
...     print(a)
...     a= a+1 
>>> my_function()

UnboundLocalError: local variable 'a' referenced before assignment

前面的代码给出了一个错误，因为对作用域中的变量赋值会使该变量成为该作用域的局部变量。在上例中，在a变量的my_function()赋值中，编译器假设a为局部变量，这就是为什么较早的print()函数尝试打印未初始化为局部变量的局部变量a；因此，它给出了一个错误。可以通过将外部范围变量声明为global来访问外部范围变量来解决此问题：

>>> a = 10
>>> def my_function():
...     global a
...     print(a)
...     a = a+1
>>> my_function()
10

因此，在 Python 中，函数中引用的变量是隐式全局变量，如果在函数体中的任何位置为a变量赋值，则假定该变量为局部变量，除非显式声明为全局变量

流控制与迭代

Python 程序由一系列语句组成。解释器按顺序执行每条语句，直到没有更多语句为止。如果文件作为主程序运行，以及通过import加载，则此情况成立。所有语句，包括变量赋值、函数定义、类定义和模块导入，都具有相同的状态。没有比任何其他语句具有更高优先级的特殊语句，并且每个语句都可以放在程序中的任何位置。程序中的所有指令/语句通常按顺序执行。然而，控制程序执行条件语句和循环流的方法主要有两种。

if...else和elif语句控制语句的条件执行。一般格式是一系列的if和elif语句，然后是最终的else语句：

x='one' 
if x==0:
   print('False')
elif  x==1:
   print('True')
else:  print('Something else')

#prints'Something else'

注意使用==运算符比较两个值。如果两个值相等，则返回True；否则返回False。还要注意，将x设置为字符串将返回Something else，而不是像在非动态类型语言中可能发生的那样生成类型错误。动态类型化语言（如 Python）允许灵活分配不同类型的对象。

控制程序流的另一种方法是使用循环。Python 提供了两种构造循环的方法，例如while和for循环语句。while循环重复执行语句，直到布尔条件为真。for循环提供了一种通过一系列元素在循环中重复执行的方法。以下是一个例子：

在本例中，while循环执行语句，直到条件x < 3为真。让我们考虑另一个例子，使用一个用于 Ty3T3 循环的 ORT T2。

>>>words = ['cat', 'dog', 'elephant']
>>> for w in words:
...     print(w)
... 
cat
dog
elephant

在本例中，循环的对列表中的所有项目执行迭代。

数据类型和对象概述

Python 包含各种内置数据类型。其中包括四种数字类型（int、float、complex、bool），四种序列类型（str、list、tuple、range），一种映射类型（dict）和两种集合类型。还可以创建用户定义的对象，例如函数或类。我们将在本章中介绍字符串和列表数据类型，并在下一章中介绍其余的内置类型。

Python 中的所有数据类型都是对象。事实上，Python 中几乎所有东西都是对象，包括模块、类和函数，以及字符串和整数等文本。Python 中的每个对象都有一个类型、一个值和一个标识。当我们写入greet= "helloworld"时，我们正在创建一个字符串对象的实例，其值为"hello world"，标识为greet。对象的标识充当指向对象在内存中位置的指针。对象的类型，也称为对象的类，描述对象的内部表示，以及它支持的方法和操作。一旦创建了对象的实例，就不能更改其标识和类型。

我们可以通过内置函数id()获取对象的身份。这将返回一个标识整数，在大多数系统上，这是指它的内存位置，尽管在任何代码中都不应依赖于此。

此外，还有许多方法可以比较对象；例如，请参见以下内容：

if a==b:    # a and b have the same value

if a is b:    # if a and b are the same object

if type(a) is type(b):   #a and b are the same type

需要对可变和不可变对象进行重要区分。可变对象（如列表）的值可以更改。它们有一些方法，例如insert()或append()，可以更改对象的值。不可变对象（如字符串）的值不能更改，因此当我们运行它们的方法时，它们只返回一个值，而不是更改基础对象的值。当然，我们可以通过将该值赋给变量或将其用作函数中的参数来使用该值。例如，int类在创建实例后是不可变的，其值不能更改，但是引用此对象的标识符可以重新分配另一个值。

串

字符串是不可变的序列对象，每个字符表示序列中的一个元素。与所有对象一样，我们使用方法来执行操作。字符串是不可变的，不会更改实例；每个方法只返回一个值。此值可以存储为另一个变量，也可以作为函数或方法的参数提供。

下表列出了一些最常用的字符串方法及其说明：

| 方法 | 描述 | | s.capitalize | 返回仅第一个字符大写的字符串，其余字符为小写。 | | s.count(substring,[start,end]) | 统计子字符串的出现次数。 | | s.expandtabs([tabsize]) | 将选项卡替换为空格。 | | s.endswith(substring,[start, end] | 如果字符串以指定的子字符串结尾，则返回True。 | | s.find(substring,[start,end]) | 返回子字符串第一次出现的索引。 | | s.isalnum() | 如果所有字符都是字符串s的字母数字，则返回True。 | | s.isalpha() | 如果所有字符都是字符串s的字母，则返回True。 | | s.isdigit() | 如果字符串中的所有字符都是数字，则返回True。 | | s.split([separator],[maxsplit]) | 拆分由空格或可选分隔符分隔的字符串。返回一个列表。 | | s.join(t) | 按t顺序连接字符串。 | | s.lower() | 将字符串转换为所有小写。 | | s.replace(old, new[maxreplace]) | 将旧的子字符串替换为新的子字符串。 | | s.startswith(substring, [start, end]]) | 如果字符串以指定的子字符串开头，则返回True。 | | s.swapcase() | 返回字符串中大小写已交换的字符串副本。 | | s.strip([characters]) | 删除空白或可选字符。 | | s.lstrip([characters]) | 返回删除前导字符的字符串副本。 |

与所有序列类型一样，字符串支持索引和切片。我们可以使用字符串的索引s[i]从字符串中检索任何字符。我们可以使用s[i:j]检索字符串的切片，其中i和j是切片的起点和终点。我们可以使用步幅返回一个扩展切片，如下所示-s[i:j:stride]。以下代码应明确说明这一点：

前两个示例非常简单，分别返回位于索引1处的字符和字符串的前七个字符。请注意，索引从0开始。在第三个示例中，我们使用的步幅为2。这将导致每秒返回一个字符。在最后一个示例中，我们省略了结束索引，切片返回整个字符串中的每一个字符。

只要值是整数，就可以使用任何表达式、变量或运算符作为索引：

另一个常见操作是使用循环遍历字符串：

由于字符串是不可变的，因此出现的一个常见问题是我们如何执行诸如插入值之类的操作。我们不需要更改字符串，而是需要考虑如何为需要的结果构建新的字符串对象。例如，如果我们想在问候语中插入一个单词，我们可以为以下内容分配一个变量：

正如这段代码所示，我们使用 slice 操作符在索引位置5拆分字符串，并使用+连接。Python 从不将字符串的内容解释为数字。如果需要对字符串执行数学运算，首先需要将其转换为数字类型：

列表

列表是最常用的内置数据结构之一，因为它们可以存储任意数量的不同数据类型。它们是对象的简单表示，由从零开始的整数索引，正如我们在字符串的情况中所看到的。

下表包含最常用的列表方法及其说明：

| 方法 | 说明 | | list(s) | 返回序列s.的列表 | | s.append(x) | 在列表s的末尾追加元素x。 | | s.extend(x) | 在列表s末尾追加列表x。 | | s.count(x) | 返回列表s中x出现的次数。 | | s.index(x,[start],[stop]) | 返回最小索引i，其中s[i]==x。我们可以为查找包含一个可选的开始和停止索引。 | | s.insert(i,e) | 在索引i处插入x。 | | s.pop(i) | 返回元素i并将其从列表s中删除。 | | s.remove(x) | 从列表s中删除元素x。 | | s.reverse() | 颠倒列表s的顺序。 | | s.sort(key,[reverse]) | 使用可选键对列表s进行排序并将其反转。 |

在 Python 中，列表实现与其他语言相比有所不同。Python 不会创建变量的多个副本。例如，当我们在另一个变量中分配一个变量的值时，两个变量都指向存储该值的相同内存地址。只有当变量更改其值时，才会分配副本。这个特性使 Python 的内存效率更高，因为它只在需要时创建多个副本

这对列表等可变复合对象具有重要影响。考虑下面的代码：

在前面的代码中，list1和list2变量都指向相同的内存位置。然而，当我们将y通过list2更改为4时，实际上我们也在更改list1所指向的相同y变量。

list的一个重要特征是它可以包含嵌套结构；也就是说，列表可以包含其他列表。例如，在下面的代码中，列表items包含其他三个列表：

我们可以使用括号操作符访问列表的值，因为列表是可变的，所以它们被复制到位。下面的示例演示如何使用它来更新元素；例如，我们将面粉价格提高了 20%：

我们可以使用一种非常常见和直观的方法从表达式创建列表；也就是说，**列出理解。**它允许我们通过一个表达式直接创建一个列表到列表中。考虑下面的示例，其中使用该表达式创建列表 AutoT0}：

列表理解可以非常灵活；例如，考虑下面的代码。它本质上展示了执行函数组合的两种不同方式，其中我们将一个函数（x*4）应用到另一个函数（x*2）。下面的代码打印出两个列表，表示f1和f2的函数组成，首先使用 for 循环计算，然后使用列表理解：

def f1(x): return x*2 
def f2(x): return x*4

lst=[]
for i in range(16):
   lst.append(f1(f2(i)))

print(lst)
print([f1(x) for x in range(64) if x in [f2(j) for j in range(16)]])

第一行输出来自 for 循环构造。第二个来自列表理解表达式：

列表理解还可以用于以更紧凑的形式复制嵌套循环的操作。例如，我们将list1中包含的每个元素相乘：

我们还可以将列表理解用于其他对象，如字符串，以构建更复杂的结构。例如，以下代码创建单词及其字母计数的列表：

正如我们将看到的，列表是我们将要研究的许多数据结构的基础。它们的多功能性、易于创建和使用使它们能够构建更专业、更复杂的数据结构。

作为第一类对象的函数

在 Python 中，不仅仅是数据类型被视为对象。函数和类都是第一类对象，允许以与内置数据类型相同的方式对它们进行操作。根据定义，第一类对象如下所示：

  • 在运行时创建
  • 指定为变量或在数据结构中
  • 作为参数传递给函数
  • 作为函数的结果返回

在 Python 中，术语第一类对象有点用词不当，因为它意味着某种层次结构，而所有 Python 对象本质上都是第一类的。

为了了解其工作原理，让我们定义一个简单的函数：

def greeting(language): 
   if language=='eng': 
        return 'hello world'
      if language =='fr'
        return 'Bonjour le monde'
      else: return  'language not supported'

由于用户定义的函数是对象，因此我们可以将它们包含在其他对象中，例如列表：

函数也可以用作其他函数的参数。例如，我们可以定义以下函数：

这里，callf()将函数作为参数，将语言变量设置为'eng'，然后以语言变量作为参数调用函数。例如，如果我们想制作一个程序，返回各种语言中的特定句子，也许是某种自然语言应用，那么我们可以看到这是多么有用。在这里，我们有一个中心位置来设置语言。除了问候功能，我们还可以创建类似的功能，返回不同的句子。通过设置语言的一个点，程序逻辑的其余部分就不必担心这一点。如果我们想改变语言，我们只需改变语言变量，就可以保持其他一切不变。

高阶函数

将其他函数作为参数或返回函数的函数称为高阶函数。Python 3 包含两个内置的高阶函数-filter()和map().注意，在早期版本的 Python 中，这些函数返回列表；在 Python3 中，它们返回一个迭代器，这使它们更加高效。map()函数提供了一种将每个项目转换为可编辑对象的简单方法。例如，这里有一种高效、紧凑的方法来对序列执行操作。注意lambda匿名函数的使用：

类似地，我们可以使用过滤器内置函数来过滤列表中的项目：

请注意，map 和 filter 执行相同的功能，类似于列表理解所能实现的功能。与列表理解相比，使用内置函数 map 和 filter 而不使用lambda操作符时，性能特性似乎没有太大的差异，除了性能上的一点优势。尽管如此，大多数样式指南建议使用列表理解而不是内置函数，可能是因为它们更易于阅读。

创建我们自己的高阶函数是函数式编程风格的标志之一。高阶函数如何有用的一个实际例子如下所示。这里，我们将传递len函数作为 sort 函数的键。这样，我们可以按长度对单词列表进行排序：

下面是不区分大小写排序的另一个示例：

注意list.sort()方法和排序的内置函数之间的差异。list.sort()方法是 list 对象的一种方法，它对 list 的现有实例进行排序，而不复制它。此方法更改目标对象并返回None。Python 中的一个重要约定是，更改对象的函数或方法返回None，以明确没有创建新对象，并且对象本身已更改。

另一方面，排序的内置函数返回一个新列表。它实际上接受任何 iterable 对象作为参数，但它总是返回一个列表。列表排序和排序都将两个可选关键字参数作为键。

对更复杂的结构进行排序的一种简单方法是使用要排序的元素的索引，使用 lambda 运算符，例如：

这里我们已按价格对商品进行了分类。

递归函数

递归是计算机科学中最基本的概念之一。当函数在执行过程中对自身进行一次或多次调用时，称为递归。循环迭代和递归的不同之处在于循环通过布尔条件或一系列元素重复执行语句，而递归则重复调用函数。在 Python 中，我们只需在自己的函数体中调用递归函数，就可以实现递归函数。为了阻止递归函数变成无限循环，我们至少需要一个参数来测试终止情况，以结束递归。这有时被称为基本情况。应该指出，递归不同于迭代。虽然两者都涉及重复，但迭代通过一系列操作循环，而递归则反复调用函数。从技术上讲，递归是迭代的特例，称为尾部迭代，通常可以将迭代函数转换为递归函数，反之亦然。递归函数的有趣之处在于，它们能够在有限语句中描述无限对象。

下面的代码应该演示递归和迭代之间的区别。这两个函数都只是打印出介于低和高之间的数字，第一个函数使用迭代，第二个函数使用递归：

请注意，对于迭代示例iterTest，我们使用 while 语句测试条件，然后调用 print 方法，最后增加低值。递归示例测试条件，打印，然后调用自身，增加其参数中的 low 变量。一般来说，迭代更有效；然而，递归函数通常更容易理解和编写。正如我们将要看到的，递归函数对于操作递归数据结构（如链表和树）也很有用。

生成器和 co 例程

通过使用 yield 语句，我们可以创建不只是返回一个结果，而是返回整个结果序列的函数。这些函数称为**生成器。**Python 包含生成器函数，这是创建迭代器的一种简单方法，特别适用于替换不可行的长列表。生成器生成项目而不是生成列表。例如，以下代码显示了为什么我们可能选择使用生成器，而不是创建列表：

#compares the running time of a list compared to a generator 
import time
#generator function creates an iterator of odd numbers between n and m 
def oddGen(n,m):
    while n<m:
      yield n
      n+=2

#builds a list of odd numbers between n and m 
def oddLst(n,m):
     lst=[]
     while n<m:
        lst.append(n)
        n+=2
     return lst

#the time it takes to perform sum on an iterator
t1=time.time()
sum(oddGen(1,1000000))
print("Time to sum an iterator: %f" % (time.time() - t1))
#the time it takes to build and sum a list
t1=time.time()
sum(oddLst(1,1000000))
print("Time to build and sum a list: %f" % (time.time() - t1))

这将打印出以下内容：

正如我们所看到的，构建一个列表来进行此计算需要花费更长的时间。由于使用生成器，性能提高是因为值是按需生成的，而不是保存为内存中的列表。计算可以在生成所有元素之前开始，并且仅在需要时生成元素。

在前面的示例中，当计算需要时，sum 方法会将每个数字加载到内存中。这是通过生成器对象反复调用__next__ ()特殊方法实现的。生成器从不返回除None以外的值。

通常，生成器对象用于 for 循环。例如，我们可以利用前面代码中创建的oddLst生成器函数打印出1和10之间的奇数整数：

for i in oddLst (1,10):print(i)

我们还可以创建一个生成器表达式，它除了用括号替换方括号外，还使用与列表理解相同的语法并执行相同的操作。但是，生成器表达式不创建列表；他们创建了一个生成器对象。此对象不创建数据，而是根据需要创建该数据。这意味着生成器对象不支持序列方法，例如append()和insert()。

但是，您可以使用list()功能将生成器更改为列表：

类与对象编程

类是创建新类型对象的一种方式，它们是面向对象编程的核心。类定义了一组在该类的实例之间共享的属性。通常，类是函数、变量和属性的集合。

面向对象的范例是引人注目的，因为它为我们提供了一种具体的方式来思考和表示程序的核心功能。通过围绕对象和数据而不是操作和逻辑组织程序，我们有了一种健壮而灵活的方法来构建复杂的应用。当然，动作和逻辑仍然存在，但通过将它们体现在对象中，我们有了一种封装功能的方法，允许对象以非常特定的方式进行更改。这使得我们的代码不那么容易出错，更容易扩展和维护，并且能够对真实世界的对象进行建模。

类是使用 class 语句在 Python 中创建的。这定义了一组与类实例集合关联的共享属性。一个类通常由许多方法、类变量和计算属性组成。重要的是要理解，定义类本身并不会创建该类的任何实例。要创建实例，必须为类指定一个变量。类主体由一系列在类定义期间执行的语句组成。类中定义的函数称为**实例方法。**通过将该类的实例作为第一个参数传递给该类实例，将一些操作应用于该类实例。此参数按约定称为 self，但它可以是任何合法标识符。下面是一个简单的例子：

class Employee(object):
    numEmployee=0
    def init (self,name,rate):
        self.owed=0 
        self.name=name
        self.rate=rate 
      Employee.numEmployee += 1

    def del (self): 
        Employee.numEmployee-=1

    def hours(self,numHours):
         self.owed += numHours*self.rate
         return ("%.2f hours worked" % numHours)

    def pay(self):
        self.owed=0
        return("payed %s " % self.name)

类变量，例如numEmployee，在类的所有实例之间共享值。在本例中，numEmployee用于统计员工实例的数量。注意，Employee类实现了__init__ and __del__特殊方法，我们将在下一节中讨论。

我们可以通过以下操作创建Employee对象的实例、运行方法以及返回类和实例变量：

特殊方法

我们可以使用dir(object)函数获取特定对象的属性列表。以两个下划线开头和结尾的方法称为**特殊方法。除以下例外外，**特殊方法一般由 Python 解释器而非程序员调用；例如，当我们使用+操作符时，实际上是在调用to _add_ ()调用。例如，我们可以使用len(my_object)，而不是使用my_object._len_ ()；在字符串对象上使用len()实际上要快得多，因为它返回表示内存中对象大小的值，而不是调用对象的_len_方法。

通常，我们在程序中实际调用的唯一特殊方法是_init_方法，用于在我们自己的类定义中调用超类的初始值设定项。强烈建议不要对自己的对象使用双下划线语法，因为当前或将来可能会与 Python 自己的特殊方法发生冲突。

但是，我们可能希望在自定义对象中实现特殊的方法，以便为它们提供一些内置类型的行为。在下面的代码中，我们创建了一个实现_repr_方法的类。此方法创建对象的字符串表示形式，用于检查：

class my_class():
    def __init__(self,greet):
        self.greet=greet 
    def __repr__(self):
        return 'a custom object (%r) ' % (self.greet)

当我们创建这个对象的实例并检查它时，我们可以看到我们得到了定制的字符串表示。注意使用%r格式占位符返回对象的标准表示。这是非常有用的最佳实践，因为在本例中，它向我们展示了greet对象是由引号表示的字符串：

遗产

继承是面向对象编程语言最强大的功能之一。它允许我们从其他类继承功能。可以创建一个通过继承修改现有类行为的新类。继承意味着，如果一个类的对象是通过继承另一个类创建的，那么该对象将拥有这两个类的所有功能、方法和变量；即父类和新类。我们从中继承功能的现有类称为父类/基类，新类称为派生类/子类。

继承可以用一个非常简单的例子来解释，我们创建了一个employee类，该类具有诸如雇员姓名和他每小时工资的比率等属性。我们现在可以创建一个新的specialEmployee类，继承employee类的所有属性。

Python 中的继承是通过在类定义中将继承的类作为参数传递来完成的。它通常用于修改现有方法的行为。

specialEmployee类的一个实例与Employee实例相同，只是hours()方法有所改变。例如，在下面的代码中，我们创建了一个新的specialEmployee类，继承Employee类的所有功能，同时也改变了hours()方法：

class specialEmployee(Employee):
    def hours(self,numHours):
        self.owed += numHours*self.rate*2 
        return("%.2f hours worked" % numHours)

子类要定义新的类变量，需要定义一个__init__()方法，如下所示：

class specialEmployee(Employee):
    def __init__(self,name,rate,bonus):
        Employee.__init__(self,name,rate)    #calls the base classes                                                     
        self.bonus=bonus

    def   hours(self,numHours):
        self.owed += numHours*self.rate+self.bonus     
        return("%.2f hours worked" % numHours)

请注意，基类的方法不是自动调用的，派生类必须调用它们。我们可以使用内置的isinstance(obj1,obj2)函数测试类成员资格。如果obj1属于obj2的类或从obj2派生的任何类，则返回True。让我们考虑下面的例子来理解这一点，在这里，Ty5T5 和 AutoT6.分别是 AdT7 和 St8 类的对象：

#Example issubclass() to check whether a class is a subclass of another class  
#Example isinstance() to check if an object belongs to a class or not 

print(issubclass(specialEmployee, Employee))
print(issubclass(Employee, specialEmployee)) 

d = specialEmployee("packt", 20, 100) 
b = Employee("packt", 20)  
print(isinstance(b, specialEmployee)) 
print(isinstance(b, Employee)) 

# the output prints  
True 
False 
False 
True

通常，所有方法都在类中定义的类的实例上操作。然而，这不是一项要求。方法有两种类型：静态方法和类方法，静态方法与类方法非常相似，主要绑定到类，不绑定到类的对象。它是在类中定义的，不需要类的实例来执行。它不会对实例执行任何操作，它是使用@staticmethod类装饰器定义的。静态方法无法访问实例的属性，因此它们最常见的用法是方便将实用程序函数分组在一起。

类方法对类本身进行操作，而不处理实例。类方法的工作方式与类变量与类而不是该类的实例相关联的方式相同。类方法是使用@classmethod装饰器定义的，与类中的实例方法不同。作为第一个参数传递，exponentialB类继承exponentialA类，将基类变量改为4。我们还可以运行父类的exp()方法，如下所示：

class exponentialA(object):
    base=3
    @classmethod
    def exp(cls,x):
        return(cls.base**x) 

    @staticmethod   
    def addition(x, y):  
        return (x+y)

class exponentialB(exponentialA):
        base=4

a = exponentialA() 
b= a.exp(3) 
print("the value: 3 to the power 3 is", b) 
print('The sum is:', exponentialA.addition(15, 10)) 
print(exponentialB.exp(3))

#prints the following output
the value: 3 to the power 3 is 27 
The sum is: 25 
64

静态方法和类方法的区别在于，静态方法对类一无所知，它只处理参数，而类方法只处理类，其参数始终是类本身。

类方法之所以有用，有几个原因。例如，由于子类继承其父类的所有相同特性，因此它有可能破坏继承的方法。使用类方法是一种精确定义运行哪些方法的方法。

数据封装与属性

除非另有规定，否则所有属性和方法都可以无限制地访问。这也意味着基类中定义的所有内容都可以从派生类访问。当我们构建面向对象的应用时，这可能会导致问题，因为我们可能希望隐藏对象的内部实现。这可能导致派生类中定义的对象与基类之间的命名空间冲突。为了防止出现这种情况，我们使用定义私有属性的方法有一个双下划线，例如__privateMethod()。这些方法名称会自动更改为__Classname_privateMethod()，以防止与基类中定义的方法发生名称冲突。请注意，这并没有严格隐藏私有属性，而是提供了一种防止名称冲突的机制。

在使用类属性定义可变属性时，建议使用私有属性。属性是一种属性，它在调用时计算其值，而不是返回存储值。例如，我们可以使用以下内容重新定义exp()属性：

class Bexp(Aexp):
    base=3
    def exp(self):
        return(x**cls.base)

总结

本章向我们介绍了 Python 编程的基本原理和介绍。我们描述了 python 提供的各种数据结构和算法。我们介绍了变量、列表和一些控制结构的使用，并学习了如何使用条件语句。我们还讨论了函数在 python 中的使用，讨论了各种对象，以及一些关于 python 语言面向对象方面的材料。我们创建了自己的对象并从中继承。

Python 还提供了更多功能。当我们准备在后面的章节中研究一些算法的实现时，下一章将重点讨论数字、序列、映射和集合。这些也是 Python 中的数据类型，在为一系列操作组织数据时证明是有用的。

进一步阅读