CODEWITHSUNDEEP
javascriptarraysmath
Aamir Mahmood
Aamir Mahmood

Reputation: 2724

Why am I getting wrong results when dividing numbers into arrays with weight percentage?

I have number of users to allocate to number of computers instances like docker or AWS. user can increase the number of instances and also can change the users. The instances have weight percentage.

The total percentage might not be equal to hundred so scale factor can be anything.

My other requirement is each instance must have at least 1 user. I have condition applied that minimum user can not be less than locations so that part is good.

Other requirement is all users should be integers.

Example

Case #1

Users: 5
Locations: 4 where 1.weight = 15, 2.weight = 30, 3.weight = 15, 4.weight = 50 (total weight 110%)

Expected Results

Locations:
    1.users = 1,
    2.users = 1,
    3.users = 1,
    4.users = 2

Case #2

Users: 10
Locations: 4 where 1.weight = 10, 2.weight = 10, 3.weight = 90, 4.weight = 10 (total weight 120%)

Expected Results

Locations: 
    1.users = 1, 
    2.users = 1, 
    3.users = 7, 
    4.users = 1

Case #3

Users: 5
Locations: 2 where 1.weight = 50, 2.weight = 50

Expected Results

Locations: 
    1.users = 3, 
    2.users = 2

That was all of the explanation of the problem. Below is what I had tried.

function updateUsers(clients, weights) {
  
  let remainingClients = clients;
  const maxWeight = weights.reduce((total, weight) => total + parseInt(weight), 0);
  let r = [];
  weights.forEach(weight => {
    let expectedClient = Math.round(clients * (weight / maxWeight));
    let val = remainingClients <= expectedClient ? remainingClients : expectedClient;
    remainingClients -= expectedClient;
    r.push(val > 0 ? val : 1);
  });
  if ( remainingClients > 0 ) {
    r = r.sort((a, b) => a > b ? 1 : -1);
    
    for ( let i = 0; i < remainingClients; i++ ) {
      r[i] = r[i] + 1;
    }
  }
  return r;
}

I get good results for some numbers like

updateUsers(12, [5, 5, 5, 90]);

gives

[1, 1, 1, 9]; //total 12 users

but using very odd figures like below

updateUsers(12, [5, 5, 5, 200]);

returns

[2, 1, 1, 11]; //total 15 users which is wrong

Upvotes: 1

Views: 121

Answers (2)

Nur
Nur

Reputation: 2473

At first get percentage, You said that in every quota should at least have 1 user, So we used Math.floor(), If its equal to 0, we return 1 and update userCount like so 1 - percentage.

const sumProcedure = (sum, n) => sum + n;
function updateUsers(userCount, weights) {
    let n = userCount,
        totalWeight = weights.reduce(sumProcedure),
        results = weights.map(weight => {
            let percentage = (weight * userCount) / totalWeight,
                floor = Math.floor(percentage);

            if (floor == 0) {
                userCount -= 1 - percentage;
                return 1
            }
            return floor;
        }),
        remain = n % results.reduce(sumProcedure);

    while (remain--) {
        let i = weights.indexOf(Math.max(...weights));
        weights.splice(i, 1);
        results[i]++
    }
    return results;
}
console.log(updateUsers(5, [50, 50]));          // [3 , 2]
console.log(updateUsers(12, [5, 5, 5, 90]));    // [1, 1, 1, 9]
console.log(updateUsers(12, [5, 5, 5, 200]));   // [1, 1, 1, 9]
console.log(updateUsers(5, [15, 30, 15, 50]));  // [ 1, 1, 1, 2 ]
console.log(updateUsers(10, [10, 10, 90, 10])); // [ 1, 1, 7, 1 ]
console.log(updateUsers(55, [5, 5, 5, 90]));    // [ 3, 2, 2, 48 ]; It has 2 remainders

Upvotes: 2

MinosIllyrien
MinosIllyrien

Reputation: 455

This approach works if speed is not super important. I don't know javascript, so a bit of it is going to be in pseudocode. I'll keep your notations though.

Let wSum = sum(weights) be the sum of all weights and unitWeight = wSum / weights.length be the weight each user should be assigned if all were given equal weight. Now, let

r[i] = 1;
weights[i] -= unitWeight;

for i = 0, 1 ... weights.length-1. This ensures that all locations receive at least 1 user and the weights are updated to reflect their 'remaining' weight. Now

remainingClients = clients - weights.length;

Assign the rest of the clients via a while(remainingClients > 0) loop or similar:

while(remainingClients > 0)
{
    var indexMax = argMax(weights);
    weights[indexMax] -= unitWeight;
    r[indexMax] += 1;
    remainingClients -= 1;
}

This gives the expected result for all your examples. The argMax should of course just return the index of the array corresponding to the maximum value. Due to argMax, the runtime becomes O(n^2), but it doesn't sound like you have tens of thousands of users, so I hope that's okay.

Upvotes: 1

Related Questions