Python算法和数据结构

说明

本文主要是对Problem Solving with Algorithms and Data Structures Using Python的翻译和自己的一些理解。


目标

  • 回顾计算机科学,编程和解决问题的思想
  • 理解抽象化和它在问题解决过程中所扮演的角色
  • 理解和实现抽象数据类型的概念
  • 回顾Python编程语言

开始

(我们回想:)过去的编程方式经历了许多挑战,因为首先电子计算机需要跳接电缆(patch cables)和交换机,把指令从人传输到机器。就像人类社会的许多方面,计算机技术的变革给计算机科学家提供了越来越多的工具和平台来实践他们的想法。诸如更快的处理器,高速网络,大容量内存等这些进步创造了急剧增长的复杂事物,计算机科学家必须通过它们来完成工作。在所有这些(东西的)快速发展期间,许多基本的定律一直在不断的保持着。计算机科学与使用计算机解决问题有关。
你无疑花费了许多时间学习解决问题的基础,并且希望对你的提出问题陈述和开发解决方案的能力感到自信。你也了解到写计算机程序通常很难。庞大的问题的复杂性和解决方案的相应的复杂性会(趋向于)掩盖与解决问题过程相关的基本思想。
这个章节剩下的部分强调了两个重要的领域。首先,它回顾了(必须)与计算机科学和算法、数据结构的学习相符合的体系结构。特别是,我们(为什么需要)学习这些主题(的原因)和(如何)理解这些主题(会)帮助我们成为一个更好的问题解决者。其次我们回顾了Python编程语言,即使我们无法提供一个详细的,毫无遗漏的参考书,但是在余下的章节中,我们会给出例子以及基本的观念和思想的解释。


什么是计算机科学

计算机科学通常很难定义。这可能是由于“计算机”这个单词在(“计算机科学”)这个名称中的不成功的使用。因为你或许知道,计算机科学不只是计算机的学习。即使计算机在这个学科中,作为一个工具,起着重要的支撑作用,但是它们只是工具。
计算机科学是对问题,解决问题和从解决问题的过程中产生的解决方案的学习。被给出一个问题的时候,计算机科学家的目标是开发一个算法,算法是一个用来解决可能会出现的问题的任何实例的指令的有序序列。算法是一个有穷的过程,如果按照算算法来执行,那么会解决一类问题。算法就是解决方案。
计算机科学被认为是算法的学习。然而我们必须谨慎的指出这个事实:有些问题或许没有解决方案。即使提供这段说明超出了这篇文档的范围,但是有些问题不能够被解决这个事实对于学习计算机科学的人是非常重要的。我们来完整地定义一下计算科学:它既包含问题的类型,也包含计算机科学是对问题的解决方案以及没有解决方案的问题的学习(这个说明)。
当描述问题和解决方案的时候,通常会包含“可计算的”这个单词。如果解决问题的算法存在,我们就称这个问题是“可计算的”。因此,对计算机科学的另外一种定义就是:计算机科学是对可计算和不可计算的问题的学习,对算法的存在和不存在的学习。在任何情形下,都可以注意到:根本没有提到“计算机”这个词。解决方案被认为是不依赖机器的。
因为计算机科学是与解决问题的过程(本身)有关的,因此它也是对抽象化的学习。抽象化允许我们以这样一种方式:分离所谓的逻辑视角和物理视角,看待问题和解决方案。这个基本思想对我们来说是很熟悉的。下面是一个通用的例子:
假设今天你可能开车去学校或公司,你作为一个司机,车的使用者,需要发出特性的交互,以便利用车完预期的目的。为了驾驶,你需要上车,插入钥匙,启动车,挂挡,刹车,加速,操纵控制。从抽象的角度看,我们可以说:你正在看汽车的逻辑视角。为了把你从一个地点运输到另外一个地点的目的,你正在使用汽车设计者提供的函数,这些函数有时也被称为“接口”。
另外一方面,修车的技工采纳了一个非常不同的观点。她不仅需要知道如何驾驶,也必须了解对执行我们认为理所当然的函数来说必要的细节。它需要了解发动机如何工作,变速齿轮如何传动,温度如何控制等等。这被认为是物理视角,细节发生在底层。
当我们使用计算机的时候,会发生相同的事情。大多数的人使用计算来编写文档,发送和接收电子邮件,在网上冲浪,听音乐,存储图片,玩游戏,而无需了解为了允许这些种类的应用程序工作而发生的细节。他们从逻辑或用户的视角看待计算机。计算机科学家,程序员,技术支持人员和系统管理员对计算机采取了一个非常不同的看法,他们必须了解操作系统如何工作,网络协议如何配置,如何编写(控制函数的)各种脚本这些细节。他们必须能够控制底层细节。
这些例子的共同点是:抽象化的用户(有时也被称为客户端)无需了解细节,只需要知道接口工作的方式。接口是用户与底层实现沟通的方式。另外一个抽象化的例子---python的math模块,一旦我们导入这个模块,就可以执行计算,比如:

>>> import math
>>> math.sqrt(16)
4.0  
>>> 


这是一个过程抽象的例子,我们没有必要知道平方根是如何被计算出来的,只需要知道调用哪一个函数和如何使用它。如果我们正确地执行了导入,那么就可以假设:这个函数会给我们提供正确的结果。我们知道有人实现了平方根问题的解决方案,但是我们只需要知道如何使用它。这有时被称为“黑盒”。我们简单的描述接口:函数的名字,需要什么(也就是参数)和返回什么。细节被隐藏在内部:
blackbox


什么是编程

编程是提出算法,把它编码成一种符号,一种编程语言(以便它能被计算机执行)的过程。即使存在许多编程语言和许多不同类型的计算机,但是重要的第一步是有解决方案。没有算法,就没有程序。
计算机科学不是编程的学习,然而编程是计算机科学家所做的事情中一个重要的部分。编程通常是我们为我们的解决方案创建一种表现形式的方式。因此语言表现形式和创建它的过程成为了这门学科的基本部分。
算法从(代表问题实例所需要的)数据和(对生成预期结果有必要的)步骤集合的角度描述问题的解决方案。编程语言必须提供一种标记方式来表现过程和数据。为了达到这个目的,语言提供了控制结构和数据类型。
控制结构允许把算法的步骤以一种方便且清晰的方式表示出来。算法至少需要执行顺序处理,(用于作出决策的)选择和(用于重复控制的)循环的控制结构。只要编程语言提供了这些基本的语句,它就可以用于算法实现。
在计算机中,所有的数据项都被表示为二进制的字符串。为了给出这些字符串的含义,我需要有数据类型。数据类型提供了对二进制数据的解释,以便我们能够明确地回想起对问题的解决有意义的数据。这些底层的,内建的数据类型(有时也被称为原始数据类型)提供了用于算法开发的“积木”。
比如:大多数编程语言都提供了用于整数的数据类型。计算机内存中的二进制字符串可以被解释为整数,并且被赋予典型的含义:我们通常所说的整数(比如23, 654和-19)。另外,数据类型也提供了数据项能够参与的操作的描述。使用整数的时候,诸如加,减,乘这些操作是共有的。我们期望数字类型的数据可以参与这些算术运算。
对我们来说经常出现的困难是问题和他们的解决方案非常复杂。这些简单的,语言提供的控制结构和数据类型,即使足以表现复杂的解决方案,但是在问题解决过程中通常处于不利地位的。我们需要控制这些复杂性和帮助创建解决方案的方法。


为什么学习数据类型和抽象数据类型

为了管理问题和解决问题过程中的复杂性,计算机科学家使用抽象化来使他们聚焦在“大局”,而不迷失在细节中。通过创建问题领域的模型,我们能够使用更好,更有效的解决问题的方式。这些模型允许我们以一种更加一致性的方式描述算法中操纵的(与问题本身有关的)数据。
之前,我们称过程抽象为隐藏了(一个特别的)(允许用户或客户端站在“非常高的层级”上看待它的)函数的细节的过程。我们现在把注意力转向一个相似的思想-数据抽象化。抽象数据类型(有时被缩写为ADT)是一个(我们如何看待)数据和允许的操作的逻辑描述,我们不必考虑这些操作是如何实现的。这意味着我们只关心数据代表什么,而不关心它究竟是如何构造的。通过提供这个级别的抽象,我们在数据周围创建了一个“封装”。思想就是:通过封装实现的细节,从用户的视角隐藏他们。这叫做“信息隐藏”。
下面的图片展示了抽象数据类型是什么以及它是如何运转的。用户与接口进行交互,(接口)使用抽象属类型指定的操作。抽象数据类型是一个“壳”,用户和这个“壳”进行交互。实现被隐藏在更深的一级。用户不必关心实现的细节。
adt 抽象数据类型的实现通常被称为数据结构。它要求我们使用程序构造的和原始的数据类型的一些集合,来提供数据的物理视图。就像我们之前讨论的,这两个视图的分离允许我们为我们的问题定义复杂的数据模型,而不必给出任何关于该模型实际上是如何构建的细节(的说明)。它提供了数据的实现无依赖的试图。因为实现一个数据类型通常有许多不同的方式,实现无依赖允许程序员(在不改变用户的交互方式的前提下,)切换实现的细节。用户可以继续专注于解决问题的过程。


为什么学习算法

计算机科学家借鉴经验,我们通过看其他人解决问题以及通过自己解决问题来学习。接触不同的解决问题的技术和看不同的算法是如何设计的有助于我们接受下一个(给我们的)具有挑战性的问题。通过思考大量的不同的算法,我们能够开始开发模式识别,以便下次一个相似的问题出现时,我们能够更好的解决它。
算法之间通常是有很大的差别的,比如说:之前看到的sqrt的例子,完全有可能有许多不同的方式来实现计算平方根函数的细节。一个算法可能比另外一个算法使用更少的资源。一个算法返回结果花费的时间可能是另外一个算法的十倍。我们有一些方式来比较这两个解决方案。即可它们都可以工作,但是一个可能比另外一个更好。我们可以假设:一个算法更加高效,或者一个算法运行的更快或者使用更少的内存。当我们学习算法的时候,也可以学习分析技术,分析技术允许我们基于解决方案自己的特性,而不是用于实现它们的程序或计算机的特性,来比较它们。
在最坏的情况下,问题可能是难以解决的,这意味着,在现实的时间里,没有算法能够解决这个问题。能够辨别有解决方案的问题,没有解决方案的问题,有解决方案但是需要太多的时间或其他资源的(来完成的)问题是非常重要的。
经常有需要我们确定和决定的取舍。作为计算机科学家,除了解决问题的能力,我们也需要了解和理解解决方案评估技术。最后,解决一个问题经常有许多方式,寻找解决方案,然后确定它是否是一个好的解决方案,将是我们要一遍又一遍做的任务。

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: