I think one thing that makes this pretty hard to review is that it's math-dense, and doesn't have a lot of documentation for what each function does. I can help review the rustyness of individual lines of code, but a lot of what makes code good or bad is it's overall structure, and figuring that out without good documentation & without intimately understanding the math is hard.
Things I found, though, looking over it:
Things I'd care about more deeply and would probably request changed in a PR:
-
I your first to_owned call, on lines 27, is actually just cloning the value, and should use clone instead. ToOwned is implemented for everything which implements Clone, so using to_owned is functionally equivalent, but it gives the reader the wrong idea. When I see to_owned I initially assume you're doing an operation like turning &[i64] into Vec<i64> - changing types - not turning &VecDeque into VecDeque.
-
It looks like all_tree_values is only ever called with a new HashSet in the second argument. If this is the case, I highly recommend refactoring it so it just creates that hashset inside itself and returns it as a result.
-
Similarly, I think split should also return its result, rather than mutating an argument. It'll make it's purpose much more clear, and also clear up code calling it.
let sst = split(&lhsv, &rhsv);
is much clearer than
let mut sst = HashSet::new();
split(&lhsv, &rhsv, &mut sst);
-
It's not bad per se, but I'd remove a lot of the type annotations you have. For instance, in lines 57-66, you're adding two rationals, so I think it's fairly obvious that you get a rational out. Giving rp, rm and rt explicit types confuses me, then, and makes me think "is there something weird going on that requires this?".
Similarly, when declaring collections, I'd leave out a lot of the types. Whenever the right hand side is HashMap::new(), it's obvious that you're creating a hashmap, and there isn't any need for type annotations on the left hand side. Sure, you are telling the reader what element type is expected and that is new information, but I think even that's usually obtainable from the environment.
If the type annotations don't add new information, and they aren't required by the compiler, then all they're doing is giving the reader extra work.
-
On line 79, I think you should be able to avoid using split_off and instead use something which doesn't mutate the underlying Vec. Immutable slices - &[i64] - can point to arbitrary places in a vec, so you don't need to create a whole new underlying allocation just to split one up.
let mut lhsv: Vec<i64> = lst.to_owned();
let rhsv = lhsv.split_off(pivot);
split(&lhsv, &rhsv, &mut sst);
Could become:
let lhsv = &lst[0..pivot];
let rhsv = &lst[pivot..];
This is one of the great things Rust can do which is impossible for many languages, even many GCd ones. These new lhsv and rhsv simply point to sub-slices of the original slice - they don't allocate anything new, these lines literally just change the start & end point from lst.
And if you implement the above suggested change to split making it return its result rather than mutate an argument, this piece of code could even become a pretty readable one-liner:
let mut sst: HashSet<Rational64> = HashSet::new();
let mut lhsv: Vec<i64> = lst.to_owned();
let rhsv = lhsv.split_off(pivot);
split(&lhsv, &rhsv, &mut sst);
for r in sst {
st.insert(r);
}
becomes:
st.extend(split(&lst[..pivot], &lst[pivot..]);
Surface level things - these don't matter much, but they could make your code more concise:
-
A lot of small loops which just add to another collection can be replaced with extend - a method supported by most collections to "add all" of an iterator.
for s in suffix.iter().skip(1) {
revprefix.push_back(*s);
}
would become
revprefix.extend(suffix.iter().skip(1));
(and similar changes to other such loops)
-
I think the inner loop in main could be replaced with something functional, if you want:
for r in st {
if r > Rational64::zero() && *r.denom() == 1 {
// save only positive integers to be summed
reachable.insert(*r.numer());
}
}
Could become:
reachable.extend(
st.iter()
.filter(|&&r| r > Rational64::zero() && *r.denom() == 1)
.map(Rational64::numer),
);
If you implemented my above suggestion of making all_tree_values return its result rather than mutating an argument, you could go even further functional:
let reachable = mergings
.into_iter()
.map(|m| all_tree_values(&Vec::from(m)))
.flat_map(|st| {
st.into_iter()
.filter(|&r| r > Rational64::zero() && *r.denom() == 1)
.map(|r| *r.numer())
})
.collect::<HashSet<_>>();
You may or may not see that as an improvement - and the old version was plenty Rusty. Thought I'd put this in though to give you an idea of how it could be written like this.
I think only one of those suggestions is actually a performance improvement, but the rest should give something of an idea of how to make it more Rusty.
It might also be possible to remove the to_owned/clone on line 29, but I don't know enough about the algorithm to say whether it's feasible. If I'm reading it correctly, though, then I think you should be able to have all_mergings take an &[i64], and instead of removing items from it, you can just change what portion of the underlying Vec you're looking at. For instance, line 13 would change like so:
instead of actually mutating the underlying storage:
let frstsuf: i64 = suffix.pop_front().unwrap();
it'd just grab the item and change what part of the underlying storage we think of suffix as:
let frstsuf = suffix[0];
suffix = &suffix[1..];
Anyways, hope that helps! Let me know if you have any questions about any of these suggestions, and whether you think these are reasonable. Most of this stuff, especially in the second "surface level things" list, is subjective - so there's room for debate!