快捷導(dǎo)航

在Python中實(shí)現(xiàn)貪婪排名算法的教程

更新時(shí)間：2015年04月17日 11:19:59 投稿：goldensun

這篇文章主要介紹了在Python中實(shí)現(xiàn)貪婪排名算法的教程,也是對(duì)學(xué)習(xí)算法的一個(gè)很好的演示,需要的朋友可以參考下

在較早的一遍文章中，我曾經(jīng)提到過(guò)我已經(jīng)寫了一個(gè)屬于自己的排序算法，并且認(rèn)為需要通過(guò)一些代碼來(lái)重新回顧一下這個(gè)排序算法。

對(duì)于我所完成的工作，我核實(shí)并且保證微處理器的安全。對(duì)非常復(fù)雜的CPU進(jìn)行測(cè)試的一個(gè)方法就是創(chuàng)建該芯片的另一個(gè)模型，其可以用來(lái)產(chǎn)生在CPU上運(yùn)行的偽隨機(jī)指令流。這所謂的ISG(指令流產(chǎn)生器)能夠在很短的時(shí)間內(nèi)創(chuàng)建幾千（甚至幾百萬(wàn)）個(gè)這樣的測(cè)試，通過(guò)某種方式，使其可以巧妙地給出一些對(duì)將在CPU上執(zhí)行的指令流的控制或操縱。

現(xiàn)在對(duì)這些指令流進(jìn)行模擬，可以通過(guò)每一個(gè)測(cè)試實(shí)例花費(fèi)的時(shí)間獲取到CPU的那一部分被使用了（這叫做被覆蓋）的信息，并且ISG所產(chǎn)生的的過(guò)個(gè)測(cè)試可能會(huì)覆蓋CPU的同一個(gè)區(qū)域。為了增加CPU的整體覆蓋范圍，我們啟動(dòng)一個(gè)被稱作復(fù)原的行為——所有的測(cè)試都運(yùn)行，并且它們的覆蓋范圍和花費(fèi)的時(shí)間將被存儲(chǔ)起來(lái)。在這次復(fù)原的最后，您可能會(huì)有幾千個(gè)測(cè)試實(shí)例只覆蓋了CPU的某一部分。

如果你拿著這個(gè)復(fù)原測(cè)試的記過(guò)，并且對(duì)其進(jìn)行排序，你會(huì)發(fā)現(xiàn)這個(gè)測(cè)試結(jié)果的一個(gè)子集會(huì)給出它們覆蓋了CPU的所有部分。通常，上千的偽隨機(jī)測(cè)試可能會(huì)被排序，進(jìn)而產(chǎn)生一個(gè)只有幾百個(gè)測(cè)試的子列表，它們?cè)谶\(yùn)行時(shí)將會(huì)給出同樣的覆蓋范圍。接下來(lái)我們經(jīng)常會(huì)做的是，查看CPU的哪個(gè)部分沒(méi)有被覆蓋，然后通過(guò)ISG或其它方法在產(chǎn)生更多的測(cè)試，來(lái)試圖填補(bǔ)這一空白。再然后會(huì)運(yùn)行一次新的復(fù)原，并且循環(huán)得再一次進(jìn)行排序來(lái)充分使用該CPU，以達(dá)到某個(gè)覆蓋范圍目標(biāo)。

對(duì)測(cè)試進(jìn)行排名是復(fù)原流程的一個(gè)重要部分，當(dāng)其進(jìn)行地很好時(shí)你可能就會(huì)忘記它。不幸的是，有時(shí)，當(dāng)我想要對(duì)其它數(shù)據(jù)進(jìn)行排名時(shí)，CAD工具廠商所提供的常用排名算法并不適合。因此，能夠擴(kuò)展到處理成百上千個(gè)測(cè)試和覆蓋點(diǎn)才是一個(gè)排名算法的本質(zhì)。

輸入

通常情況下，我不得不從其他CAD程序產(chǎn)生的文本或HTML文件來(lái)解析我的輸入 - 這是個(gè)是單調(diào)乏味的工作，我會(huì)跳過(guò)這個(gè)乏味的工作，而通過(guò)以Python字典的形式提供理想的輸入。（有時(shí)用于解析輸入文件的代碼可以跟排名算法一樣大或著更大）。
讓我們假設(shè)每個(gè)ISG測(cè)試都有一個(gè)名稱，在確定的“時(shí)間”內(nèi)運(yùn)行，當(dāng)模擬顯示'覆蓋'設(shè)計(jì)中的一組編號(hào)的特性時(shí)。解析之后，所收集的輸入數(shù)據(jù)由程序中的結(jié)果字典來(lái)表示。

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])),
 }<span style="font-size:10pt;line-height:1.5;font-family:'sans serif', tahoma, verdana, helvetica;"></span>

貪婪排名算法的核心是對(duì)當(dāng)前選擇測(cè)試的子集進(jìn)行排序：

至少用一個(gè)測(cè)試集覆蓋盡可能大的范圍。
經(jīng)過(guò)第一個(gè)步驟，逐步減少測(cè)試集，同時(shí)覆蓋盡可能大的范圍。
給選擇的測(cè)試做出一個(gè)排序，這樣小數(shù)據(jù)集的測(cè)試也可以選擇使用
完成上述排序后，接下來(lái)就可以優(yōu)化算法的執(zhí)行時(shí)間了
當(dāng)然，他需要能在很大的測(cè)試集下工作。

貪婪排名算法的工作原理就是先選擇當(dāng)前測(cè)試集的某一項(xiàng)的最優(yōu)解，然后尋找下一項(xiàng)的最優(yōu)解，依次進(jìn)行...

如果有兩個(gè)以上的算法得出相同的執(zhí)行結(jié)果，那么將以執(zhí)行”時(shí)間“來(lái)比較兩種算法優(yōu)劣。

用下面的函數(shù)完成的算法：

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循環(huán)（第5行），下一個(gè)最好的測(cè)試會(huì)被追加到排名和測(cè)試，不會(huì) 丟棄貢獻(xiàn)的任何額外覆蓋（37-41行）

上面的函數(shù)是略顯簡(jiǎn)單，所以我花了一點(diǎn)時(shí)間用tutor來(lái)標(biāo)注，當(dāng)運(yùn)行時(shí)打印出它做的。
函數(shù)（有指導(dǎo)）：
它完成同樣的事情，但代碼量更大，太繁冗:

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開始: 添加以上代碼

樣值輸出
調(diào)用排序并打印結(jié)果的代碼是：

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))

結(jié)果包含大量東西，來(lái)自tutor并且最后跟著結(jié)果。

對(duì)這個(gè)偽隨機(jī)生成15條測(cè)試數(shù)據(jù)的測(cè)試案例，看起來(lái)只需要七條去產(chǎn)生最大的總覆蓋率。（而且如果你愿意放棄三條測(cè)試，其中每個(gè)只覆蓋了一個(gè)額外的點(diǎn)，那么15條測(cè)試中的4條就將給出92.5%的最大可能覆蓋率）。

您可能感興趣的文章: