《编程珠玑(续)(修订版)》—第2章2.1节Awk中的关联数组

 2023-09-05 阅读 219 评论 0

摘要:本节书摘来自异步社区《编程珠玑(续)(修订版)》一书中的第2章,第2.1节Awk中的关联数组,作者【美】Jon Bentley,更多章节内容可以访问云栖社区“异步社区”公众号查看。 第2章 关联数组编程珠玑(续)(

本节书摘来自异步社区《编程珠玑(续)(修订版)》一书中的第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数组中插入一个新的零值元素。过量的元素会明显增加程序的时间和空间开销。

有这些小例子作为背景,我们将继续看两个大一点的程序。好在我们不需要研究太大的程序。

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/1/703.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息