# 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])),
}```

1. 至少用一个测试集覆盖尽可能大的范围。
2. 经过第一个步骤，逐步减少测试集，同时覆盖尽可能大的范围。
3. 给选择的测试做出一个排序，这样小数据集的测试也可以选择使用
4. 完成上述排序后，接下来就可以优化算法的执行时间了
5. 当然，他需要能在很大的测试集下工作。

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

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

#### 函数（有指导）：

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

### 样值输出

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

## Round 1
Covered so far:  0 points:
Ranked so far: []
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
14,      -2.08,    test_00
14,    -100.00,    test_04
13,     -40.62,    test_14
13,     -58.04,    test_01
12,      -4.46,    test_05
12,     -26.79,    test_12
12,     -34.82,    test_02
12,     -85.71,    test_07
11,      -5.73,    test_08
11,     -15.55,    test_09
11,     -69.57,    test_06
9,     -12.05,    test_10
9,     -16.07,    test_13
9,     -52.23,    test_11
8,     -32.74,    test_03
Note: This time around, more than one test gives the same
maximum delta contribution of 14 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
Ranking test_00 in round  1 giving extra coverage of: [2, 3, 5, 11, 12, 16, 19, 23, 25, 26, 29, 36, 38, 40]

## Round 2
Covered so far: 14 points:
Ranked so far: ['test_00']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
12,     -58.04,    test_01
10,    -100.00,    test_04
9,     -12.05,    test_10
9,     -26.79,    test_12
9,     -85.71,    test_07
8,      -4.46,    test_05
7,     -15.55,    test_09
7,     -16.07,    test_13
7,     -40.62,    test_14
7,     -69.57,    test_06
6,     -34.82,    test_02
5,      -5.73,    test_08
5,     -32.74,    test_03
5,     -52.23,    test_11
Ranking test_01 in round  2 giving extra coverage of: [0, 10, 13, 15, 17, 20, 22, 27, 30, 31, 33, 34]

## Round 3
Covered so far: 26 points:
Ranked so far: ['test_00', 'test_01']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
7,    -100.00,    test_04
5,     -12.05,    test_10
5,     -26.79,    test_12
5,     -85.71,    test_07
4,      -4.46,    test_05
3,      -5.73,    test_08
3,     -16.07,    test_13
3,     -32.74,    test_03
3,     -34.82,    test_02
2,     -15.55,    test_09
2,     -40.62,    test_14
1,     -52.23,    test_11
1,     -69.57,    test_06
Ranking test_04 in round  3 giving extra coverage of: [1, 4, 6, 7, 8, 9, 18]

## Round 4
Covered so far: 33 points:
Ranked so far: ['test_00', 'test_01', 'test_04']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
4,     -12.05,    test_10
3,     -85.71,    test_07
2,      -4.46,    test_05
2,     -32.74,    test_03
1,      -5.73,    test_08
1,     -15.55,    test_09
1,     -26.79,    test_12
1,     -34.82,    test_02
1,     -69.57,    test_06
0,     -16.07,    test_13
0,     -40.62,    test_14
0,     -52.23,    test_11
The following test(s) cannot contribute more to coverage
and will be dropped:
test_13, test_14, test_11
Ranking test_10 in round  4 giving extra coverage of: [14, 24, 35, 39]

## Round 5
Covered so far: 37 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1,      -4.46,    test_05
1,      -5.73,    test_08
1,     -26.79,    test_12
1,     -32.74,    test_03
1,     -34.82,    test_02
1,     -69.57,    test_06
0,     -15.55,    test_09
0,     -85.71,    test_07
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
The following test(s) cannot contribute more to coverage
and will be dropped:
test_09, test_07
Ranking test_05 in round  5 giving extra coverage of: [21]

## Round 6
Covered so far: 38 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1,      -5.73,    test_08
1,     -26.79,    test_12
1,     -69.57,    test_06
0,     -32.74,    test_03
0,     -34.82,    test_02
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
The following test(s) cannot contribute more to coverage
and will be dropped:
test_03, test_02
Ranking test_08 in round  6 giving extra coverage of: [28]

## Round 7
Covered so far: 39 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05', 'test_08']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
1,     -26.79,    test_12
1,     -69.57,    test_06
Note: This time around, more than one test gives the same
maximum delta contribution of 1 to the coverage so far
we order based on the next field of minimum cost
(equivalent to maximum negative cost).
Ranking test_12 in round  7 giving extra coverage of: [32]

## Round 8
Covered so far: 40 points:
Ranked so far: ['test_00', 'test_01', 'test_04', 'test_10', 'test_05', 'test_08', 'test_12']
What the remaining tests can contribute, largest contributors first:
# DELTA, BENEFIT, TEST
0,     -69.57,    test_06
The following test(s) cannot contribute more to coverage
and will be dropped:
test_06

## ALL TESTS NOW RANKED OR DISCARDED

A total of 40 points were covered,
using only 7 of the initial 15 tests,
and should take 209.15 time units to run.

The tests in order of coverage added:

TEST  DELTA-COVERAGE
test_00  14
test_01  12
test_04  7
test_10  4
test_05  1
test_08  1
test_12  1