测试集分割算法

发表于:2020-7-22 10:28  作者:肖哥shelwin   来源:测试不将就

字体: | 上一篇 | 下一篇 |我要投稿 | 推荐标签: 软件测试技术 回归测试

  在回归测试中,随着软件特性的增加和测试覆盖度的提升,测试用例数量往往呈几何级数增长。这一现象被称为"测试膨胀"或"测试爆炸"。
  "测试爆炸"造成的一个显著后果就是回归测试的执行速度越来越慢,从而延长测试反馈周期,降低软件开发和测试效率,最终拖累软件交付进度。
  加快测试速度,提升测试效率,是软件测试持续优化的主要内容之一。在实际工作中,我们可以采取许多技术手段实现这一目标,包括但不限于:删除冗余用例,Mock等待函数,选择性测试,动态优先级测试,并行测试等。
  其中,并行测试是一种效果较好的手段。所谓并行测试,就是将测试集分割为多个子集,并且让所有子集同时执行的做法。这里,根据分割粒度不同,并行测试形态各异。我们既可以按照测试套件(suite)来分割,也可以按照测试用例(case)来分割。
  不管使用哪种分割粒度,核心的分割算法是一致的。分割算法共同目标是最小化测试执行时间。基于这个目标,分割算法需要将测试集分割得尽可能均匀。这里,"均匀"的含义是测试子集各自执行时间相等。
  显然,给每个子集分配相同数量suite或case的做法不一定是最优的,因为不同suite或case的执行时间极有可能有差别。那么,有没有更好的做法呢?
  从本质上说,并行测试中的测试集分割问题与数学上的分区(Partition)问题是等价的。分区问题研究如何将一组数字划分为多个总和相等的分组。分区问题已经从理论上被证明是NP-hard问题。通俗说,对于这类问题,我们难以(在较短时间内)采用精确算法计算最优解,而只能退而求其次用近似算法计算次优解。
  针对分区问题,一种简单有效的近似算法是贪心算法。它的策略十分简单,将待分割的数组从高往低排序,依次将数组中的每个元素分配到当前总和最小的分组中。如果遇到总和相同的多个分组,就随机分配给其中任意一个。
  例如,待分配数组是[4, 7, 6, 5, 8],需要分成2个小组。将其从高往低排序,得到[8, 7, 6, 5, 4]。首先分配8,此时两个小组为空(总和都为0),因此将8随机分配,例如给小组1;然后分配7,由于小组2的元素总和0小于小组1的元素总和8,因此将7分配给小组2;接着,采用同样方式依次分配6,5,4。最终分配结果为:小组1为[8, 5],总和13;小组2为[7,6,4],总和17。
  贪心算法的Python实现为:
   def greedy_partition(data, num_groups):
  groups = [[] for i in xrange(num_groups)]
  for n in sorted(data, reverse=True):
  groups.sort(key=lambda x: sum(x))
  groups[0].append(n)
  return [sum(g) for g in groups]
  回到刚才的例子,贪心算法的结果并不是最优的。例如,将数组[8, 7, 6, 5, 4]分割为两组[8, 6]和[7, 5, 4],各自和是14和16;分割为[8, 7]和[6, 5, 4],各自和是15和15(最优解)。如果数组[8, 7, 6, 5, 4]分别表示5个测试用例的执行时间(单位秒),那么采用贪心算法,并行测试时间为17秒,高于理论最小值15秒。
  针对分区问题,除了贪心算法,常见的算法还有KK算法和动态规划算法。对于数组[8, 7, 6, 5, 4]的二分问题,KK算法的分组结果为[8, 6]和[7, 5, 4],动态规划算法的分组结果为[8, 7]和[6, 5, 4]。在这个示例中,其效果都是优于贪心算法的。KK算法和动态规划算法比较复杂,这里就不展开描述了,它们的Python实现为: https://github.com/slxiao/python-advanced/blob/
  master/python-partition/partition.py。
  那么,在实际项目中,贪心算法,KK算法和动态规划算法的效果又如何呢?以我经历的一个自动化测试项目为例。这个项目一共有97个suite,总执行时间是3494秒。97个suite的执行时间符合长尾分布,如下图所示。这里,纵轴为执行时间,单位为秒。
  三种算法的对比结果如下:
  从结果可以看出,贪心算法不仅实际效果好,而且执行速度快。动态规划算法虽然效果也好(实际上,动态规划算法是一种理论上的最优算法),但是它的执行时间很慢,是贪心算法的722倍。KK算法执行速度快,与贪心算法相差不大,但是在我们的项目中,它的效果一般,不如贪心算法。
  根据实验结果,在这个自动化测试项目的并行化中,我们最终选择了贪心算法来分割测试集。当然,测试集分割不是并行测试的全部。在算法落地的过程中,还有一些技术问题需要考虑。
  一,测试集分割之后,测试suite/case的执行顺序相比分割前,会发生变化。许多时候,测试suite/case之间存在隐性依赖(显性依赖的测试步骤应该被组合在一起,够成一个完整的case或suite)。一旦执行顺序发生改变,可能产生各种莫名其妙的失败。因此,作为前提条件,我们需要先把测试之间的隐性依赖去掉。根据经验,这个过程可能需要花费相当的时间。
  二,分割算法依赖于测试suite/case执行时间这一先验知识。这就需要我们采集和存储测试suite/case的历史执行时间。另外,如果某些suite/case的执行时间出现大幅波动,还需要我们调查背后原因,有必要的时候还需要开发预测算法来估计它们的近似执行时间。
  三,分割算法需要处理增加和删除suite/case的情况。如果有新的执行时间未知的suite/case加入进来,如何对它们进行分组?当有suite/case被删除时,如何及时调整分组算法?这些问题在实现分组算法时都需要考虑到。
  需要说明的是,本文的测试集分割算法既适用于基于共享环境的并行测试,也适用于基于独立环境的并行测试。在基于独立环境的并行测试中,测试子集各自运行于不同的测试环境;在基于共享环境的并行测试中,测试子集运行在同一测试环境。
  在实际项目中,如果条件允许,应该尽量采用基于共享环境的并行测试。这种情况下,不仅测试是并发的,而且被测软件的执行也是并发的。这种并行测试,不仅能够节省测试时间,而且能够更好测试被测软件的并发性能。

       本文内容不用于商业目的,如涉及知识产权问题,请权利人联系博为峰小编(021-64471599-8017),我们将立即处理

评 论

论坛新帖

顶部 底部


建议使用IE 6.0以上浏览器,800×600以上分辨率,法律顾问:上海瀛东律师事务所 张楠律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2020, 沪ICP备05003035号
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪公网安备 31010102002173号

51Testing官方微信

51Testing官方微博

扫一扫 测试知识全知道