本节书摘来自异步社区《编程珠玑(续)(修订版)》一书中的第2章,第2.1节Awk中的关联数组,作者【美】Jon Bentley,更多章节内容可以访问云栖社区“异步社区”公众号查看。
第2章 关联数组
编程珠玑(续)(修订版)
人类学家说,语言深刻地影响了世界观。一般把这个观察结果称为“Whorf假说”① ,也经常把它总结为“语言塑造了人的思想”。
跟大多数程序员一样,我使用的Algol系列的语言塑造了我的计算思维。对于像我这样的程序员来说,PL/1、C和Pascal看起来都很相似,我们不难把这样的代码翻译成COBOL或Fortran的代码。用这些语言能轻易地表达我们旧的、习以为常的思维模式。
另外一些语言则挑战了我们对于计算的看法。我们感到惊奇的是:Lisp用户们用S表达式和递归来神奇地工作,APL迷们用一组长向量的外积来为世界建模,Snobol程序员把任何问题都变成一个很大的字符串。我们这些Algol系列的程序员可能会发现,研究这些“异族文化”是痛苦的,但是这种体验一般会增长我们的见识。
本章讨论Algol传统之外的一种语言特性:关联数组(associative array)。我们熟悉的数组都用数值作下标,而关联数组则允许像count[“cat”]这样的引用。这样的数据结构出现在Snobol和Rexx(一种IBM命令解释器)这样的语言中,它允许我们用简单的程序来表达复杂的算法。这些数组与Algol相似到可以很快被理解的程度,又新到足以挑战我们思维习惯的程度。
本章将讨论Awk语言提供的关联数组。虽然Awk的大多数成分都来自Algol传统,但是关联数组和其他几个特性还是值得研究的。下面这一节介绍Awk的关联数组;后续几节描述两个重要的程序,这两个程序用大多数Algol系列的语言来写都是很麻烦的,却可以用Awk优雅地表达出来。
2.1 Awk中的关联数组
附录A中概述了Awk语言。我们将通过研究一个程序来简要复习一下这个语言,这个程序找出姓名文件中可疑的项。这个程序的每一行都是一个“模式-动作”对。对于每个输入行,如果这个输入行与左侧的一个模式匹配,则执行右侧括号中包含的动作。这个完整的Awk程序只包含3行代码:
length($1) > 10 { e++; print "long name in line", NR}
NF != 1 { e++; print "bad name count in line", NR}
END { if (e > 0) print "total errors: ", e }
第一个模式捕捉长的名字。如果第一个字段(名为$1)超过10个字符,则相应的行为是对e增1,并使用内建变量NR(记录个数或行数)打印一条警告信息。变量e统计错误个数,Awk通常将所有变量初始化为零。第二个“模式-动作”对捕捉那些没有恰好包含一个名字的行(内建变量NF统计输入行中字段的数量)。第三个动作在输入的结尾执行,用于打印错误的个数。
关联数组并不在Awk内核之中,许多Awk程序并不使用它。但这些数组很巧妙地集成到了语言之中:如同其他变量一样,数组不用被声明,它在第一次使用时自动初始化。
现在转向有关名字的第二个问题:给定包含n个名字的文件,生成全部n2个名字对。我知道一些人曾用这样的程序为他们的孩子选取名和中名。如果输入文件包含名字Billy、Bob和Willy,那么输出将引导父母为孩子选择一个更悦耳的名字,比如Billy Bob而不是Billy Willy。
这个程序使用变量n计数当前已看到的名字个数。和所有Awk变量一样,其初始值为零。第一个语句在输入的每一行上都执行,注意n在使用之前加1。
{ name[++n] = $1 }
END { for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)print name[i], name[j]}
输入文件被读取后,名字存储在name[1]到name[n]中。END动作用两层for循环打印名字对。注意,尽管该程序只使用数值下标②,但却不必事先声明name数组的大小。
程序产生许多输出,特别是在输入文件中多次出现某些名字的情况下。因此,下一个程序使用一个字符串索引的数组来清理输入文件。完整的程序如下:
{ if ( count[$1]++ == 0 ) print $1 }
一个名字第一次读取时它的count值为零,于是它被输出,并增加相应的数组元素。该名字的后续出现被读到时,其count 值变大但不做任何额外动作。程序结束后,count 的下标恰好代表了名字的集合。
这一事实让我们可以将之前的两个程序合为一个:给定一个名字文件(可能有重复的),下面的程序打印所有的名字对。
{ name[$1] = 1 }
END { for (i in name)for (j in name)print i, j}
关联数组name代表名字集合,其中所有值都是1。信息包含在数组索引中,可以用下述形式的循环来检索:
for ( i in name ) statement
该循环在所有i值上重复执行statement。作为name的下标,i恰好代表输入文件里的名字。该循环以任意的顺序列举所有的名字,名字通常是不排序的。(Awk的确为UNIX系统排序提供了一个方便的接口,但这已经超出了本章的范围。)
下一个程序将应用从托儿所转移到了厨房。购物清单
chips 3
dip 2
chips 1
cola 5
dip 1
其实应按项合并得到更简便的形式:
dip 3
cola 5
chips 4
下面的程序完成这一任务:
{ count[$1] = count[$1] + $2 }
END { for (i in count) print i, count[i] }
1.3节给出了一个程序,统计文档中每个单词出现的次数。下面的程序用Awk中的字段非常简单地定义单词为用空白分隔的字符序列。因此,字符串"Words"、"words"和"words;"是3个不同的单词。
{ for (i = 1; i <= NF; i++) count[$i]++ }
END { for (i in count) print count[i], i }
这个程序在VAX-11/750上用了40秒的CPU时间来处理本章的一份草稿中的4500个单词。出现频率最高的3个单词是“the”(出现213次)、“to”(110次)和“of”(104次)。11.1节将回到有关这个程序运行时间的问题上来。
下面这个简单的拼写检查器报告输入文件中所有不在字典文件dict中的单词。预处理使用Awk的
getline命令将字典读入到数组goodwords中:
BEGIN { while (getline <"dict") goodwords[$1] = 1 }{ for (i = 1; i <= NF; i++)if (!($i in goodwords))badwords[$i] = 1}
END { for (i in badwords) print i }
主要的处理过程收集badwords,后处理过程打印违例的词。测试
if ( $i in goodwords ) ...
当第i个字段是数组goodwords的下标时为真,而非运算符!将这一条件取反。不熟悉Awk的程序员或许用过更简单的条件测试
if ( goodwords[$i] == 0 ) ...
这一条件测试的答案是一样的,但却会产生不必要的副作用——向goodwords数组中插入一个新的零值元素。过量的元素会明显增加程序的时间和空间开销。
有这些小例子作为背景,我们将继续看两个大一点的程序。好在我们不需要研究太大的程序。
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态