I read Charles William’s MaxMinFair algorithm and I didn’t like his approach. That’s typical. I’ll read somebody’s code and think “They’re making that too hard”. Then I’ll set about rewriting it. In this case, as in most cases, it turns out that it is that hard, but I wasn’t going to convince myself until I tried it. I ended up with a different approach that’s not shorter, not easier to read, and not easier to follow. Oh well, here it is anyway.
|
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 |
Function MaxMinFairDK(Supply As Double, Demands As Variant) As Variant Dim dPrior As Double Dim vaReturn As Variant Dim dAvailable As Double Dim i As Long, j As Long Dim dTemp As Double Dim wf As WorksheetFunction On Error GoTo ErrHandler Set wf = Application.WorksheetFunction If IsObject(Demands) Then Demands = Demands.Value2 'make range array dAvailable = Abs(Supply) 'ignore negative supplies If Not IsArray(Demands) Then 'One demand = min of supply or demand MaxMinFairDK = Array(dAvailable, Demands)(Abs(dAvailable > Demands)) Else 'Excel returns NA when you use too many columns If UBound(Demands, 2) > 1 Then Err.Raise xlErrNA 'Assume everybody gets everything they want ReDim vaReturn(LBound(Demands, 1) To UBound(Demands, 1), 1 To 1) vaReturn = Demands For i = UBound(Demands, 1) To LBound(Demands, 1) Step -1 'If there's enough, do nothing except reduce what's available If dAvailable / i > (wf.Large(Demands, i) - dPrior) Then dAvailable = dAvailable - ((wf.Large(Demands, i) - dPrior) * i) dPrior = wf.Large(Demands, i) Else 'Once there's not enough, everyone splits what's left For j = LBound(Demands, 1) To UBound(Demands, 1) If Demands(j, 1) > dPrior Then vaReturn(j, 1) = dPrior + (dAvailable / i) End If Next j Exit For End If Next i MaxMinFairDK = vaReturn End If ErrExit: Exit Function ErrHandler: MaxMinFairDK = CVErr(Err.Number) Resume ErrExit End Function |
In Charles’s implementation, he allocates an equal amount of the supply to each node, then takes back what that node didn’t need and puts it back in the available pool. When I was looking at the results, I was thinking that the smallest n nodes simply get their demand and only when there’s not enough to go around do we need to do something different than allocate the full demand.
In my implementation, I start by giving everyone what they demand. Then I start with the smallest demand, and if I can accommodate that amount for everyone, I just reduce the amount available and move to the second smallest demand. At some point (the sixth smallest demand in Charles’s data) I can’t meet that demand and still give everyone an equal share. At that point, I give anyone who hasn’t had their demand met an equal amount – the amount that’s already been distributed plus an equal share of what’s left.
| Rank | Demand | Incremental Demand | Allocated | Remaining |
|---|---|---|---|---|
| 18.30 | ||||
| 7 | 0.70 | 0.70 | 4.90 | 13.40 |
| 6 | 1.00 | 0.30 | 1.80 | 11.60 |
| 5 | 1.30 | 0.30 | 1.50 | 10.10 |
| 4 | 2.00 | 0.70 | 2.80 | 7.30 |
| 3 | 3.50 | 1.50 | 4.50 | 2.80 |
| 2 | 7.40 | 3.90 | 7.80 | (5.00) |
| 1 | 10.00 | 2.60 | 2.60 | (7.60) |
In the first iteration, I hand out 0.70 to everyone because I have enough supply to do that. In the second iteration, I had out the differential, 0.30, to everyone who’s left because I have enough supply remaining. When I get to #2, I can’t hand out 3.90 to the remaining two nodes because I don’t have enough supply. I’ve allocated up to 3.5 to anyone who’s demanded it, so the last two get the 3.5 plus half of the 2.8 that remains.
Although I didn’t accomplish anything, it was still a fun exercise.
It’s always interesting to see how someone else codes the same thing!
I think I win on execution speed, probably because you are using wf.LARGE.
snb writes:
Quite right Charles. I never consider execution speed until it’s too late, but I should have guessed that you considered it. I started out sorting the list, but didn’t like it because the output array needs to match the input array. Still, it may have been the better way. It would get rid of the worksheet function part, which is always good because it make the code more portable.
After sorting the task is much easier:
Timing for my UDf, Dick’s UDF and SNB’s sub on my example data
CW UDF .084
DK UDF .127
SNB Sub 10.8
I thought a sort based function might be faster with a long table, so I wrote one using my VBA sort routine, and another calling a Python sort.
Here are results for 10,000 rows (times in seconds):
CW UDF 0.014
DK UDF 21.64
SNB Sub1 163.8 for 1000 rows
SNB Sub2 0.055
DJ VBA UDF 0.051
DJ Py UDF 0.025
So some pretty dramatic differences there. Now I just need to have another look at Charles’ code and see how he gets it so fast on unsorted data.
I am curious about the code to turn a range into an array
If IsObject(Demands) Then Demands = Demands.Value2 ‘make range array
Since Demands is a parameter passed into the function, and by default it is passed in ByRef, is it safe to just overwrite the parameter in that way – should the parameter be defined as ByVal just to be safe? If the calling function did something else with that parameter afterwards, then it might be expecting it to be pointing to a range object, not an array. Just curious …
@Charlie
The function is a worksheet User Defined Function and so can only return the result of the function for Excel( parameters are not passed back to Excel).
If it was going to be called from code you would assign it to a variable local to the function and then coerce to values if required.