1.1　约束

 主存容量有限，通常量级小于需要处理、生成的数据量。

 无标识符，即没有变量名或者带标签的内存地址，只有以数字表示的内存地址。

1.2　代码

  1 #!/usr/bin/env python
  2 
  3 import sys, os, string
  4 
  5 # 用于处理“辅助存储器”的中间件
  6 def touchopen(filename, *args, **kwargs): 
  7     try:
  8         os.remove(filename) 
  9     except OSError:
 10         pass
 11     open(filename, "a").close() # "touch"文件
 12     return open(filename, *args, **kwargs)
 13     
 14 # 内存受限，不应多于1024个内存单元
 15 data = []
 16 # 幸运的是，
 17 # 所有的停止词共556个字符，并且每行的字符数不超过80个，因此我们可以利用
 18 # 这一点来简化问题：在处理每一行输入的同时，将停止词加载至内存中。
 19 # 如果这两个假设不成立的话，整个算法需要做相应的调整。
 20
 21 # 全局策略：（第一部分）读取输入文件，计算单词个数的同时，将数值存入
 22 # 辅助存储器（一个文件）中。（第二部分）在辅助存储器中寻找出现频率最高的
 23 # 25个单词。
 24 
 25 # 第一部分：
 26 # - 一次读入输入文件的一行
 27 # - 去除非字母字符及停止词，并将其全部转化成小写
 28 # - 在文件中找到该单词，计数器加1
 29 
 30 # 加载停止词列表
 31 f = open('../stop_words.txt')
 32 data = [f.read(1024).split(', ')] # data[0]为所有的停止词列表
 33 f.close()
 34 
 35 data.append([])    # data[1]为读入待处理的行（最多80个字符）
 36 data.append(None)  # data[2]为当前单词首字母的下标
 37 data.append(0)     # data[3]为当前字符的下标
 38 data.append(False) # data[4]为是否已完成当前单词读取的标志
 39 data.append('')    # data[5]为当前单词
 40 data.append('')    # data[6]为辅助存储器中已出现过单词列表
 41 data.append(0)     # data[7]为单词频数
 42 
 43 # 打开辅助存储器
 44 word_freqs = touchopen('word_freqs', 'rb+')
 45 # 打开输入文件
 46 f = open(sys.argv[1])
 47 # 循环并每次读取文件中的一行
 48 while True:
 49     data[1] = [f.readline()]
 50     if data[1] == ['']: # 输入文件末尾
 51         break
 52     if data[1][0][len(data[1][0])-1] != '\n': # 若该行并不以\n结尾
 53         data[1][0] = data[1][0] + '\n' # 加入\n
 54     data[2] = None
 55     data[3] = 0
 56     # 循环当前行的每一个字符
 57     for c in data[1][0]: # 在练习中尝试省略变量c
 58         if data[2] == None:
 59             if c.isalnum():
 60                 # 找到单词的开始
 61                 data[2] = data[3]
 62         else:
 63             if not c.isalnum():
 64                 # 找到单词的结尾，处理它
 65                 data[4] = False
 66                 data[5] = data[1][0][data[2]:data[3]].lower()
 67                 # 忽略长度小于2的单词和停止词
 68                 if len(data[5]) >= 2 and data[5] not in data[0]:
 69                     # 检查频数表中是否已经有该单词
 70                     while True:
 71                         data[6] = word_freqs.readline().strip()
 72                         if data[6] == '':
 73                             break; 
 74                         data[7] = int(data[6].split(',')[1])
 75                         # 单词：没有空白字符
 76                         data[6] = data[6].split(',')[0].strip()
 77                         if data[5] == data[6]:
 78                             data[7] += 1
 79                             data[4] = True
 80                             break
 81                     if not data[4]:
 82                         word_freqs.seek(0, 1) # 针对Windows
 83                         word_freqs.writelines("%20s,%04d\n" % (data[5], 1))
 84                     else:
 85                         word_freqs.seek(-26, 1)
 86                         word_freqs.writelines("%20s,%04d\n" % (data[5], data[7]))
 87                     word_freqs.seek(0,0)
 88                 # 重置
 89                 data[2] = None
 90         data[3] += 1
 91 # 输入文件处理完毕
 92 f.close()
 93 word_freqs.flush()
 94 
 95 # 第二部分
 96 # 现在需要找到出现频率最高的25个单词
 97 # 之前内存中的内容对此过程无用
 98 del data[:]
 99
100 # 使用前25个下标来标注出现频率最高的25个单词
101 data = data + [[]]*(25 - len(data))
102 data.append('') # data[25]为从文件中读取的word,freq
103 data.append(0)  # data[26]为freq
104
105 # 循环读取辅助存储器中的内容
106 while True:
107     data[25] = word_freqs.readline().strip()
108     if data[25] == '': # 文件结尾
109         break
110     data[26] = int(data[25].split(', ')[1]) # 将频数以整型存入
111     data[25] = data[25].split(',')[0].strip() # 单词
112     # 查看当前值是否比内存中单词出现的次数多
113     for i in range(25): # 在练习中尝试省略变量i
114         if data[i] == [] or data[i][1] < data[26]:
115             data.insert(i, [data[25], data[26]])
116             del data[26] # 删除最后一个元素
117             break
118             
119 for tf in data[0:25]: # 在练习中尝试省略变量tf
120     if len(tf) == 2:
121         print tf[0], ' - ', tf[1]
122 # 完工
123 word_freqs.close()

注：若对Python不熟悉，可参阅引言中对列表、列表下标和上下界的解释。

1.3　注解

这种风格的程序反映了受限的运行环境。内存的约束强制程序员在可用内存中循环使用受限的变量，使计算任务变得复杂。另外，程序中缺少标识符导致代码文字不自然通顺，取而代之的是注释和文档。这就是20世纪50年代早期编程的一切。然而，这种编程风格并没有绝迹，如今它仍被用于与硬件的直接交互以及内存优化。

未接触过此类约束的程序员对以上示例程序可能会比较陌生。这个程序无疑与Python或现代编程语言并无联系，却代表着本书的主题：编程风格因约束而生。约束通常源于外部：或许因硬件的内存有限；或许因汇编代码不支持标识符；又或许因性能糟糕，必须直接对机器进行编程。约束有时也源于内部：开发者或整个开发团队决定坚持以某种方式思考问题并进行编程，主要出于可维护性、可读性、扩展性、问题适用性的考虑以及部分开发者的过往经验等；或者类似于本书教授低级语言的情形，而不用学习新的词法。实际上，在任何编程语言中使用“往日的美好”这种低级的编程风格都是完全可行的。

在解释了此类不寻常的词频统计的实现原因之后，让我们仔细看一看代码。巨大的内存约束使待处理数据的大小不容忽视。在本例中，我们给data变量强加了只允许1024个内存单元的约束（第15行）。我们使用“内存单元”来模糊地定义简单数据，如字符或数字。对于像《傲慢与偏见》这样超过1024个字符的书，需要将文件分成若干个小块来读取处理，并且频繁地将超出主存大小的数据存入辅助存储器（一个文件）中。在编码之前，我们需要就“什么将存入主存”、“什么将存入辅存”以及“何时将内容存入辅存”（第16~23行的注释）的各种选择做粗略的计算。访问主存的速度一如既往地远远快于访问辅存的速度，所以如此考量与性能优化息息相关。

除了以上方法，仍然有许多选择可供探索，也希望你可以在这种风格约束下探索其他解决方案。示例程序分为两个部分：第一部分（第25~93行）处理输入文件，对单词进行计数，并将词频数据写入文件；第二部分（第95~123行）处理词频文件中的中间结果，找到出现频率最高的25个单词并输出。

第一部分的代码逻辑如下。

 将停止词存入主存中，大约500个字符（第30~33行）。

 将输入文件一行行读入，每行最多80个字符（第47~92行）。

 对于每一行（第57~92行），去除多余的字符，识别单词并统一转化成小写。

 从辅存中检索相应单词，并将词频写入辅存（第70~87行）。

这样处理输入文件之后，我们将注意力集中在临时文件中的词频统计上。我们需要将词频按降序排列，因此代码逻辑如下。

 在主存中保存一个最常出现的25个单词的有序列表（第101行）。

 每次从文件中读入一行，每行包括单词及其出现的频数（第105~117行）。

 若新单词的出现次数较当前有序列表中某一个单词的次数多，将其插入至合适位置并保持列表有序，同时去除列表末尾的单词（第113~117行）。

 最后，输出前25个单词及其频数（第119~121行），关闭临时文件（第123行）。

可以看到内存约束影响了使用的算法，所以必须时刻留心内存中有多少数据。

此风格第二个强加的约束是缺少标识符。该约束同样对程序影响很大，只是表现在另一个方面：可读性。没有变量，数据内存仅可以通过数字下标访问。问题中的原生概念，如单词、频率、个数、排序等，在代码中无处可寻，取而代之的是以内存下标为基础的间接表示。将原生概念引入代码的唯一方法是使用注释以解释每个内存单元中数据的意义（例如第35~41行、第100~103行等）。在阅读代码时，我们时常需要回顾之前的注释来回忆内存单元中数据的高级意义。

1.4　系统设计中的应用

如今计算机兆字节级内存盛行，这里所提及的“受限的内存”基本上只是过去模糊的回忆。然而，面对现代编程语言强调透明的内存管理，以及程序处理中不断增长的数据规模，程序员很容易失去对程序内存消耗的控制，从而导致运行时性能的下降。对不同程序风格的内存使用策略所带来的不同结果给予适当的关注，总是一件好事情。

近来，随着大数据的出现，处理小内存的复杂性成为了关注的焦点。在这种情况下，内存虽不是绝对意义上的有限，但远远小于需要处理的数据量。例如，若我们把对《傲慢与偏见》进行的词频统计应用在整个古登堡数字电子书计划上，那么显然我们不可能将所有的书同时读入内存中，也不可能将所有单词与其频数全部存在内存中。一旦内存大小无法适应数据规模，开发者必须设计出聪明的体系：使更多数据在各种情况下都能适应内存大小的数据表达方法；数据在主存和辅存轮换的方法。在这些约束下，编程仿佛重温了“往日的美好”。

说起标识符的缺失，在20世纪五六十年代，编程语言进化的一个主要目的就是消除类似示例程序中注释那样的间接表述。程序文字要能反映出问题中的原生高级概念，而不是低级的计算机概念，并且要依靠外部的文档来对应问题概念。长久以来，虽然编程语言已经提供了用户命名的抽象方法，但开发者无法适当地给代码元素、应用编程接口（Application Programming Interface，API）、整个组件命名的情况比比皆是，使得整个代码、库以及系统晦涩难懂，正如本章的示例程序。

就让这“往日的美好”时刻警醒我们，“宽裕的内存与合适的名字”是多么地美好。

1.5　发展历程

这种编程风格直接来源于第一个可实现的计算模型——图灵机。图灵机包含一个无限长、状态可修改的“纸带”（数据内存）与读取修改状态的状态机。图灵机对于计算机发展与程序设计影响深远。图灵的思想启发冯•诺伊曼设计出了第一台存储程序计算机，图灵自己也编写了“计算”机器——被称为自动计算引擎（Automatic Computing Engine，ACE）——的说明书。在那个年代，ACE比冯•诺伊曼的计算模型更为先进，只是其说明书被英国政府列为机密，并因为第二次世界大战后的政治因素，图灵的设计长期被保密，未被实施。冯•诺伊曼的架构与图灵机都引领了20世纪50年代编程语言的发展，并赋予编程以重用且变化内存状态的概念。

1.6　拓展阅读

Bashe, C., Johnson, L., Palmer, J. and Pugh, E. (1986). IMB’s Early Computers: A Technical History (History of Computing), MIT Press, Cambridge, MA.

摘要：IBM是计算机行业的早期巨头。此书讲述了IBM从机电装置生产商转变为计算机行业巨头的故事。

Carpenter, B.E. and Doran, R.W. (1977). The other Turing Machine.Computer Journal 20(3): 269–279.

摘要：就图灵关于计算机器架构的一个技术报告。该框架基于冯•诺伊曼的计算机器，但进一步引入了子程度、栈及其他概念。报告原文可在以下链接下载：http://www.npl.co.uk/ about/ history/ notable-indivisuals/turing/ace-proposal。

Turing, A. (1936). On computable numbers, with an application to the Entscheidungs problem. Proceedings of the London Mathematical Society, 2(42): 230–265. ①

摘要：最初的“图灵机”。本书推荐这篇论文不是因其在数学领域的贡献，而是因图灵机的编程模型：带有符号的纸带、可以左右移动的纸带输入/输出设备，以及纸带上符号的可复写性。

① 由人民邮电出版社出版的《图灵的秘密：他的生平、思想及论文解读》，对这篇论文进行了详尽的解读，同时还附带大量历史背景资料、图灵个人经历等内容。—— 编者注

von Neumann, J. (1945). First draft of a report on the EDVAC. Reprinted in IEEE Annals of the History of Computing, 15(4) : 27–43, 1993.

摘要：最初的“冯•诺伊曼架构”。与图灵的论文一样，推荐文中的编程模型。

1.7　词汇表

主存：通常指内存，能够被CPU直接访问。大部分存储于主存的数据并不稳定，在程序结束或电源关闭后便会消失。现在，主存是随机存取存储器（Random Access Memory，RAM），意为CPU能够快速地寻址任意一个内存空间，并不需要顺序地扫描。

辅存：与主存相对，辅存指任何一种无法被CPU直接访问的存储设备，需要通过输入/输出总线被间接地访问。辅存中的数据在电源断开后仍会存留，直至被明确地删除。在现代计算机中，硬盘和U盘是最常见的辅存设备。访问辅存的速度比主存慢几个数量级。

1.8　练习

1.1 另一种语言。保持编程风格，使用另一种编程语言实现示例程序。

1.2 不使用标识符。示例程序中仍有少量的标识符，如第57行（c）、第113行（i）和第120行（tf）。修改示例程序，去除这些标识符。

1.3 一次读入多行。示例程序每次仅读入一行，没有充分利用主存。修改示例程序，每次尽可能读入多行，但不要超过1024个内存单元的约束。选择合适的行数并证明。尝试读入多行的程序是否比原始示例程序更快，并解释结果。

1.4 不同的任务。选择引言中提出的一个任务，使用本章的风格完成编程。