Python怎么实现贪婪排名算法？

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

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

python学习网，大量的免费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])),
}

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

至少用一个测试集覆盖尽可能大的范围。

经过第一个步骤，逐步减少测试集，同时覆盖尽可能大的范围。

给选择的测试做出一个排序，这样小数据集的测试也可以选择使用

完成上述排序后，接下来就可以优化算法的执行时间了

当然，他需要能在很大的测试集下工作。

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

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

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

defgreedyranker(results):
results=results.copy()
ranked,coveredsofar,costsofar,round=[],set(),0,0
noncontributing=[]
whileresults:
round+=1
#Whateachtestcancontributetothepoolofwhatiscoveredsofar
contributions=[(len(cover-coveredsofar),-cost,test)
fortest,(cost,cover)insorted(results.items())]
#Greedyrankingbytakingthenextgreatestcontributor
delta_cover,benefit,test=max(contributions)
ifdelta_cover>0:
ranked.append((test,delta_cover))
cost,cover=results.pop(test)
coveredsofar.update(cover)
costsofar+=cost
fordelta_cover,benefit,testincontributions:
ifdelta_cover==0:
#thistestcannotcontributeanything
noncontributing.append((test,round))
results.pop(test)
returncoveredsofar,ranked,costsofar,noncontributing

每次while循环（第5行），下一个最好的测试会被追加到排名和测试，不会 丢弃贡献的任何额外覆盖（37-41行）

上面的函数是略显简单，所以我花了一点时间用tutor来标注，当运行时打印出它做的。

函数（有指导）：

它完成同样的事情，但代码量更大，太繁冗:

defgreedyranker(results,tutor=True):
results=results.copy()
ranked,coveredsofar,costsofar,round=[],set(),0,0
noncontributing=[]
whileresults:
round+=1
#Whateachtestcancontributetothepoolofwhatiscoveredsofar
contributions=[(len(cover-coveredsofar),-cost,test)
fortest,(cost,cover)insorted(results.items())]
iftutor:
print('\n##Round%i'%round)
print('Coveredsofar:%2ipoints:'%len(coveredsofar))
print('Rankedsofar:'+repr([tfort,dinranked]))
print('Whattheremainingtestscancontribute,largestcontributorsfirst:')
print('#DELTA,BENEFIT,TEST')
deltas=sorted(contributions,reverse=True)
fordelta_cover,benefit,testindeltas:
print('%2i,%7.2f,%s'%(delta_cover,benefit,test))
iflen(deltas)>=2anddeltas[0][0]==deltas[1][0]:
print('Note:Thistimearound,morethanonetestgivesthesame')
print('maximumdeltacontributionof%itothecoveragesofar'
%deltas[0][0])
ifdeltas[0][1]!=deltas[1][1]:
print('weorderbasedonthenextfieldofminimumcost')
print('(equivalenttomaximumnegativecost).')
else:
print('thenextfieldofminimumcostisthesameso')
print('wearbitrarilyorderbytestname.')
zeroes=[testfordelta_cover,benefit,testindeltas
ifdelta_cover==0]
ifzeroes:
print('Thefollowingtest(s)cannotcontributemoretocoverage')
print('andwillbedropped:')
print(''+','.join(zeroes))

#Greedyrankingbytakingthenextgreatestcontributor
delta_cover,benefit,test=max(contributions)
ifdelta_cover>0:
ranked.append((test,delta_cover))
cost,cover=results.pop(test)
iftutor:
print('Ranking%sinround%2igivingextracoverageof:%r'
%(test,round,sorted(cover-coveredsofar)))
coveredsofar.update(cover)
costsofar+=cost

fordelta_cover,benefit,testincontributions:
ifdelta_cover==0:
#thistestcannotcontributeanything
noncontributing.append((test,round))
results.pop(test)
iftutor:
print('\n##ALLTESTSNOWRANKEDORDISCARDED\n')
returncoveredsofar,ranked,costsofar,noncontributing

每一块以 if tutor开始: 添加以上代码

样值输出

调用排序并打印结果的代码是：

totalcoverage,ranking,totalcost,nonranked=greedyranker(results)
print('''
Atotalof%ipointswerecovered,
usingonly%ioftheinitial%itests,
andshouldtake%gtimeunitstorun.

Thetestsinorderofcoverageadded:

TESTDELTA-COVERAGE'''
%(len(totalcoverage),len(ranking),len(results),totalcost))
print('\n'.join('%6s%i'%rforrinranking))

结果包含大量东西，来自tutor并且最后跟着结果。