首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》Linux基准测试解决方案

关灯直达底部

对于C测试用例,我们开发了一个基准测试库。本节中,我们简单地描述一下计时代码的核心思想,并告诉感兴趣的读者源代码所在的代码库。

这个库主要是用于测试排序程序。计时的API也要负责对命令行参数进行解析:

计时库假设问题的规模是由-n这个参数设定的。为了产生可复用的实验,随机值的种子可以通过-s来设定。一个测试用例需要包含以下函数:

void problemUsage

计时库会解析计时参数,然后剩余的参数会传递给prepareInput函数。

void prepareInput(int size,int argc,char**argv)

这个函数和解决的问题相关,它负责构建输入集合。这个函数不能直接地通过形式参数传递执行,而是需要使用测试用例中的静态变量。

void postInputProcessing

如果在问题解决之后需要做一些验证和后续处理,那么就在这里写一些代码。

void execute

这个方法包含了功能代码。这里永远只会有一个方法调用。当这个方法为空时,总开销(在高端计算机上)平均是0.002毫秒,这个值被认为对最后的结果没有影响。

测试用例如例A-2所示。

例A-2:n个数的加法

每次实验都将会执行一次这些函数,所以我们需要写一个shell脚本,在不同数据上多次执行程序。每次测试时,我们都需要写一个配置文件。例A-3就是第4章中基于值排序算法的配置文件config.rc。

例A-3:比较排序算法的配置文件样例

这个配置文件声明了将会执行三个快速排序的变种和一个插入排序。这次测试的数据规模n从1~16 384,n每次增加一倍。对于特定的数据规模,将会执行10次实验,最好和最坏的结果将被抛弃。然后输出剩下8次实验结果的平均值(和标准方差)。

例A-4:compare.sh基准测试脚本

compare.sh脚本使用一个C程序eval计算平均值和标准方差,这个程序使用了本章开头的一些方法。例A-5是一个管理脚本suiteRun.sh,这个脚本加载配置文件,然后根据配置文件重复执行compare.sh脚本。

例A-5:suiteRun.sh基准测试脚本