Python 中的贪婪排名算法
在较早的一遍文章中，我曾经提到过我已经写了一个属于自己的排序算法，并且认为需要通过一些代码来重新回顾一下这个排序算法。
对于我所完成的工作，我核实并且保证微处理器的安全。对非常复杂的CPU进行测试的一个方法就是创建该芯片的另一个模型，其可以用来产生在CPU上运行的伪随机指令流。这所谓的ISG(指令流产生器)能够在很短的时间内创建几千（甚至几百万）个这样的测试，通过某种方式，使其可以巧妙地给出一些对将在CPU上执行的指令流的控制或操纵。
现在对这些指令流进行模拟，可以通过每一个测试实例花费的时间获取到CPU的那一部分被使用了（这叫做被覆盖）的信息，并且ISG所产生的的过个测试可能会覆盖CPU的同一个区域。为了增加CPU的整体覆盖范围，我们启动一个被称作复原的行为——所有的测试都运行，并且它们的覆盖范围和花费的时间将被存储起来。在这次复原的最后，您可能会有几千个测试实例只覆盖了CPU的某一部分。
如果你拿着这个复原测试的记过，并且对其进行排序，你会发现这个测试结果的一个子集会给出它们覆盖了CPU的所有部分。通常，上千的伪随机测试可能会被排序，进而产生一个只有几百个测试的子列表，它们在运行时将会给出同样的覆盖范围。接下来我们经常会做的是，查看CPU的哪个部分没有被覆盖，然后通过ISG或其它方法在产生更多的测试，来试图填补这一空白。再然后会运行一次新的复原，并且循环得再一次进行排序来充分使用该CPU，以达到某个覆盖范围目标。
对测试进行排名是复原流程的一个重要部分，当其进行地很好时你可能就会忘记它。不幸的是，有时，当我想要对其它数据进行排名时，CAD工具厂商所提供的常用排名算法并不适合。因此，能够扩展到处理成百上千个测试和覆盖点才是一个排名算法的本质。
输入
通常情况下，我不得不从其他CAD程序产生的文本或HTML文件来解析我的输入 – 这是个是单调乏味的工作，我会跳过这个乏味的工作，而通过以Python字典的形式提供理想的输入。 （有时用于解析输入文件的代码可以跟排名算法一样大或着更大）。
让我们假设每个ISG测试都有一个名称，在确定的“时间”内运行，当模拟显示’覆盖’设计中的
一组编号的特性时。解析之后，所收集的输入数据由程序中的结果字典来表示。
| 123456789101112131415161718 | results = {# \’TEST\’: ( TIME, set([COVERED_POINT …])), \’test_00\’: ( 2.08, set([2, 3, 5, 11, 12, 16, 19, 23, 25, 26, 29, 36, 38, 40])), \’test_01\’: ( 58.04, set([0, 10, 13, 15, 17, 19, 20, 22, 27, 30, 31, 33, 34])), \’test_02\’: ( 34.82, set([3, 4, 6, 12, 15, 21, 23, 25, 26, 33, 34, 40])), \’test_03\’: ( 32.74, set([4, 5, 10, 16, 21, 22, 26, 39])), \’test_04\’: (100.00, set([0, 1, 4, 6, 7, 8, 9, 11, 12, 18, 26, 27, 31, 36])), \’test_05\’: ( 4.46, set([1, 2, 6, 11, 14, 16, 17, 21, 22, 23, 30, 31])), \’test_06\’: ( 69.57, set([10, 11, 15, 17, 19, 22, 26, 27, 30, 32, 38])), \’test_07\’: ( 85.71, set([0, 2, 4, 5, 9, 10, 14, 17, 24, 34, 36, 39])), \’test_08\’: ( 5.73, set([0, 3, 8, 9, 13, 19, 23, 25, 28, 36, 38])), \’test_09\’: ( 15.55, set([7, 15, 17, 25, 26, 30, 31, 33, 36, 38, 39])), \’test_10\’: ( 12.05, set([0, 4, 13, 14, 15, 24, 31, 35, 39])), \’test_11\’: ( 52.23, set([0, 3, 6, 10, 11, 13, 23, 34, 40])), \’test_12\’: ( 26.79, set([0, 1, 4, 5, 7, 8, 10, 12, 13, 31, 32, 40])), \’test_13\’: ( 16.07, set([2, 6, 9, 11, 13, 15, 17, 18, 34])), \’test_14\’: ( 40.62, set([1, 2, 8, 15, 16, 19, 22, 26, 29, 31, 33, 34, 38])), } |
贪婪排名算法的核心是对当前选择测试的子集进行排序：
- 至少用一个测试集覆盖尽可能大的范围。
- 经过第一个步骤，逐步减少测试集，同时覆盖尽可能大的范围。
- 给选择的测试做出一个排序，这样小数据集的测试也可以选择使用
- 完成上述排序后，接下来就可以优化算法的执行时间了
- 当然，他需要能在很大的测试集下工作。
贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解，然后寻找下一项的最优解，依次进行…
如果有两个以上的算法得出相同的执行结果，那么将以执行”时间“来比较两种算法优劣。
用下面的函数完成的算法：
贪婪排名算法的核心是对当前选择测试的子集进行排序：
- 至少用一个测试集覆盖尽可能大的范围。
- 经过第一个步骤，逐步减少测试集，同时覆盖尽可能大的范围。
- 给选择的测试做出一个排序，这样小数据集的测试也可以选择使用
- 完成上述排序后，接下来就可以优化算法的执行时间了
- 当然，他需要能在很大的测试集下工作。
贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解，然后寻找下一项的最优解，依次进行…
如果有两个以上的算法得出相同的执行结果，那么将以执行”时间“来比较两种算法优劣。
用下面的函数完成的算法：
| 12345678910111213141516171819202122 | def greedyranker(results): results = results.copy() ranked, coveredsofar, costsofar, round = [], set(), 0, 0 noncontributing = [] while results: round += 1 # What each test can contribute to the pool of what is covered so far contributions ayon-h\”> = [(len(cover – coveredsofar), –cost, test) for test, (cost, cover) in sorted(results.items()) ] # Greedy ranking by taking the next greatest contributor delta_cover, benefit, test = max( contributions ) if delta_cover > 0: |