Sorting Vector of vectors of f64

Hi. I'm trying to write the code for the fractional knapsack algorithm and I need some help figuring out how to sort this vector I created (if it is possible at all). Perhaps my implementation is not the most efficient one, but first let me explain the reasoning behind it.
I'm doing this as a part of a Coursera course. The inputs for the assignment come as stdin from the user. So the first line of input tells the number of N items that you can choose from and the total capacity of your bag.
The next N lines will have the value and the weight of each item.
Here is what I've done so far.
use std::io;
use std::str::FromStr;

fn read_value<T: FromStr>() -> Result<T, <T as FromStr>::Err> {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("could not read from stdin");
    s.trim().parse()
}

fn read_values<T: FromStr>() -> Result<Vec<T>, T::Err> {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("could not read from stdin");
    s.trim().split_whitespace().map(|word| word.parse()).collect()
}

fn main() {
    let capacity = read_values::<f64>().unwrap();
    println!("{:?}", capacity);
    let length = capacity[0].clone();
    let mut items:Vec<Vec<f64>> = Vec::with_capacity(length as usize);
    for (_, j) in (0..items.capacity()).enumerate() {
        let mut values = read_values::<f64>().unwrap();
        let weight = values[0]/values[1];
        values.push(weight);
        items.push(values);
    };
    items.sort_by(|a, b| a[2].partial_cmp(b[2]));
    println!("{:?}", items);
//    items.
    let mut vecofvalbyw: Vec<f64> = Vec::with_capacity(items.capacity());
    for item in &items {
        vecofvalbyw.push(item[0]/item[1]);
    }
    let mut result = 0f64;
    let mut tweight = 0f64;
    loop {
   // Here items[2][1] is the item with the higher value/weight ratio

        if items[2][1] < capacity[1] && items[2][1] < capacity[1]-tweight {
            result += &items[2][0];
            tweight += &items[2][1];
            if  tweight == capacity[1] {
                break;
            }
    // Haven't finished the algorithm. Still thinking
        }
    }
    println!("{}", result);
}

As you can see, I haven't finished the algorithm yet because I still haven't figured out what the next move should be. I'm thinking that the next step is to check if the weight of the item exceeds the capacity and add just the fraction that will fit. Then, I would jump to the second most benefiting item and repeat the process.
Ok, but that is not the main problem here.
As a result of my implementation, the items vector is a Vec<Vec>. And it would make it easier to choose which item to add in the bag if I could sort these vectors based on the third element. The third element is the value/weight ratio.
This would give a Vec<Vec> sorted by the third element of each internal vector.
I tried items.sort_by(|a, b| &a[2].partial_cmp(&b[2])); but rust returns
^^^^^^^^^^^^^^^^^^^^^^expected enum std::cmp::Ordering, found reference

I didn't really understand the error message, but I'm guessing this is not the way to do this. I mean, this is not the way to sort the vector in the first place. The problem is I don't know what the right way of doing would be.

Any advice?

Thanks
Fabrex

I'm fairly new to Rust but I've hit this issue several times. Here's the kind of solution I'm using:

use std::cmp::Ordering;

fn main() {
    let mut items = vec![4.5, 11.5, -7.3, 14.0, 18.7, 11.5, 1.3, -2.1, 33.7];
    println!("{:?}", items);
    items.sort_by(cmp_f64);
    println!("{:?}", items);
}

fn cmp_f64(a: &f64, b: &f64) -> Ordering {
    if a < b {
        return Ordering::Less;
    } else if a > b {
        return Ordering::Greater;
    }
    return Ordering::Equal;
}

Link to code in the playground.

Note that this will explode violently on some f64 values (NaNs), which is why Rust does not do it by default.

2 Likes

@HadrienG: fair point.

Given this input:

let mut items = vec![4.5, 11.5, -7.3, 14.0, f64::NAN, 18.7, 11.5, f64::NAN, 1.3, -2.1, 33.7];

here are two possible solutions either of which is sufficient on its own.

Solution 1: Filter out any NANs first:

items = items.iter().filter_map(|f| if f.is_nan() { None } else { Some(*f) }).collect::<Vec<f64>>();

Here's the output:

[-7.3, -2.1, 1.3, 4.5, 11.5, 11.5, 14.0, 18.7, 33.7]

Solution 2: Account for NANs in the comparison:

fn cmp_f64(a: &f64, b: &f64) -> Ordering {
    if a.is_nan() {
        return Ordering::Greater;
    }
    if b.is_nan() {
        return Ordering::Less;
    }
    if a < b {
        return Ordering::Less;
    } else if a > b {
        return Ordering::Greater;
    }
    return Ordering::Equal;
}

This second solution arbitrarily puts NANs at the end to make them easy to check for & pop off. Here's the output:

[-7.3, -2.1, 1.3, 4.5, 11.5, 11.5, 14.0, 18.7, 33.7, NaN, NaN]
2 Likes

Indeed! A third popular solution is to use a floating-point wrapper which adds the additional guarantee of not being NaN, such as noisy_float.

Once you are aware of this IEEE 754 design flaw, there are many ways to work around it. It is nice that the Rust type system helps you acknowledge its existence :slight_smile:

1 Like

I would suggest you to use a struct Item to improve readability of your code and make it more comprehensible, instead of constructing a vector of vectors.

Moreover this solution may be more efficient because you have one less level of indirection and you don't need to ask for an allocation for each item and take advantage of the stack, instead.

Thank you all for your suggestions. I'm making the changes right now and so far so good.
After I get the entire code running I'll be taking garro's suggestion and placing the values in a struct.

Fabrex

This can be done more simply using the retain method:

items.retain(|f| !f.is_nan())

This should also be faster, with one less allocation, but I haven't done any benchmark to confirm that.

When you need to do that with a iterator, I think than using .cloned and .filter instead of .filter_map makes your intention more clear, but this is pretty subjective:

items = items.iter().cloned().filter(|f| !f.is_nan()).collect::<Vec<f64>>();
1 Like

Hi everybody. Just wanted to thank you all for the suggestions and say that this list forum is really helping me learn Rust. I wanted to post the final code just for the record. I know that there are certainly more efficient ways of implementing this, but I am really happy with the final result. When I say "final result" I don't mean the code itself, but rather the opportunity to learn from implementing it.
Thank you very much
Here is the code

use std::io;
use std::str::FromStr;
use std::cmp::Ordering;

fn read_values<T: FromStr>() -> Result<Vec<T>, T::Err> {
    let mut s = String::new();
    io::stdin().read_line(&mut s).expect("could not read from stdin");
    s.trim().split_whitespace().map(|word| word.parse()).collect()
}

fn comp_f64(a: &f64, b: &f64) -> Ordering {
    if a < b {
        return Ordering::Less;
    } else if a > b {
        return Ordering::Greater;
    }
    Ordering::Equal
}

fn input_parser() -> (Vec<Vec<f64>>, Vec<f64>) {
    let capacity = read_values::<f64>().unwrap();
    let length = capacity[0].clone() as usize;
    let mut items:Vec<Vec<f64>> = Vec::with_capacity(length);
    for _ in 0..items.capacity() {
        let mut values = read_values::<f64>().unwrap();
        let weight = values[0]/values[1];
        values.push(weight);
        items.push(values);
    };
    items.sort_by(|a, b| comp_f64(&a[2],&b[2]));
    (items, capacity)
}

fn fract_knapsack(items: Vec<Vec<f64>>, capacity:Vec<f64>) {
    let mut result = 0f64;
    let mut tweight = 0f64;
    for item in items.iter().rev() {
        if tweight < capacity[1] && capacity[1] - tweight >= item[1] {
            result += item[0];
            tweight += item[1];
        } else if capacity[1] - tweight < item[1] {
            result += item[0] * ((capacity[1] - tweight) / item[1]);
            tweight += item[1] * ((capacity[1] - tweight) / item[1]);
        }
        if tweight == capacity[1] {
            break;
        }
    }
    println!("{:.4}", result);
}

fn main() {
    let (items, capacity) = input_parser();
    fract_knapsack(items, capacity);
}

Ps: I haven't done the Struct suggestion, but will surely get it going in a near future. The thing is, I work with computational chemistry doing molecular dynamics simulations and we are a bit used to the whole vector of vectors here in the lab. But I greatly appreciate the suggestion.

1 Like