Python 中的贪婪排名算法，python排名算法, 对于我所完成的工作，我
Python 中的贪婪排名算法，python排名算法, 对于我所完成的工作，我
在较早的一遍文章中，我曾经提到过我已经写了一个属于自己的排序算法，并且认为需要通过一些代码来重新回顾一下这个排序算法。
对于我所完成的工作，我核实并且保证微处理器的安全。对非常复杂的CPU进行测试的一个方法就是创建该芯片的另一个模型，其可以用来产生在CPU上运行的伪随机指令流。这所谓的ISG(指令流产生器)能够在很短的时间内创建几千（甚至几百万）个这样的测试，通过某种方式，使其可以巧妙地给出一些对将在CPU上执行的指令流的控制或操纵。
现在对这些指令流进行模拟，可以通过每一个测试实例花费的时间获取到CPU的那一部分被使用了（这叫做被覆盖）的信息，并且ISG所产生的的过个测试可能会覆盖CPU的同一个区域。为了增加CPU的整体覆盖范围，我们启动一个被称作复原的行为——所有的测试都运行，并且它们的覆盖范围和花费的时间将被存储起来。在这次复原的最后，您可能会有几千个测试实例只覆盖了CPU的某一部分。
如果你拿着这个复原测试的记过，并且对其进行排序，你会发现这个测试结果的一个子集会给出它们覆盖了CPU的所有部分。通常，上千的伪随机测试可能会被排序，进而产生一个只有几百个测试的子列表，它们在运行时将会给出同样的覆盖范围。接下来我们经常会做的是，查看CPU的哪个部分没有被覆盖，然后通过ISG或其它方法在产生更多的测试，来试图填补这一空白。再然后会运行一次新的复原，并且循环得再一次进行排序来充分使用该CPU，以达到某个覆盖范围目标。
对测试进行排名是复原流程的一个重要部分，当其进行地很好时你可能就会忘记它。不幸的是，有时，当我想要对其它数据进行排名时，CAD工具厂商所提供的常用排名算法并不适合。因此，能够扩展到处理成百上千个测试和覆盖点才是一个排名算法的本质。
输入
通常情况下，我不得不从其他CAD程序产生的文本或HTML文件来解析我的输入 – 这是个是单调乏味的工作，我会跳过这个乏味的工作，而通过以Python字典的形式提供理想的输入。 （有时用于解析输入文件的代码可以跟排名算法一样大或着更大）。
让我们假设每个ISG测试都有一个名称，在确定的“时间”内运行，当模拟显示’覆盖’设计中的
一组编号的特性时。解析之后，所收集的输入数据由程序中的结果字典来表示。
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])),
}
贪婪排名算法的核心是对当前选择测试的子集进行排序：
- 至少用一个测试集覆盖尽可能大的范围。
- 经过第一个步骤，逐步减少测试集，同时覆盖尽可能大的范围。
- 给选择的测试做出一个排序，这样小数据集的测试也可以选择使用
- 完成上述排序后，接下来就可以优化算法的执行时间了
- 当然，他需要能在很大的测试集下工作。
贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解，然后寻找下一项的最优解，依次进行…
如果有两个以上的算法得出相同的执行结果，那么将以执行”时间“来比较两种算法优劣。
用下面的函数完成的算法：
Python
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 = [(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:
ranked.append((test, delta_cover))
cost, cover = results.pop(test)
coveredsofar.update(cover)
costsofar += cost
for delta_cover, benefit, test in contributions:
if delta_cover == 0:
# this test cannot contribute anything
noncontributing.append( (test, round) )
results.pop(test)
return coveredsofar, ranked, costsofar, noncontributing
每次while循环（第5行），下一个最好的测试会被追加到排名和测试，不会
丢弃贡献的任何额外覆盖（37-41行）
上面的函数是略显简单，所以我花了一点时间用tutor来标注，当运行时打印出它做的。
函数（有指导）：
它完成同样的事情，但代码量更大，太繁冗:
def greedyranker(results, tutor=True):
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 = [(len(cover - coveredsofar), -cost, test)
for test, (cost, cover) in sorted(results.items()) ]
if tutor:
print('n## Round %i' % round)
print(' Covered so far: %2i points: ' % len(coveredsofar))
print(' Ranked so far: ' + repr([t for t, d in ranked]))
print(' What the remaining tests can contribute, largest contributors first:')
print(' # DELTA, BENEFIT, TEST')
deltas = sorted(contributions, reverse=True)
for delta_cover, benefit, test in deltas:
print(' %2i, %7.2f, %s' % (delta_cover, benefit, test))
if len(deltas)>=2 and deltas[0][0] == deltas[1][0]:
print(' Note: This time around, more than one test gives the same')
print(' maximum delta contribution of %i to the coverage so far'
% deltas[0][0])
if deltas[0][1] != deltas[1][1]:
print(' we order based on the next field of minimum cost')
print(' (equivalent to maximum negative cost).')
else:
print(' the next field of minimum cost is the same so')
print(' we arbitrarily order by test name.')
zeroes = [test for delta_cover, benefit, test in deltas
if delta_cover == 0]
if zeroes:
print(' The following test(s) cannot contribute more to coverage')
print(' and will be dropped:')
print(' ' + ', '.join(zeroes))
# Greedy ranking by taking the next greatest contributor
delta_cover, benefit, test = max( contributions )
if delta_cover > 0:
ranked.append((test, delta_cover))
cost, cover = results.pop(test)
if tutor:
print(' Ranking %s in round %2i giving extra coverage of: %r'
% (test, round, sorted(cover - coveredsofar)))
coveredsofar.update(cover)
costsofar += cost
for delta_cover, benefit, test in contributions:
if delta_cover == 0:
# this test cannot contribute anything
noncontributing.append( (test, round) )
results.pop(test)
if tutor:
print('n## ALL TESTS NOW RANKED OR DISCARDEDn')
return coveredsofar, ranked, costsofar, noncontributing
每一块以
if tutor开始: 添加以上代码
样值输出
调用排序并打印结果的代码是：
Python
totalcoverage, ranking, totalcost, nonranked = greedyranker(results)
print('''
A total of %i points were covered,
using only %i of the initial %i tests,
and should take %g time units to run.
The tests in order of coverage added:
TEST DELTA-COVERAGE'''
% (len(totalcoverage), len(ranking), len(results), totalcost))
print('n'.join(' %6s %i' % r for r in ranking))
结果包含大量东西，来自tutor并且最后跟着结果。
对这个伪随机生成15条测试数据的测试案例，看起来只需要七条去产生最大的总覆盖率。（而且如果你愿意放弃三条测试，其中每个只覆盖了一个额外的点，那么15条测试中的4条就将给出92.5%的最大可能覆盖率）。
## Round 1
Covered so far: 0 points:
Ranked so far: []
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
14, -2.08, test_00
14, -100.00, test_04
13, -40.62, test_14
13, -58.04, test_01
12, -4.46, test_05
12, -26.79, test_12
12, -34.82, test_02
12, -85.71, test_07
11, -5.73, test_08
11, -15.55, test_09
11, -69.57, test_06
9, -12.05, test_10
9, -16.07, test_13
9, -52.23, test_11
8, -32.74, test_03
Note: This time around, more than one test gives the same
maximum delta contribution of 14 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
Ranking test_00 in round 1 giving extra coverage of: [2, 3, 5, 11, 12, 16, 19, 23, 25, 26, 29, 36, 38, 40]
## Round 2
Covered so far: 14 points:
Ranked so far: ['test_00']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
12, -58.04, test_01
10, -100.00, test_04
9, -12.05, test_10
9, -26.79, test_12
9, -85.71, test_07
8, -4.46, test_05
7, -15.55, test_09
7, -16.07, test_13
7, -40.62, test_14
7, -69.57, test_06
6, -34.82, test_02
5, -5.73, test_08
5, -32.74, test_03
5, -52.23, test_11
Ranking test_01 in round 2 giving extra coverage of: [0, 10, 13, 15, 17, 20, 22, 27, 30, 31, 33, 34]
## Round 3
Covered so far: 26 points:
Ranked so far: ['test_00', 'test_01']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
7, -100.00, test_04
5, -12.05, test_10
5, -26.79, test_12
5, -85.71, test_07
4, -4.46, test_05
3, -5.73, test_08
3, -16.07, test_13
3, -32.74, test_03
3, -34.82, test_02
2, -15.55, test_09
2, -40.62, test_14
1, -52.23, test_11
1, -69.57, test_06
Ranking test_04 in round 3 giving extra coverage of: [1, 4, 6, 7, 8, 9, 18]
## Round 4
Covered so far: 33 points:
Ranked so far: ['test_00', 'test_01', 'test_04']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
4, -12.05, test_10
3, -85.71, test_07
2, -4.46, test_05
2, -32.74, test_03
1, -5.73, test_08
1, -15.55, test_09
1, -26.79, test_12
1, -34.82, test_02
1, -69.57, test_06
0, -16.07, test_13
0, -40.62, test_14
0, -52.23, test_11
The following test(s) cannot contribute more to coverage
and will be dropped:
test_13, test_14, test_11
Ranking test_10 in round 4 giving extra coverage of: [14, 24, 35, 39]
## Round 5
Covered so far: 37 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1, -4.46, test_05
1, -5.73, test_08
1, -26.79, test_12
1, -32.74, test_03
1, -34.82, test_02
1, -69.57, test_06
0, -15.55, test_09
0, -85.71, test_07
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
The following test(s) cannot contribute more to coverage
and will be dropped:
test_09, test_07
Ranking test_05 in round 5 giving extra coverage of: [21]
## Round 6
Covered so far: 38 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1, -5.73, test_08
1, -26.79, test_12
1, -69.57, test_06
0, -32.74, test_03
0, -34.82, test_02
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
The following test(s) cannot contribute more to coverage
and will be dropped:
test_03, test_02
Ranking test_08 in round 6 giving extra coverage of: [28]
## Round 7
Covered so far: 39 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05', 'test_08']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1, -26.79, test_12
1, -69.57, test_06
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
Ranking test_12 in round 7 giving extra coverage of: [32]
## Round 8
Covered so far: 40 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05', 'test_08', 'test_12']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
0, -69.57, test_06
The following test(s) cannot contribute more to coverage
and will be dropped:
test_06
## ALL TESTS NOW RANKED OR DISCARDED
A total of 40 points were covered,
using only 7 of the initial 15 tests,
and should take 209.15 time units to run.
The tests in order of coverage added:
TEST DELTA-COVERAGE
test_00 14
test_01 12
test_04 7
test_10 4
test_05 1
test_08 1
test_12 1
下一个会是什么
已经存在有一种新的
统一覆盖互通性标准 (Unified Coverage Interoperability Standard)以供数据库理想的存储测试覆盖率数据，贪婪排名应该被挂起到 UCIS DB，以便通过它的C-接口获得输入数据，或者也可能是替代解析文本文件的XML输出。
相关内容
- Python 基于协同过滤的推荐，Python协同过滤,利用这些分
- Python验证码识别处理实例，python验证码实例,(就上面的
- Python中如何写控制台进度条的整理，python控制台,分享给
- 随机迷宫生成算法，迷宫算法,游戏地址和对应的开源项
- Python实现同时兼容老版和新版Socket协议的一个简单Web
- 使用python扫描本地音乐并下载歌词，python扫描, 先简单
- 一些简单的Python测试题，简单Python测试题,未经作者许可
- Python实现控制台中的进度条，python控制台, 我之前一直
- Python 标准库 urllib2 的使用细节，pythonurllib2,这里总结了
- 教你用Python创建瀑布图，Python创建瀑布图,未经许可，禁
评论关闭