1999 年 4 月 24 日，斯洛文尼亚国家 Linux 用户组在卢布尔雅那大学计算机科学系举办了首届 UNIX/Linux 全国竞赛。该竞赛是与为高中生举办的第 23 届年度全国计算机科学竞赛和第五届计算节相关的活动之一，这两项活动均于 4 月下旬在卢布尔雅那大学计算机科学系举行。与已经建立的全国计算机科学竞赛的悠久传统不同，后者非常重视使用过程式编程语言容易解决的问题，而本次竞赛旨在通过 UNIX 编程环境中的“替代”工具来实现解决方案，从而最好地展现这些工具的优势。

在为本次竞赛准备练习题时，我们这些担任组委会的人员在网上广泛搜索了其他地方的类似竞赛。遗憾的是，我们一无所获。因此，我们希望向更广泛的受众提供我们自己的经验，并希望在此领域发起一些合作。在本文中，我们将介绍竞赛的练习题及其解决方案，并进行详细的解释和评论。最后，我们将总结竞赛结果，并附上一些评论和感想。

2:1. 文本频率分析

执行简单的文本频率分析。读取文本文件，并将文本中所有单词及其频率的完整列表写入标准输出。列表应按升序排列，频率最低的单词在顶部，频率最高的单词在底部。“频率”是一个数字，它告诉我们某个单词在给定文本中出现的次数。您可以假设文本文件仅包含字母和空格。

2:2. vi 编辑器

在多用户系统中，您希望阻止多个用户同时使用 vi 编辑器编辑同一文件。提出一个解决方案！将您的解决方案实现为一个脚本。评论您的解决方案的优点和缺点。您可以假设每个用户都使用命令 vi 文件名 调用编辑器。您不能依赖 vi 编辑器在编辑已打开的文件时发出警告。

2:3. 随机排序

给定文件中的行按特定标准排序。您不希望这样，并希望伪随机地洗乱这些行。提出您的洗乱算法，并在代码中实现它。注意代码的效率。“伪随机”意味着您可以使用您选择的工具中提供的随机数生成器。

2:4. IP 地址

文本文件包含对 IP 地址的多个引用。您希望将它们全部替换为完全限定域名 (FQDN)。IP 地址和相应的 FQDN 列在 /etc/hosts 文件中

193.2.1.72      nanos.arnes.si

您可以假设此文件仅包含如所示的记录。

数值 IP 值的形式为 0.0.0.0-255.255.255.255。在不牺牲太多通用性的情况下，您可以假设给定文本文件中的每个模式 0.0.0.0-999.999.999.999 都是有效的 IP 地址，并且可以在 /etc/hosts 文件中找到其对应的 FQDN。您还可以假设文本文件中的每个 IP 地址都以至少一个空格字符在两侧分隔。

您可以使用任何命令 shell 的脚本语言（例如，sh、csh、ksh、bash）或任何脚本语言，例如 sed、awk 和 perl。您还可以使用 POSIX 指定的 UNIX 系统提供的所有用户命令。您不允许使用编译语言，例如 C、C++、Pascal 或 FORTRAN。如果您不确定您计划使用的工具是否被允许，您可以咨询监督委员会的成员。监督委员会的决定是最终决定。

2:1. 文本频率分析

使用 sort 和 uniq 命令以及一些命令管道很容易解决此练习。该解决方案可以用单行代码编写

tr " " "\n" < filename | sort | uniq -c | sort -n

使用 tr，我们将文本文件中的每个空格替换为换行符，从而将其分解为每行写入一个单词的形式。由于 tr 期望来自标准输入的数据流，因此我们必须使用 < 符号将数据从文件重定向到标准输入。练习的作者为我们简化了生活，因为我们不必担心文本中的句点、逗号和其他非字母字符。来自 tr 的输出通过管道（| 符号）传输到 sort 命令的输入，sort 命令输出文本文件中所有单词的字母排序列表。我们再次将其通过管道传输到 uniq 命令的输入。在没有选项的情况下，uniq 命令消除文本中相邻行的多次出现。使用选项 -c（计数），它还会报告输入中读取的每行的出现次数。由于我们事先已经分解了文本，因此 uniq 输出频率列表。唯一剩下的任务是按频率而不是字母顺序对其进行排序，我们使用第二个 sort 命令来完成。-n 选项用于按第一个字段的数值进行排序。

解释是否太快了？如果您不熟悉管道，我们建议您尝试逐步组装完整的操作。首先，单独使用 tr 命令

tr " " "\n" < filename

现在尝试将其输出通过管道传输到 sort，并观察会发生什么！继续执行其余的管道命令。

让我们用一个例子来说明对实际文本进行频率分析。Fran Levstik 的文本 Martin Krpan 中最常用的十个单词是

61 v
65 Krpan
74 bi
74 na
107 da
121 in
127 ne
142 se
161 pa
207 je

2:2. vi 编辑器

此练习需要熟悉文件锁定的概念。给定的程序（在我们的例子中是 vi 编辑器）被重命名或移动到用户 PATH 环境变量中未包含的目录。在其位置，我们放置了一个名为 vi 的封装脚本，该脚本在被调用时会创建一个锁文件，启动编辑器并在退出时删除锁文件。锁文件是在我们正在编辑的文件所在的同一目录中创建的，而不是在 /tmp 目录中创建的，例如。这对于避免当两个不同目录中存在两个同名文件时可能引起的任何混淆是必要的。

如果两个用户同时开始编辑某个文件，则可能会出现问题。用户 A 启动脚本，脚本发现锁文件不存在并继续创建一个。在实际创建之前 - 请记住，UNIX 是一个多任务系统 - 该进程被用户 B 启动同一脚本中断。由于锁文件仍然不存在，因此脚本也决定允许用户 B 设置锁。

如果反转该过程，则可以避免该问题：首先我们创建锁文件，然后再检查我们是否成功。这听起来奇怪吗？此处提供的解决方案正是这样做的。使用 touch 命令，脚本始终尝试创建锁文件，然后根据 touch 报告的退出状态做出反应。成功退出时，touch 以零（真）退出代码退出，而失败退出时，它报告非零（假）退出代码。在其他可能的情况下，touch 也会以非零退出代码退出，但这里我们只关注一种情况。如果我们尝试 touch 属于另一个用户的我们没有写入权限的文件，touch 会报告错误并以非零退出代码退出。因此，我们必须确保在创建锁文件时，没有其他用户具有写入权限。这是使用 umask 命令完成的，如下所示：用户 (u) 是唯一被授予读取和写入 (rw) 权限的用户，而来自同一组 (g) 和所有其他 (o) 用户均未被授予任何权限。由于我们不希望 umask 命令影响我们的环境，因此我们通过将其括在括号中来限制其影响。touch 命令后面的乱码用于将 touch 产生的错误消息发送到遗忘之地。我们只对退出代码感兴趣，并且对 touch 完全安静地运行感到满意。

#!/bin/ksh
if ( umask u=rw,g=,o=; touch $1.lock >\
/dev/null 2>&1 )
then
  vi $1
  rm -f $1.lock
else
  echo "$1 is currently locked."
fi

由于它取决于 touch 退出代码，因此此处提供的解决方案无法阻止用户多次打开自己的文件。这不是练习中明确要求的，因此在此上下文中不被认为是缺陷。也没有什么可以阻止 root 打开任何人的文件。此外，采用封装脚本的解决方案无法阻止任何用户从 vi 编辑器内部读取已打开的文件。与传统的 AT&T vi 不同，许多较新的版本都内置了文件锁定功能。vim (Vi IMproved) 是 Linux 上最常见的 vi 替代品，就是其中之一。

2:3. 随机排序

随机排序显然是一个可以通过蛮力轻松完成的过程。首先，每行前面都加上一个随机数，然后根据这些随机数对文件中的行进行排序，最后删除所有前置数字，仅保留原始行及其更改后的顺序。同样，该解决方案可以用单行代码编写

awk '{ print rand(), $0 }' sorted.lst | sort -n
|
cut -d " " -f 2-

第一个命令在文件 sorted.lst 上以 awk 脚本语言执行以下语句

{ print rand(), $0 }

condition { statement }

在我们的例子中，未指定条件，这意味着对输入中的每一行执行语句。语句本身表示打印一个随机数，后跟输入中读取的行。然后将 awk 的输出通过管道传输到 sort 的输入，sort 按其第一个字段的数值对行进行排序。第一个字段是在上一步中添加的前置随机数。

最后，我们使用 cut 删除前置随机数。提供给 cut 的两个选项意味着，将空格视作字段分隔符 (-d " ") 并从第二个字段开始提取字段 (-f 2-)。因此，我们删除了第一个字段，即前置随机数。

排序使上述算法成为 N log N 算法。Durstenfeld 发明了一种更有效的随机排序算法（Comm. ACM 7, 1964, 420），它具有线性依赖性。在这里，我们为我们的目的提供了一个 Perl 实现

#!/usr/bin/perl
@line =<>; # the complete input file
                    #is read into a vector
for ($i = 0; $i <= $#line; $i++) { # for i-th line
    $rnd = $i + int(rand($#line - $i + 1));
                    # we select a random line
                    # between i and the end
    print $line [$rnd]; # print it
    $line [$rnd] = $line[$i]; # replace with i-th
}

2:4. IP 地址

此练习要求识别文本中的以下模式：一个空格，后跟一个、两个或最多三个数字、一个点、再次一个、两个或三个数字、另一个点、再次一个、两个或三个数字、又一个点、再次一个、两个或三个数字，以及最后的空格。这种模式可以用 Perl 中的 正则表达式 有效地描述为

\b\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}\b

这里 \b 表示单词边界，\. 是一个显式点（否则点在正则表达式语法中表示“任何字符”），\d{1,3} 表示一个到三个数字的序列。

该解决方案包括两个独立的任务。首先，我们必须读取 /etc/hosts 文件并构建映射表。其次，我们扫描文本文件中的 IP 地址，并使用映射表中的相应 FQDN 替换它们。我们再次提供一个 Perl 解决方案

#!/usr/bin/perl
open (HOSTS_FILE, "/etc/hosts");
while ($line = <HOSTS_FILE>) {
    chomp $line;
    ($ip, $fqdn) = split(/ +/, $line);
    $hostbyip {$ip} = $fqdn;
}
close(HOSTS_FILE);
while (<>) {
  s/\b(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})
  \b/$hostbyip{$1}/g;
  print;
}

在构建映射表 $hostbyip 时，我们使用了 Perl 的一个很好的功能，称为关联数组或哈希，它允许我们通过符号名称引用表中的元素。在这里，我们使用了写为字符串的 IP 地址（变量 $ip）。第二个任务中的地址替换是使用 s（替换）运算符实现的：s/模式/替换/g。最后的 g（全局）修饰符使替换运算符更加积极；在行中找到的第一个模式不能满足它，但它会继续扫描该行的其余部分以查找给定模式的另一个或多个出现。

实际上，域名系统很久以前就取代了 /etc/hosts 文件。对于更实际的示例，我们将不得不将读取 /etc/hosts 表替换为 gethostbyaddr 调用。修改后的程序实际上更短

#!/usr/bin/perl -p
BEGIN {
    sub gethostbyip {
    my ( $ip ) =  @_ ;
    $packaddr = pack ("C4", split (/\./, $ip) );
    ($name) = gethostbyaddr( $packaddr, 2 );
    return $name;
    }
}
s/\b(\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3})
\b/gethostbyip($1)/eg;

今年共有 13 名参赛者参加。他们有 90 分钟的时间使用纸和笔解决所有练习题。他们可以使用所有可用的文献，但无法使用计算机测试他们的解决方案。因此，委员会决定对所有展示正确思路的解决方案给予好评，即使这些解决方案在语法上不是没有错误的。在审查了所有提交的解决方案后，委员会决定向以下三名参赛者颁奖

提交的解决方案的平均质量表明，尽管 Linux 在去年受到了所有宣传，但高中生对 UNIX/Linux 编程环境中的工具并不特别熟悉。这很遗憾，因为我们认为，许多强大的脚本语言和模块化工具是 Linux 相对于其竞争对手的优势之一。

对要求参赛者填写的匿名问卷的分析也产生了一些有趣的结果。参赛者被问及他们自己的计算环境，将练习题按 1 到 5 的等级从“简单”到“困难”进行分类，并提出建议。有些人认为对脚本语言的限制过于严格。一位参赛者提出了一个有趣的回答，他认为“如果可以使用 C 或 C++”，这些练习题将很简单。

这需要评论。每种练习题都最容易用一个人熟悉的语言解决。任何同时熟悉 C 和某种脚本语言的人都可能会同意，这些练习题可以使用后者以更少的努力解决。这是故意的。无意的是，我们发现高中生几乎不接触任何脚本语言，因此不了解脚本语言的好处。例如，快速原型设计可以从现成的工具中快速轻松地完成。这是对编译语言的补充，而不是替代。如果速度确实很重要，则成功的原型通常会后跟编译版本，通常以更快的执行速度为特征。在实践中，这两种方法共存，而在我们的学校中，似乎有一种方法占据完全的主导地位。

最后但并非最不重要的一点是，本次竞赛的标题可能也值得评论。UNIX 或狭义的 Linux 表示操作系统内核。内核级练习题不是本次竞赛的一部分，并且考虑到参赛者可用的时间和资源有限，目前在此时是不可行的。诚实地说，在简短醒目的名称和冗长精确的名称之间权衡时，我们倾向于前者。谁知道呢 - 也许我们为自己创造的额外空间甚至会在以后的某个时候被证明是有用的。