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.
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))
'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)
'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)
MaxMinFairDK = vaReturn
MaxMinFairDK = CVErr(Err.Number)
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.
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.
8 thoughts on “MaxMinFair Rewrite”
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.
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 …
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.
Posting code? Use <pre> tags for VBA and <code> tags for inline.