在較早的一遍文章中，我曾經提到過我已經寫了一個屬于自己的排序算法，并且認為需要通過一些代碼來重新回顧一下這個排序算法。
對于我所完成的工作，我核實并且保證微處理器的安全。對非常復雜的CPU進行測試的一個方法就是創建該芯片的另一個模型，其可以用來產生在CPU上運行的偽隨機指令流。這所謂的ISG(指令流產生器)能夠在很短的時間內創建幾千（甚至幾百萬）個這樣的測試，通過某種方式，使其可以巧妙地給出一些對將在CPU上執行的指令流的控制或操縱。
現在對這些指令流進行模擬，可以通過每一個測試實例花費的時間獲取到CPU的那一部分被使用了（這叫做被覆蓋）的信息，并且ISG所產生的的過個測試可能會覆蓋CPU的同一個區域。為了增加CPU的整體覆蓋范圍，我們啟動一個被稱作復原的行為——所有的測試都運行，并且它們的覆蓋范圍和花費的時間將被存儲起來。在這次復原的最后，您可能會有幾千個測試實例只覆蓋了CPU的某一部分。
如果你拿著這個復原測試的記過，并且對其進行排序，你會發現這個測試結果的一個子集會給出它們覆蓋了CPU的所有部分。通常，上千的偽隨機測試可能會被排序，進而產生一個只有幾百個測試的子列表，它們在運行時將會給出同樣的覆蓋范圍。接下來我們經常會做的是，查看CPU的哪個部分沒有被覆蓋，然后通過ISG或其它方法在產生更多的測試，來試圖填補這一空白。再然后會運行一次新的復原，并且循環得再一次進行排序來充分使用該CPU，以達到某個覆蓋范圍目標。
對測試進行排名是復原流程的一個重要部分，當其進行地很好時你可能就會忘記它。不幸的是，有時，當我想要對其它數據進行排名時，CAD工具廠商所提供的常用排名算法并不適合。因此，能夠擴展到處理成百上千個測試和覆蓋點才是一個排名算法的本質。
輸入
通常情況下，我不得不從其他CAD程序產生的文本或HTML文件來解析我的輸入 - 這是個是單調乏味的工作，我會跳過這個乏味的工作，而通過以Python字典的形式提供理想的輸入。 （有時用于解析輸入文件的代碼可以跟排名算法一樣大或著更大）。
讓我們假設每個ISG測試都有一個名稱，在確定的“時間”內運行，當模擬顯示'覆蓋'設計中的 一組編號的特性時。解析之后，所收集的輸入數據由程序中的結果字典來表示。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
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> |
貪婪排名算法的核心是對當前選擇測試的子集進行排序：
- 至少用一個測試集覆蓋盡可能大的范圍。
- 經過第一個步驟，逐步減少測試集，同時覆蓋盡可能大的范圍。
- 給選擇的測試做出一個排序，這樣小數據集的測試也可以選擇使用
- 完成上述排序后，接下來就可以優化算法的執行時間了
- 當然，他需要能在很大的測試集下工作。
貪婪排名算法的工作原理就是先選擇當前測試集的某一項的最優解，然后尋找下一項的最優解，依次進行...
如果有兩個以上的算法得出相同的執行結果，那么將以執行”時間“來比較兩種算法優劣。
用下面的函數完成的算法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
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來標注，當運行時打印出它做的。
函數（有指導）：
它完成同樣的事情，但代碼量更大，太繁冗:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
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開始: 添加以上代碼
樣值輸出
調用排序并打印結果的代碼是：
|
1
2
3
4
5
6
7
8
9
10
11
|
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%的最大可能覆蓋率）。
