需求解决列区间 [b,e) 中的列 的每个大小需求 — 即符合 b <= c < e 的所有 c— 将得到其总和至少为某个值的一组大小。需求 r 用以下公式表示：
图 7. 列大小需求 我想找到满足需求不等式的 “最小” 大小（Si）。这实际上是一个线性编程问题。这种情况比一般的问题更特殊，因为：
- 所有因子就是 0 或 1。
- 所有为 1 的因子在一个连续的变量范围中。
- 我们只对整数解感兴趣。
由于这些特殊情况，最小解可能不是 惟一的，所以我还要直观地衡量这个解。
我将简要描述可以提供合理解决方法的 req.Manager 类功能。由于这不是本文的重点，而且它的解决方法是次优的，这里不作详述。
这个类在一个单独的 req.py 模块中，该模块独立于 GTK+。该模块有一个内部测试，该测试使用 Python 的 if __name__ == '__main__': 结构。
下面是解决方法测试的一些例子。每个例子有一个给定的三元组 (Bi, Ei, Si)，这意味着要寻找一组大小，并应满足 [Bi, Ei) 的每个子区间加起来至少为 Si。
清单 16. req.Manager 解决方法示例1
2
3
4
5
6
7
8
9
10
11
| python req.py 0 1 20 1 2 30
Solution: [20, 30]
python req.py 0 2 10 1 3 5
Solution: [5, 5, 1]
python req.py 0 2 100 1 3 50
Solution: [46, 54, 6]
python req.py 0 2 100 1 3 50 2 3 20
Solution: [49, 51, 21]
|
向 req.Manager 添加需求 下面是 req.Manager 类的构造函数，其中包含添加需求的方法。
清单 17. req.ManageraddRangeReq 方法1
2
3
4
5
6
7
| class Manager:
def __init__(self):
self.rangeReqs = []
self.reqs = None
def addRangeReq(self, rangeReq):
self.rangeReqs += [rangeReq]
|
在这里，rangeReq 是以下类的一个对象：
清单 18. req.RangeSize1
2
3
4
5
| class RangeSize:
def __init__(self, be=(0,1), sz=1):
self.begin = be[0]
self.end = be[1]
self.size = sz
|
通过启发式方法解决 最佳解决方案需要线性编程技术，而且所需的代码更少。
清单 19. req.Manager.solve1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def solve(self):
n = self.nSegments()
m = len(self.rangeReqs)
self.reqs = n * [0]
self.rangeReqs.sort()
# Satisfy single segment requirements
dumSingle = RangeSize((n, n+1), 1)
endSingleIndex = bisect.bisect_right(self.rangeReqs, dumSingle)
for rr in self.rangeReqs[ : endSingleIndex]:
curr = self.reqs[rr.begin]
needMore = rr.size - curr
self.reqs[rr.begin] += needMore
bigRangeReqs = self.rangeReqs[endSingleIndex:] # non-single ranges
self.partialSatisfy(bigRangeReqs, 1, 2) # half
self.partialSatisfy(bigRangeReqs, 1, 2) # half
self.partialSatisfy(bigRangeReqs, 1, 1) # complete
return self.reqs
|
上面的清单 19 包括一个 solve() 方法，并采用一种启发式方法，该方法由以下步骤组成：
- 对需求排序。
- 满足 [b,e) 区间内 b+1=e 条件的单个元素需求。
- 对于每个未被满足的需求 r，加上 r 的未满足大小的一半（在 r 区间元素中平均分布）。这是通过调用 req.Manager.partialSatisfy 方法来完成的。这一步要做两次。
- 和前面的步骤一样，现在加上完整的 未满足的大小。
清单 20. req.Manager.partialSatisfy1
2
3
4
5
6
7
8
9
10
11
12
| def partialSatisfy(self, bigRangeReqs, rationN, ratioD):
# Thru reqs, add to satisfy rationN/ratioD of requirement
for rr in bigRangeReqs:
curr = sum(self.reqs[rr.begin: rr.end])
needMore = rr.size - curr
if needMore > 0:
give = (rationN * (needMore + ratioD - 1)) / ratioD
q, r = divmod(give, rr.end - rr.begin)
for si in range(rr.begin, rr.end):
self.reqs[si] += q
for si in range(rr.begin, rr.begin + r):
self.reqs[si] += 1
|
可以将它与 GTK+ 的 gtk_table_size_request C 代码作比较，后者具有：
清单 21. gtk_table_size_request 片段1
2
3
4
| GTK_table_size_request_pass1 (table);
GTK_table_size_request_pass2 (table);
GTK_table_size_request_pass3 (table);
GTK_table_size_request_pass2 (table);
|
和这些 gtk_table_size_request_pass {1,2,3} 函数的实现。 |
