稍微說點錢的事吧 - 分錢的方法 (3)
|
MyDivider1 |
|||
|
id |
factor |
value |
Diff. |
|
0 |
40 |
0 |
-0.4 |
|
1 |
20 |
1 |
0.8 |
|
2 |
20 |
0 |
-0.2 |
|
3 |
20 |
0 |
-0.2 |
|
|
|
|
|
|
SUM: |
100 |
1 |
0 |
|
Sum( | Diff | ) = 1.6 |
|||
繼續上次的題目，先來看看上次結束時的表格。
第一位(id=0)出了40%的錢，卻少拿0.4元。
第二位(id=1)出了20%的錢，卻多拿0.8元。
這是不是不太公平呢？
那個Diff.，給他一個工程一點的名字叫做"誤差"好了。
不知道有沒有人注意到，上次的Print程式碼，算出表格內Diff^2 Sum這個值。我叫他"誤差絕對值和" (其實通常會用平方和，在(2)裡面是用平方和的)
大家對誤差這東西有什麼看法沒？ 它應該是不可避免、但是愈接近零愈好的東西。
在整個系統中，誤差絕對值和也是不可避免、但愈接近零愈好的數值。
(2)的算法是完全無法解決這個問題的，這邊我要換個算法，其實非常單純：
1. 先發給所有人、發到夠，但不發到超過。這時所有人的Diff會是負值，而且會符合 | Diff | < 最小單位 p。
2. 所有人依Diff做排序，少最多的先拿一份最小單位 p，他會變成多最少的人。依序直到發完。
以下為證明，不想看可跳過：
證明法1
共多了N分最小單位p
排序後所有可拿到那N份的誤差分類到集合Q，
拿不到的誤差分類成集合R。
因為排序，q∈∀Q、r∈∀R ， q< r< (q + p) 成立。
假設q不拿多的一份p，而讓 r 去拿，會使誤差平方和變小。
(q+p)2 + r2 > q2 + (r+p)2
q2 + 2qp + p2 + r2 > q2 + r2 + 2rp + p2
2qp > 2rp
q > r 與 q< r< (q + p) 矛盾，不成立。
故不存在任何Q、R間的交換可使誤差平方和變小，證明此分配法誤差平方和是最小的。
證明法2
若一個系統在分完錢後，可以找到一個多拿的人，將他多拿的一個刻度p，轉給一個少拿的人，並使他們兩個的誤差絕對值和減少，代表系統現在的狀態誤差絕對值和不是系統可能的最小值。
誤差為集合D。
某筆正的誤差dm，將一個刻度p轉給某筆負的誤差dn。
兩者原始誤差絕對值和 = dm + (-dn) = dm – dn
轉移後的誤差絕對值和 = (p – dm) + (dn + p) = 2p – (dm – dn)
誤差減少代表
dm – dn ＞ 2p – (dm – dn)
2(dm – dn) ＞ 2p
dm – dn ＞ p
當dm = Dmax, dn = Dmin時，dm – dn 有最大值。
故，當 Dmax – Dmin ＞p 成立時，代表系統現在的狀態誤差絕對值和不是系統可能的最小值。
※至此可以作為單元測試的測試式。
又，dm – dn ＞p
dm – p ＞ dn
dm – p 為拿到p 之前的誤差，若是排序後才分配，必定(dm – p ) ＜ dn，故
dm – p ＞dn 不成立。
可反證排序後再分配的算法，誤差絕對值和是可能的最小值。
以下依照新的方式設計算法，看起來很長但實際有一半是註解。順便因應新的規則修改一下單元測試。
這個算法裡面有一些有趣的細節。另外，只能傳陣列、拿陣列也不太好用。故、待續！
不過在那之前，我應該會先寫寫另一個主題、敬請期待！
public class MyDivider2 : BaseDivider
{
sealed protected override decimal[] divide(decimal[] factors, decimal totalValue, int digits)
{
return Divide(factors, totalValue, (decimal)Math.Pow(0.1, digits));
}
/// <summary>依照輸入的比例、總值、與最小單位，傳回分配的結果。</summary>
/// <param name="totalValue">被分配的總值。</param>
/// <param name="factors">各單位的權重。</param>
/// <param name="graduation">刻度，就是最小單位</param>
/// <returns>依照權重分配總值的結果。</returns>
public decimal[] Divide(decimal[] factors, decimal totalValue, decimal graduation)
{
// 特殊狀況
if (factors == null)
throw new NullReferenceException();
if (factors.Length == 0)
return new decimal[0];
if (factors.Length == 1)
return new decimal[] { totalValue };
int count = factors.Length;
decimal[] values = new decimal[count];
decimal fSum = factors.Sum();
// 每股(factor)能分配到的錢(value)
decimal valPerFact = totalValue / fSum;
// 每股(factor)能分配到的刻度份數(graduation)
decimal grdPerFact = valPerFact / graduation;
// 函數: 計算某index的factor，可以分配到幾份的理論刻度(含小數點下)
Func<int, decimal> getGraduationCount = i => grdPerFact * factors[i];
// 函數: 計算某index的factor，小數點以下、領不到的刻度差
Func<int, decimal> computeDiff =
i =>
{
var _grd = getGraduationCount(i);
// 實際領到的整數刻度 - 可領到的理論刻度 = 沒領到的差額
return Math.Truncate(_grd) - _grd;
};
// 紀錄已分發的總值
var currValueShared = 0M;
for (int i = 0; i < count; i++)
{
values[i] = Math.Truncate(getGraduationCount(i)) * graduation;
currValueShared += values[i];
}
// 還有幾個刻度能分
int partCount = (int)Math.Truncate((totalValue - currValueShared) / graduation);
// 如果在這邊就結束、當然很讚
if (partCount == 0)
return values;
// 建立索引表，供排序
int[] idxTable = new int[count];
for (int i = 0; i < count; i++)
idxTable[i] = i;
// 依差作排序(很慢), 少最多的每人分得一單位
// *排序(OrderBy)是最慢的部分
var idxEnumerator = idxTable
.OrderBy(i => computeDiff(i))
.Take(partCount);
// 多拿一個刻度後，會變成"多最少"的人
foreach (int i in idxEnumerator)
values[i] += graduation;
return values;
}
}
結果：
|
MyDivider2 |
|||
|
id |
factor |
value |
Diff. |
|
0 |
40 |
1 |
0.6 |
|
1 |
20 |
0 |
-0.2 |
|
2 |
20 |
0 |
-0.2 |
|
3 |
20 |
0 |
-0.2 |
|
|
|
|
|
|
SUM: |
100 |
1 |
0 |
|
Sum( | Diff | ) = 1.20 |
|||