Python编程实战：寻找回文

灰太狼 2022-09-10 05:08 147阅读 0赞

仔细观察单词Radar、Kayak、Rotator和Sexes，它们有什么共同的特点呢？这些单词都是回文（Palindrome），无论是从前往后拼写，还是从后往前拼写，它们都构成同一个单词。回文短语在这方面表现得更加明显，整个短语正着拼写和倒着拼写都表达同样的意思。拿破仑就是一位著名的回文创造者。拿破仑曾被流放到厄尔巴岛，当第一次见到这个岛时他说道：“Able was I ere I saw Elba.”

2011年，DC漫画公司出版了一本有趣的书，书中的某些故事情节就涉及回文。当超级英雄女巫萨塔娜受到诅咒时，她只能通过默念回文形式的咒语来施展法力。为了击败挥舞着剑的攻击者，女巫萨塔娜必须设法想出诸如“nurses run”“stack cats”“puff up”之类的两字短语。这引发了我的思考：故事中的回文短语到底还有多少呢？女巫萨塔娜还有更好的选择吗？

在本章中，你会从网上获取字典文件，并把这些文件加载到程序中，再利用编写的Python程序寻找这些文件所包含的回文单词。接下来，你会学习从文件中寻找更为复杂的回文短语的方法。之后，你将尝试用一个叫作cProfile的工具分析程序代码的性能，该工具有助于你编写出性能更好的代码。最后，你会学习回文的筛选方法，看看它们中有多少个具有“攻击”性的含义。

# 2.1　寻找和加载字典文件 #

本章中的所有项目均需要使用一个以文本格式存储的单词列表文件。通常，这种文件也被称为字典文件（Dictionary File）。因此，在继续学习新内容之前，我们先来探讨一下加载字典文件的问题。

尽管我们称这样的文件为字典文件，但是字典文件中只包含单词本身，不包含单词的发音、音节数、含义等。这是一个好消息，倘若字典文件中包含单词的这些信息，那将阻碍我们进行本章的项目。对你来说，还有一个更好的消息，那就是这些字典文件可以免费从网上获取。

从本书配套资源给定的链接中可以找到适用于本章项目的字典文件。下载其中的一个文件，或者以在线的方式直接打开所选文件，复制其内容并粘贴到诸如Notepad、WordPad（macOS上的TextEdit）之类的文本编辑软件中，将其另存为.txt类型的文本文件。将字典文件和Python程序放在同一目录中。本章项目使用的文本文件名字是2of4brif.txt。该文件位于配套资源的压缩文件12dicts-6.0.2.zip中。

除了配套资源给出的文件外，UNIX和类UNIX操作系统中还附带一个含有200000多个单词的大型单词文件，并用换行符把这些单词分隔开。该文件通常存储于/usr/share/dict/words或者/usr/dict/words目录下。在Debian GNU/Linux操作系统上，该单词列表存储在/usr/share/ opendict/dictionary目录下。在macOS上，字典文件通常存储在/Library/ Dictionaries目录下，这个目录下还包含一些非英文的字典文件。若要使用这些字典文件，你需要根据操作系统及版本在线查找这些文件的准确存储位置。

有些字典文件不包含单词a和I；而在有些字典中，每个字母都可以作为一个单独的单词（例如，d就是字典文件中以字母d开头的首个单词）。在本书项目中，我们将忽略单个字母形式的回文。因此，刚刚提到的问题应该容易解决。

# 2.1.1　处理文件打开异常 #

无论什么时候，当加载一个外部文件时，程序都会自动检查一些I/O问题，并告知你是否存在这样的问题，例如文件丢失或文件名错误。

使用下面的try和except语句来捕获和处理程序执行过程中某些错误引发的异常：

➊ try :
          ➋ with open(file) as in_file :
                 do something
         except IOError➌ as e :
          ➍ print("{}\nError opening {}. Terminating program.".format(e, file),
                     file = sys.stderr)
          ➎ sys.exit(1)

首先，执行try语句块➊。该语句块内的with语句能够保证嵌套代码块无论以什么样的方式结束，文件都会被自动关闭➋。在终止进程之前关闭已打开文件是一种很好的编程习惯。如果不关闭这些文件，可能会耗尽系统的文件描述符（长时间运行的大型脚本就容易出现这类问题）。在Windows操作系统中，若不关闭文件，系统就会锁定文件，造成文件无法被进一步访问。如果一直向这些文件中写入数据，会使文件损坏或者数据丢失。

如果出现错误，并且错误类型与except关键字之后命名的异常类型相匹配➌，那么会跳过剩余的try语句，直接执行except语句块内的语句➍。若没有出现错误，程序就只执行try语句块内的语句，同时跳过except语句块。except语句块中的print语句会让用户知道存在的问题是什么，而file=sys.stderr参数会将IDLE解释器窗口中的错误语句标红。

语句sys.exit(1) ➎用于终止程序。语句sys.exit(1)表示程序退出，参数1表明程序没有正常关闭。

若发生的异常与except语句指定的异常类型不匹配，则这个异常会被抛给任何外部try语句块或主程序。若不存在该类型异常的处理语句，则这个异常会导致程序终止，并发出标准的“traceback”错误提示消息。

# 2.1.2　加载字典文件 #

清单2-1的功能是以列表的形式加载字典文件的内容。你既可以手动输入该脚本，也可以从本书配套资源中获取其对应的程序文件*load\_dictionary.py*。你可以把这个文件当作模块导入其他程序中，并用一行代码调用它。请记住，模块是一个可以在其他Python程序中使用的Python程序。你可能已经意识到模块是代码的一种抽象（Abstraction）表示方法。抽象意味着你不必关注代码的所有细节。抽象的原则就是封装（Encapsulation），它会隐藏行为的细节。将加载文件的代码封装到一个模块中，这样在另一个程序中就不必关注它的实现细节。

清单2-1　将一个字典文件加载至列表中的模块代码

load_dictionary.py
         """以列表的形式加载一个文本文件。
    
         参数：
         文本文件的名字。
    
         异常:
         若没有找到文件，则报告IOError类型的异常。
    
         返回值:
         一个包含文本文件中所有单词小写形式的列表。
    
         要求导入的模块 sys。
    
         """
      ➊ import sys
    
      ➋ def load(file):
             """打开文本文件，并以列表的形式返回文件内容对应的小写字母。"""
             try:
                 with open(file) as in_file:
                  ➌ loaded_txt = in_file.read().strip().split('\n')
                  ➍ loaded_txt = [x.lower() for x in loaded_txt]
                     return loaded_txt
             except IOError as e:
              ➎ print("{}\nError opening {}. Terminating program.".format(e, file),
                     file=sys.stderr)
                sys.exit(1)

在文档字符串之后，为了让错误处理代码起作用，我们通过导入sys模块来调用一些系统函数➊。接下来的代码段定义了一个load()函数，该函数基于前面讨论过的文件加载方法实现➋，它以要加载的文件名为参数。

若打开文件时没有引发异常，则删除文本文件中的空格，并将各数据项单独分成一行保存至列表变量中➌。在函数返回列表之前，让每个单词都成为列表中的一个单独项。由于Python会区分字符的大小写，因此使用列表推导（List Comprehension）方法将所有单词统一转换为小写➍。列表推导是一种将列表或其他可迭代对象转换为另一个列表的快捷方法。在本例中，列表推导起到for循环的作用。

如果遇到I/O错误，程序会显示标准错误消息，并根据错误消息的描述参数e显示该事件产生的原因，同时向用户发出程序即将结束的提示➎。然后，使用sys.exit(1)命令终止程序。

这段示例代码是为了说明这些步骤的功能。一般来说，你不会直接调用sys模块的exit()函数，在程序结束之前，你可能还希望它做一些其他的事情，例如向日志文件中写入数据。为了使代码简洁和易于控制，在后面的章节中会把try-except代码块和sys.exit()语句都写到main()函数中。

# 2.2　项目2：寻找回文单词 #

首先，你将在字典文件中寻找回文单词。然后，你将学习寻找更为困难的回文短语的方法。

> **目标**
> 
> 使用Python在英文字典文件中搜索回文。

# 2.2.1　策略和伪代码 #

在开始编写代码之前，先想一想你要做什么。识别回文是一件很容易的事情，即将一个单词简单地与它自身的反向切片进行比较。下面是一个生成单词正向切片和反向切片的示例：

>>> word = 'NURSES'
    >>> word[:]
    'NURSES'
    >>> word[::-1]
    'SESRUN'

当对字符串（任何可分割类型）做切片操作时，若不提供切片的区间和步长，则默认的起始和终止位置分别是字符串的开头和结尾，步长等于1。

图2-1所示为反向切片的完整过程。本例指定的起始位置为2，步长为−1。由于没有提供结尾索引（在冒号之间没有指定索引值或设置空格），因此在执行切片操作时，将从后向前逐个（步长为−1）遍历字符串中的单词，直到没有字符剩下为止。

![6dede57453dc6873cb0147b87b906d4b.png][]

图2-1　单词“NURSES”的反向切片示例

反向切片与正向切片的行为并不完全相同，这种不同主要表现在起始位置值的设置以及对端点的处理。这种不同可能会混淆正反向切片，为了避免这一问题，我们将单词的反向切片简单地设置为\[::-1\]。

与加载字典文件相比，在字典中查找回文单词所需的代码更少。下面是查找回文单词的伪代码：

以列表的形式加载字典文件中的单词
    创建一个空列表，保存查找到的回文单词
    循环遍历列表中的每个单词：
       如果单词的正向切片与反向切片相同：
          将该单词添加到回文单词列表中
    输出回文单词列表

# 2.2.2　寻找回文单词的代码 #

清单2-2是程序*palindromes.py*的源代码，该程序会判断从字典文件中读取的哪些单词是回文，并将这些回文单词保存到一个列表中，最后输出列表中的各个回文单词项。从本书的配套资源中可以下载到这段代码。除此以外，还需要用到程序*load\_dictionary.py*和一个字典文件。记住，将这些文件保存在同一目录下。

清单2-2　从加载的字典文件中寻找回文单词

palindromes.py
         """在字典文件中寻找回文单词"""
      ➊ import load_dictionary
      ➋ word_list = load_dictionary.load('2of4brif.txt')
      ➌ pali_list = []
    
      ➍ for word in word_list:
             if len(word) > 1 and word == word[::-1]:
                 pali_list.append(word)
    
         print("\nNumber of palindromes found = {}\n".format(len(pali_list)))
      ➎ print(*pali_list, sep='\n')

首先，将程序*load\_dictionary.py*当作一个模块导入本程序➊。需要注意的是，在导入模块时不必输入文件的扩展名.py。此外，这个模块应该与本程序位于同一目录下。这样就不必指定该模块的路径名。由于导入的这个模块（load\_dictionary）已经包含导入语句import sys，因此我们不需要在本程序里重复导入它。

为了用字典中的单词填充定义的单词列表，使用点符号调用load\_dictionary模块中的load()函数➋。将字典文件的名称当作该函数的参数。同样地，若字典文件与Python程序位于同一目录下，则不需要指定该文件所在的路径。本程序使用的字典文件可能与你使用的字典文件有所不同。

接下来，创建一个保存回文的空列表➌。然后循环遍历word\_list列表中的每个单词➍，判断单词的正向切片与反向切片是否相同。如果这个单词本身与它的切片相同，那么将该单词添加到列表pali\_list中。需要注意的是，含有一个字母以上的单词（len(word) > 1）才满足回文的严格定义。

最后，单独输出列表中的各个回文单词，即输出的单词之间没有分隔符（引号或逗号）➎。通过循环遍历列表中每个单词的方式也可以实现这样的功能，但是这里采用一种更加高效便捷的做法，即使用分拆操作符（Splat Operator）——在对象前加上符号\*。在本程序中，分拆操作符以列表为输入，将列表中的每个元素分拆成函数的位置参数。函数print()的最后一个参数的作用是：设置数据之间的分隔符，默认的分隔符是空格（sep=' '）。然而，本程序想把每个回文单词都单独输出在一行上（sep='\\n'）。

在英文中，回文单词相当少见。对于一个含有60000个单词的字典文件，若足够幸运，你可能会找到大约60个或者说约0.1%的回文单词。尽管回文单词不太常见，但是利用Python程序很容易找到它们。现在，让我们来看看更有趣、更复杂的回文短语。

# 2.3　项目3：寻找回文短语 #

与寻找回文单词相比，寻找回文短语（Palingram）需要考虑更多事情。在本节中，我们将编写一个查找回文短语的程序。

> **目标**
> 
> 使用Python在英文字典中搜索两个单词构成的回文现象，并使用cProfile工具来分析和优化这段搜索回文短语的代码。

# 2.3.1　策略和伪代码 #

“nurses run”和“stir grits”就是两个回文短语的例子，如图2-2所示。与回文单词类似，从回文短语中间的字母开始，它从前读和从后读都是一样的字母序列。我喜欢把这样的“中间字母或字母组”当作核心词（Core Word）。对单词“nurses”来说，它由回文序列（Palindromic Sequence）和倒序词序列（Reversed Word）派生而来。

![c7b9afd9078ba55938ecbf949fe5a897.png][]

图2-2　剖析回文短语

本项目对应的程序会检查回文短语的核心词。根据图2-2的描述，可对核心词的特点做出以下推论。

1．核心词的字母数量既可以是奇数，也可以是偶数。

2．从核心词的开头部分起，当反向读取字母序列时，这些连续的字母会拼凑成一个单词（First Part）。

3．这个连续的部分由核心词的部分字母或者全部字母组成。

4．核心词剩余部分的连续字母构成回文序列（Second Part）。

5．回文序列可以由核心词的部分字母或全部字母组成。

6．回文序列不一定是一个真正的单词（除非它由该单词的所有字母组成）。

7．这两个部分不能重叠或共享字母。

8．回文序列本身是可逆的。

> **注意**
> 
> 如果整个核心词都由倒序词组成，而核心词又不是回文单词，那么这样的单词被称为回字（Semordnilap）。回字类似于回文单词，它们间关键的区别是：回文单词倒读时会拼写成相同的单词，而回字倒读时会拼写成一个不同的单词。例如，单词bats与单词stab互为回字，单词wolf与单词flow互为回字。

图2-3所示为由6个字母组成的任意单词。“X”代表单词的一部分，当倒着读时，它可能会组成一个真正的单词（例如单词“nurses”中的“run”）。“O”表示可能的回文序列（例如单词“nurses”中的“ses”）。图2-3中左侧的单词会组成一个类似于图2-2中nurses的单词，它们的开头都由一个倒序词组成。图2-3中右侧的单词会组成一个类似于图2-2中grits的单词，倒序词位于单词的末尾部分。需要注意的是，单词的组合数等于每一列中单词的字母总数加1。还需要注意的是，顶部和底部的行代表两种相同的情况。

![febddb83a4d3b321a199848b3ebc8204.png][]

图2-3　在含有6个字母的核心单词中，倒序部分（X）和回文序列（O）的可能位置

每一列的最顶行代表回字，最底行代表回文。回字和回文都属于倒序词，只是它们属于不同的倒序词类型而已。因此，将回字和回文视为同一种东西，并且在循环中用一行代码就可判断出它们。

若要查看实际的关系图，请参考图2-4所示。从图中可以看出，在回文短语“devils lived”和“retro porter”中，单词“devils”和单词“porter”都是核心词。这两个短语在回文序列和倒序词方面互为镜像。以回字evil和回文kayak为例，比较这两种情况。

![075a707c71b9755d5ccd8b74b726b9f9.png][]

图2-4　单词、回字和回文中的倒序部分（X）和回文序列（O）

回文既是倒序词又是回文序列。由于回文与回字具有相同的X模式，因此可以使用处理回字的代码来处理回文。

从策略上来讲，你需要循环遍历字典中的每个单词，判断其是否属于图2-3中的某个组合。假设字典文件中有60000个单词，则程序大约需要做500000次判断。

为了理解这个循环，请查看图2-5中回文“stack cats”的核心单词。你的程序需要循环遍历单词中的每个字母，遍历过程从结尾的字母开始；下次迭代时增加一个字母，即从次尾字母开始，依次类推。为了找到像“stack cats”这样的回文短语，还要判断核心词（stack）的末尾是否存在回文序列，以及它的开头是否存在一个倒序单词。需要注意的是，图2-5所示的第一个循环判断就会成功，因为在回文短语中，单独的字母（k）也能组成回文。

![649fff55a6171dd4583984ae67a974a0.png][]

图2-5　当循环遍历核心词时，寻找回文序列和倒序词

但是，这样做还不够。如果想判断它是否存在图2-3中的“镜像”现象，你必须倒着执行遍历过程，即从单词的开头查找回文序列，从单词的结尾查找倒序词。这种方法可以让你找到像“stir grits”这样的回文短语。

下面是查找回文短语的伪代码：

以列表的形式加载字典文件中的内容
    创建一个保存回文短语的空列表
    遍历列表中的每个单词：
       获取单词的长度
       如果单词长度大于1：
          遍历单词中的每个字母：
             如果该单词前面的字母组成倒序词，并且该单词剩余的字母构成回文序列：
                 将单词及倒序词添加至回文短语列表中
             如果该单词末尾的字母组成倒序词，并且该单词前面的字母组成回文序列：
                 将单词及倒序词添加至回文短语列表中
    按照字母表顺序对列表中的回文短语排序
    输出回文短语列表中的回文单词对

# 2.3.2　寻找回文短语的代码 #

清单2-3是程序*palingrams.py*的代码实现。该程序先循环遍历单词列表，确定哪些单词对构成回文短语，再将这些回文短语对保存到列表中，并单独输出回文列表中的各个数据项。从本书的配套资源中可以获得该程序。当开始本项目时，建议以2of4brif.txt为项目的字典文件，这样程序的运行结果会与本书所给的结果一致。记住，将字典文件、程序*load\_dictionary.py*以及程序*palingrams.py*放到同一目录下。

清单2-3　在已加载的字典中查找和输出回文短语

palingrams.py
         """寻找给定字典文件中的所有回文短语"""
         import load_dictionary
    
         word_list = load_dictionary.load('2of4brif.txt')
    
         # 寻找回文短语
      ➊ def find_palingrams():
             """寻找字典中的回文短语。"""
             pali_list = []
             for word in word_list:
              ➋ end = len(word)
              ➌ rev_word = word[::-1]
              ➍ if end > 1:
                  ➎ for i in range(end):
                      ➏ if word[i:] == rev_word[:end-i] and rev_word[end-i:] in word_list:
                            pali_list.append((word, rev_word[end-i:]))
                      ➐ if word[:i] == rev_word[end-i:] and rev_word[:end-i] in word_list:
                            pali_list.append((rev_word[:end-i], word))
          ➑ return pali_list
    
      ➒ palingrams = find_palingrams()
         # 根据短语的第一个单词，对回文短语进行排序
         palingrams_sorted = sorted(palingrams)
    
         # 输出回文短语列表
      ➓ print("\nNumber of palingrams = {}\n".format(len(palingrams_sorted)))
         for first, second in palingrams_sorted:
             print("{} {}".format(first, second))

在清单2-3中，先利用在程序*palindromes.py*中用过的方法加载字典文件。然后，定义一个查找回文短语的函数➊。该函数使寻找回文短语的代码和统计寻找字典中回文短语所耗费时间的代码相分离。

在find\_palingrams()函数的内部创建一个名为pali\_list空列表变量，用该列表保存程序发现的所有回文短语。紧接着，定义一个for循环，逐一检查列表word\_list中的每个单词。在for循环体内，先获取单词的长度，并将其值赋给变量end➋。单词的长度决定了对单词进行切片操作时使用的索引值，它还确定了倒序词和回文序列可能的组合数。

接下来，对单词进行反向切片，将切片结果分配给变量rev\_word➌。为了增强代码的可读性，也可以用''.join(reversed(word))操作替代word\[::-1\]反向切片操作。

由于寻找的是单词对形式的回文短语，因此应排除单字母型的单词➍。然后，在该循环体内以嵌套的方式定义一个for循环，遍历当前单词中的所有字母➎。

紧接着，执行条件判断语句：判断单词后面的字母是否构成回文序列，同时判断单词前面的剩余字母组成的倒序词是否位于单词列表中（换句话说，判断倒序词是否属于一个“真正的”单词）➏。如果该单词满足条件，就把该单词及其倒序词添加到回文短语列表中。

由图2-3可知，必须再次执行条件判断语句，但要改变切片操作的方向和词序，以达到倒置输出结果的目的。换句话说，你必须判断单词的开头是否构成回文序列➐，而不是判断单词的末尾是否构成回文序列。在函数定义的末尾，返回回文短语列表➑。

当函数定义完后，就可以在程序中调用它➒。在for循环中，将字典中的单词添加到回文短语列表时会导致单词顺序发生改变，所以这些回文短语不会按照字母表顺序排列。因此，根据单词对中的第一个单词，使回文列表按照字母表顺序排列。最后，输出列表的长度➓，并让每个回文短语都单独显示在一行上。

如前所述，当运行程序*palingrams.py*时，搜索一个包含约60000个单词的字典文件大约要花费3分钟。在下一节中，我们将研究该程序耗时的关键因素，并尝试提高程序的运行效率。

# 2.3.3　程序性能分析 #

程序性能分析是一种通过收集与程序运行行为相关的统计数据而展开的分析过程，例如在程序执行过程中，收集函数的调用次数和运行函数所耗费的时间。程序性能分析是优化程序的关键，它能够准确地得出程序的哪些部分占用较多的时间和内存。这样一来，程序开发者就知道从哪里入手来提高程序的运行性能。

# 1．用cProfile模块分析程序性能 #

性能是度量程序质量的重要指标。性能分析器应该输出程序执行期间各部分耗费的时间和运行频次。Python标准库中就有这样的性能分析模块——cProfile，它是一个适合对长时间运行程序进行性能分析的C语言扩展程序。

find\_palingrams()函数中的某些操作可能导致程序*palingrams.py*的运行时间较长。为了确认这一猜想，我们可以运行cProfile程序性能分析器，检查程序*palingrams.py*中各操作的耗时情况。

将下面的代码复制到一个名为*cprofile\_test.py*的新文件中，并将它放到*palingrams.py*程序和字典文件所在的目录中。下面这段代码的作用是导入模块cProfile和程序palingrams，并用cProfile模块检查find\_palingrams()函数的性能。其中，点号表示函数调用。需要注意的是，当导入模块时，无须指定模块的扩展名（.py）：

import cProfile
    import palingrams
    cProfile.run('palingrams.find_palingrams()')

运行程序*cprofile\_test.py*，当运行完毕后（将在解释器窗口中看到“>>>”），你应该会看到类似下面这样的输出内容：

62622 function calls in 199.452 seconds
    
      Ordered by: standard name
    
      ncalls  tottime  percall  cumtime  percall filename:lineno(function)
           1    0.000    0.000  199.451  199.451 <string>:1(<module>)
           1  199.433  199.433  199.451  199.451 palingrams.py:7(find_palingrams)
           1    0.000    0.000  199.452  199.452 {built-in method builtins.exec}
       60388    0.018    0.000    0.018    0.000 {built-in method builtins.len}
        2230    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}

在测试计算机上，所有循环、切片和搜索操作共花费199.452秒。当然，在不同的计算机上得到的统计结果可能会有所不同。你还可以获得一些与内置函数相关的额外信息。由于每得到一个回文短语都要调用内置的append()函数，因此通过append()函数的调用次数可以知道找到的回文短语总数量（2230个）。

> **注意**
> 
> 一般来说，常在解释器窗口中直接运行cProfile模块来分析程序性能。该模块还允许你将输出结果另存到文本文件中，利用浏览器就可查看文件的内容。若想获得更多有关该模块的信息，请访问Python官网中与该模块相关的主题。

# 2．用time模块统计程序运行时间 #

统计程序运行时间的另一种方法是使用time.time()函数，它会返回一个纪元时间戳（Epoch Timestamp）——从1970年1月1日0时0分0秒到当前经历的秒数。将文件*palingrams.py*中的代码复制到一个新文件内，将这个新文件命名为*palingrams\_timed.py*，同时在该程序的顶部插入以下代码：

import time
    start_time = time.time()

现在，跳转到文件末尾，添加如下代码片段：

end_time = time.time()
    print("Runtime for this program was {} seconds.".format(end_time-start_time))

保存该程序并运行它。几秒后，你可以在解释器窗口的底部看到如下输出信息：

Runtime for this program was 222.73954558372498 seconds.

从解释器窗口中的输出结果来看，程序的运行时间比原来要长，这是因为本次统计的不是函数find\_palingrams()的运行时间，而是整个程序的运行时间（输出语句也包含在内）。

与cProfile模块不同，time模块提供的统计信息不够详细。但与cProfile模块一样，该模块也可以单独统计某个代码块的运行时间。重新编辑刚刚运行的程序，改变统计时间的开始和结束语句（如下面代码段中的粗体部分所示），这样就可将程序运行时耗费时间的函数find\_palingrams()“包裹”起来：

start_time = time.time()
    palingrams = find_palingrams()
    end_time = time.time()

保存这个程序并运行它。你可以在解释器窗口的底部看到如下输出信息：

Runtime for this program was 199.42786622047424 seconds.

这次程序的输出结果与先前用cProfile模块的输出结果一致。如果重新运行程序，或者使用不同的计时器统计程序运行时间，你会得到完全不同的输出结果，但不要过分关注输出结果之间的差异。程序运行的相对时间才是指导代码优化的关键。

# 3．回文短语程序优化 #

但对我来说，为了得到回文短语而等待3分钟是不能接受的。由程序性能分析结果可知，程序的大部分时间都耗费在find\_palingrams()函数上。这可能与列表的读写、切片以及搜索操作有关。采用其他的数据结构（如元组、集合或字典）可能会加快该函数的执行速度。特别地，当使用in关键字时，集合的运行速度要比列表快得多。集合利用散列表进行快速的查找。散列算法可将文本字符串转换为比文本本身小得多的唯一数字，这会让搜索操作更加高效。此外，当用列表存储数据时，对每个数据项的搜索都是呈线性的。

想象如下场景，思考该问题：如果在家里寻找丢失的手机，你可以列出一张房间清单。在找到手机之前，你只需依次检查清单上的每个房间；然而，你也可以不按列出的清单依次搜索每个房间，而是用另一部手机拨打丢失手机的号码，根据手机铃声，直接进入手机所在的房间。

集合的一个缺点是：集合中元素的顺序是不可控的，且它不允许有重复的值。当使用列表时，它的元素顺序是可控的，还允许元素重复，但是它的查找操作会耗费更长的时间。幸运的是，对本项目而言，我们不必关心元素的顺序性和重复性，因此集合才是最佳选择。

改写程序*palingrams.py*中函数find\_palingrams()的代码，采用集合存储单词，如清单2-4所示。从配套资源中的*palingrams\_optimized.py*程序里可以找到这段代码。如果想检查这个新程序的运行时间，你只需对*palingrams\_timed.py*的副本进行少许修改。

清单2-4　利用集合存储单词，优化函数find\_palingrams()的代码

palingrams_optimized.py
         def find_palingrams():
             """寻找字典中的回文短语。"""
             pali_list = []
          ➊ words = set(word_list)
          ➋ for word in words:
                 end = len(word)
                 rev_word = word[::-1]
                 if end > 1:
                     for i in range(end):
                      ➌ if word[i:] == rev_word[:end-i] and rev_word[end-i:] in words:
                            pali_list.append((word, rev_word[end-i:]))
                      ➍ if word[:i] == rev_word[end-i:] and rev_word[:end-i] in words:
                            pali_list.append((rev_word[:end-i], word))
            return pali_list

与原来的代码相比，优化后的代码只有4行发生改变。定义一个新的变量words，用它来保存word\_list列表对应的集合➊。然后，遍历整个集合➋。在这个集合中查找单词的切片并判断它是否属于该集合➌➍，而以前该操作作用的对象是列表。

下面是程序  
*palingrams\_optimization.py*中新的find\_palingrams()函数运行时所耗费的时间：

Runtime for this program was 0.4858267307281494 seconds.

哇！程序的运行时间由3分钟减少为不足一秒！这就是优化！这两个程序的不同之处在于采用的数据结构。验证单词是否属于列表是一个非常耗费时间的操作。

为什么刚开始时我向你介绍“错误”的方法呢？因为实际情况就是这样的。你必须先让代码正常运行，然后考虑代码的优化。这是一个有经验的程序员从一开始就会考虑到优化的简单例子，但是它蕴含着优化的整体思想：尽全力先让程序运行起来，然后让程序变得更好。

本文摘自：《Python编程实战》

![11381f7956861e81857c12fc4800b8ef.png][]

你可以把本书当作学习Python的辅助类图书。本书是一本完全面向初学者的入门图书。在本书中，你将使用基于项目的方法进行自我训练。本书不会浪费你的金钱和书架空间，也不是对你已学过的知识概念的重新整理。不过，请别担心！本书不会让你独自去完成这些项目，书中所有的代码均有注释和解释。

本书的这些项目适用于希望通过编程进行实验仿真、理论验证、自然现象模拟和获取快乐的人。其中包括那些将编程作为工作的一部分但并不是程序员的人（如科学家和工程师），还包括那些“非专业人士”——编程的业余爱好者和把编程当作娱乐消遣的人。如果你想弄明白本书提到的项目，但又发现自己从头开始做这些复杂的项目会非常艰巨或耗费大量时间，那么本书就很适合你。

本书基于Python语言，通过项目展示Python的奇妙应用，适合Python初学者学习。在本书中，你将使用Python编程语言模拟探索火星、木星以及银河系最遥远的地方，体验诗人的意境，了解高级的金融知识等。你还会学到各种各样的技术，如马尔可夫链分析技术、蒙特卡罗模拟、图像叠加技术、基因遗传算法等。与此同时，你还会学习一些模块的使用方法，例如pygame、Pylint、pydocstyle、Tkinter、python-docx、Matplotlib和pillow等。

[6dede57453dc6873cb0147b87b906d4b.png]: /images/20220829/97cb449cb0414411aeffdd22213e4f69.png
[c7b9afd9078ba55938ecbf949fe5a897.png]: /images/20220829/a59cd7f7b5934bf49824a606d7d0cb2c.png
[febddb83a4d3b321a199848b3ebc8204.png]: /images/20220829/ab6a70df52cc43af95e81881253ba46b.png
[075a707c71b9755d5ccd8b74b726b9f9.png]: /images/20220829/e1caecf33d5d4f019c89146f9908ea36.png
[649fff55a6171dd4583984ae67a974a0.png]: /images/20220829/049b9d144661426f80486734c6275af6.png
[11381f7956861e81857c12fc4800b8ef.png]: /images/20220829/0e4885be7bbd4e138d5c188c00b76981.png