Python 中的贪婪排名算法

449 查看

在较早的一遍文章中,我曾经提到过我已经写了一个属于自己的排序算法,并且认为需要通过一些代码来重新回顾一下这个排序算法。

对于我所完成的工作,我核实并且保证微处理器的安全。对非常复杂的CPU进行测试的一个方法就是创建该芯片的另一个模型,其可以用来产生在CPU上运行的伪随机指令流。这所谓的ISG(指令流产生器)能够在很短的时间内创建几千(甚至几百万)个这样的测试,通过某种方式,使其可以巧妙地给出一些对将在CPU上执行的指令流的控制或操纵。

现在对这些指令流进行模拟,可以通过每一个测试实例花费的时间获取到CPU的那一部分被使用了(这叫做被覆盖)的信息,并且ISG所产生的的过个测试可能会覆盖CPU的同一个区域。为了增加CPU的整体覆盖范围,我们启动一个被称作复原的行为——所有的测试都运行,并且它们的覆盖范围和花费的时间将被存储起来。在这次复原的最后,您可能会有几千个测试实例只覆盖了CPU的某一部分。

如果你拿着这个复原测试的记过,并且对其进行排序,你会发现这个测试结果的一个子集会给出它们覆盖了CPU的所有部分。通常,上千的伪随机测试可能会被排序,进而产生一个只有几百个测试的子列表,它们在运行时将会给出同样的覆盖范围。接下来我们经常会做的是,查看CPU的哪个部分没有被覆盖,然后通过ISG或其它方法在产生更多的测试,来试图填补这一空白。再然后会运行一次新的复原,并且循环得再一次进行排序来充分使用该CPU,以达到某个覆盖范围目标。

对测试进行排名是复原流程的一个重要部分,当其进行地很好时你可能就会忘记它。不幸的是,有时,当我想要对其它数据进行排名时,CAD工具厂商所提供的常用排名算法并不适合。因此,能够扩展到处理成百上千个测试和覆盖点才是一个排名算法的本质。

输入

通常情况下,我不得不从其他CAD程序产生的文本或HTML文件来解析我的输入 – 这是个是单调乏味的工作,我会跳过这个乏味的工作,而通过以Python字典的形式提供理想的输入。 (有时用于解析输入文件的代码可以跟排名算法一样大或着更大)。

让我们假设每个ISG测试都有一个名称,在确定的“时间”内运行,当模拟显示’覆盖’设计中的
一组编号的特性时。解析之后,所收集的输入数据由程序中的结果字典来表示。

贪婪排名算法的核心是对当前选择测试的子集进行排序:

  1. 至少用一个测试集覆盖尽可能大的范围。
  2. 经过第一个步骤,逐步减少测试集,同时覆盖尽可能大的范围。
  3. 给选择的测试做出一个排序,这样小数据集的测试也可以选择使用
  4. 完成上述排序后,接下来就可以优化算法的执行时间了
  5. 当然,他需要能在很大的测试集下工作。

贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解,然后寻找下一项的最优解,依次进行…

如果有两个以上的算法得出相同的执行结果,那么将以执行”时间“来比较两种算法优劣。

用下面的函数完成的算法:

贪婪排名算法的核心是对当前选择测试的子集进行排序:

  1. 至少用一个测试集覆盖尽可能大的范围。
  2. 经过第一个步骤,逐步减少测试集,同时覆盖尽可能大的范围。
  3. 给选择的测试做出一个排序,这样小数据集的测试也可以选择使用
  4. 完成上述排序后,接下来就可以优化算法的执行时间了
  5. 当然,他需要能在很大的测试集下工作。

贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解,然后寻找下一项的最优解,依次进行…

如果有两个以上的算法得出相同的执行结果,那么将以执行”时间“来比较两种算法优劣。

用下面的函数完成的算法: