怎么实现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])), }
贪婪排名算法的核心是对当前选择测试的子集进行排序:
至少用一个测试集覆盖尽可能大的范围。
经过第一个步骤,逐步减少测试集,同时覆盖尽可能大的范围。
给选择的测试做出一个排序,这样小数据集的测试也可以选择使用
完成上述排序后,接下来就可以优化算法的执行时间了
当然,他需要能在很大的测试集下工作。
贪婪排名算法的工作原理就是先选择当前测试集的某一项的最优解,然后寻找下一项的最优解,依次进行...
如果有两个以上的算法得出相同的执行结果,那么将以执行”时间“来比较两种算法优劣。
用下面的函数完成的算法:
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 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%的最大可能覆盖率)。
看完上述内容,你们掌握怎么实现Python贪婪排名算法的方法了吗?如果还想学到更多技能或想了解更多相关内容,欢迎关注亿速云行业资讯频道,感谢各位的阅读!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。