3
\$\begingroup\$

The goal is to take an array of numbers, have a max weight (saying 40%), and if any number above the max_num = sum * weight is present, remove the excess and distribute it over the sum of numbers that are below max_num based on their own weights.

The code is designed to be able to take a sum of any number, although in practice the sum will be 100.0 or less.

As an example:

(just realized the example was wrong, should have been 50%)
target_weight = 50%
numbers = [51,49]
result should be [50,50]

it takes the max weight of 50 for the sum of 100. Has an excess of 1, 49 owns 100% of the distribution numbers so it gets the full 1.

The following has ids in the Vec but this is only for the use case and not needed in the actual math.

In this example, the max weight is 40% with 1 of the numbers being 50. Therefor 10 is the excess and it gets distributed amongst the remaining numbers based on their weights of the sum of the numbers less than maximum number.

We use 1e2 for float accuracy when converting from u128 into f64.

sum = 10000
5000 (50.0) is 1000 (10.0) above the max a number can be of 4000 (40.0)
excess = 1000
We get the percentage weight based on sum of remaining numbers
2000 (20.0) weight = 40%
1000 (10.0) weight = 20%
1000 (10.0) weight = 20%
1000 (10.0) weight = 20%

50.0 turns into 40
20.0 turns into 24
10.0 turns into 12
10.0 turns into 12
10.0 turns into 12
fn main() {
    let target_weight: f64 = 0.40;

    let mut datas: Vec<(u16, u128)> = vec![
        (1, 2000),
        (2, 5000),
        (3, 1000),
        (4, 1000),
        (5, 1000),
    ];
    
    // sort desc
    datas.sort_by(|a, b| {
        b.1.cmp(&a.1)
    });
    
    // convert datas weights to float
    let mut datas_as_f64: Vec<(u16, f64)> = datas.iter()
        .map(|x| {
            (x.0, x.1 as f64 / 100.0)
        })
        .collect();

    let mut _nums_sum: f64 = 0.0;
    for data in datas_as_f64.iter() {
        _nums_sum += data.1;
    }
    
    let nums_len = datas.len();
    // assert math can be done
    assert!(target_weight * nums_len as f64 >= 1.0);

    let target_sum = _nums_sum as f64;
    let mut nums_sum = _nums_sum as f64;
    let mut excess = 0.0;
    let target_weight: f64 = 100.0 * target_weight;
    let max_num: f64 = nums_sum * target_weight / 100.0;

    // if a model has over max weight
    // distribute that to the other models
    // based on their proportion of remaining weight
    for num in datas_as_f64.iter() {
        let _num: f64 = num.1;
        if _num > max_num {
            excess += _num - max_num;
        }
    }

    println!("excess: {}", excess);
    println!("target_weight: {}", target_weight);

    // update weights and distribute
    for num in datas_as_f64.iter_mut() {
        let _num: f64 = num.1 as f64;
        if _num > max_num {
            num.1 = max_num;
        } else {
            let max_allot = max_num - _num;
            let percent_of_sum = _num * 100.0 / nums_sum;
            let possible_allot = excess * percent_of_sum / 100.0;
            if max_allot > possible_allot {
                num.1 += possible_allot;
                excess -= possible_allot;
            } else {
                num.1 += max_allot;
                excess -= max_allot;
            }
        }
        nums_sum -= _num;
    }
    
    let mut _nums_sum_post: f64 = 0.0;

    // print weights
    for data in datas_as_f64.iter() {
        println!("datas_as_f64 id: {}", data.0);
        println!("datas_as_f64 weight: {}", data.1);
        _nums_sum_post += data.1;
    }
    println!("_nums_sum_post: {}", _nums_sum_post);
}

What do you think of this? I've done manual testing just playing around with the numbers in the array and it works so far in my attempts.

To see the output visit this Playground page.

\$\endgroup\$
0

1 Answer 1

4
\$\begingroup\$

The major problem is that your code fails on some inputs. Consider:

let mut datas: Vec<(u16, u128)> = vec![
    (1, 2000),
    (2, 5000),
    (3, 4100),
    (4, 1000),
    (5, 1000),
];

It won't distribute numbers correctly. Your method for reallocation seems unsound.

let mut _nums_sum: f64 = 0.0;
for data in datas_as_f64.iter() {
    _nums_sum += data.1;
}

Iterators have a handy sum method which you can use to simply loops like this.

let _nums_sum: f64 = datas_as_f64.iter().map(|x| x.1).sum();

Also the use of _ at the start of a variable name goes against standard rust style.

You can simply this:

        if max_allot > possible_allot {
            num.1 += possible_allot;
            excess -= possible_allot;
        } else {
            num.1 += max_allot;
            excess -= max_allot;
        }

Instead you can do:

let allot = max_allot.min(possible_allot);
num.1 += allot;
excess -= allot;
\$\endgroup\$
8
  • \$\begingroup\$ When i test those numbers it results the same as the initial array. at a 40% weight of a sum of 131, the max is 52.4. In this case no numbers in the array should change. As for the sum suggestion. How can i run that with the Vec<(u16, u128)> without a for loop? \$\endgroup\$
    – Bob Linux
    Mar 4 at 6:07
  • \$\begingroup\$ thanks for the max_allot.min(possible_allot); this works, but the edit to your suggestion is using num.1 += allot ; excess -= allot ; i assume you meant. \$\endgroup\$
    – Bob Linux
    Mar 4 at 6:13
  • \$\begingroup\$ @BobLinux, I added an example of how to use sum. Yes, I messed up my edit, your guess was correct. \$\endgroup\$ Mar 5 at 0:41
  • \$\begingroup\$ @BobLinux, I may not have understood what your code is doing. Isn't the whole point that the sum doesn't change, but excess gets redistributed between the options? \$\endgroup\$ Mar 5 at 0:42
  • \$\begingroup\$ Yes. With your numbers the sum doesn't change. It's 131 and at the end it's 131. In that example, no numbers should change because the weight of 40% of the sum is never breached by any of the numbers. If you change it to 30%, 2 numbers are breached with an excess of 12.400000000000006 that is distributed to the non breaching numbers based on their weight of the non breaching numbers sum \$\endgroup\$
    – Bob Linux
    Mar 5 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.