导语：
本文主要介绍了关于Python怎么实现贪婪排名算法？的相关知识，希望可以帮到处于编程学习途中的小伙伴
通常，必须解析来自其他 CAD 程序生成的文本或 HTML 文件的输入是乏味的，并且通过以 Python 字典的形式提供理想的输入。 （有时用于解析输入文件的代码可能与排名算法一样大或更大）。
让我们假设每个 ISG 测试都有一个名称，并且在模拟显示设计中一组编号的功能的“覆盖范围”时运行确定的“时间”。解析后，收集到的输入数据在程序中用结果字典表示。
python学习网，大量的免费
，欢迎在线学习！
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])),
}贪婪排名算法的核心是对当前选定测试的子集进行排序：
至少用一个测试集覆盖尽可能大的范围。
第一步之后，测试集逐渐减少，同时覆盖尽可能大的范围。
对选中的测试做一个排序，这样数据集小的测试也可以选择使用
以上排序完成后，接下来可以对算法的执行时间进行优化。
当然，他需要能在很大的测试集下工作。
贪心排序算法的工作原理是先选择当前测试集中某一项的最优解，然后寻找下一项的最优解，然后进行...
如果两种以上的算法产生相同的执行结果，则执行“时间”将用于比较两种算法的优劣。
用下面的函数完成的算法：
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 行）
上面的函数有点简单，所以我花了一点时间在教程中对其进行了注释，并在运行时打印出它的作用。
函数（有指导）：
它完成同样的事情，但代码量更大，太繁冗:
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 DISCARDED\n')
return coveredsofar, ranked, costsofar, noncontributing每一块以 if tutor开始: 添加以上代码
样值输出
调用排序并打印结果的代码是：
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% 的可能覆盖率）。
本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！
内容反馈