• 26.2k
• 13
• 47
• 113

• 26.2k
• 13
• 47
• 113

• 93
• 3

I'm learning Rust by solving ProjectEuler problems.

To this end, I am trying to port a solution to problem 88 (link) in Python that heavily relies on generators to Rust (which doesn't have generators).

I tried doing this by basically implementing a state machine in a recursive struct that implements the Iterator trait, but it runs many times slower than the Python version, and I can't exactly figure out why.

Flamegraph implies that a lot of time is spent in allocating memory, which sort of makes sense, but I don't understand why the Rust version is so much slower.

Can anyone explain why the Rust version is so much slower and/or how to optimise it to be as fast (or faster) than the Python version, while being more idiomatic?

Thanks in advance!

Python algorithm:

def solution88(N=12000):
 import itertools as it
 def multiplicative_partitions(n, k=None, i_min=2):
 if k is None:
 # Start from k=2 to avoid the trivial partition (n,)
 for k in it.count(2):
 x = multiplicative_partitions(n, k)
 try:
 yield next(x)
 except StopIteration:
 return
 yield from x
 elif k <= 0:
 return
 elif k == 1:
 yield (n,)
 elif k == 2:
 sqrt_n = int(n ** 0.5)
 for i in range(i_min, sqrt_n + 1):
 if not n % i:
 yield (i, n // i)
 else:
 sqrt_n = int(n ** 0.5)
 for i in range(i_min, sqrt_n + 1):
 if not n % i:
 for a in multiplicative_partitions(n // i, k - 1, i):
 yield (i, *a)
 unprocessed = N - 2 + 1
 results = [None] * unprocessed
 n = 4 # 4 = 2 + 2 = 2 * 2
 while unprocessed > 0:
 for mp in multiplicative_partitions(n):
 if n >= sum(mp):
 k = n - sum(mp) + len(mp)
 if k <= N and results[k - 2] is None:
 results[k - 2] = n
 unprocessed -= 1
 n += 1
 print(set(results))
 return sum(set(results))
print(f"The answer is: {solution88()}")

(Note: I didn't come up with this Python solution, but a much slower one, initially. Credit for this one goes to user '6557' on ProjectEuler)

Rust algorithm:

use itertools::Itertools;
use std::collections::HashSet;
const LIMIT: usize = 12_000;
struct MulPar {
 n: usize,
 k: usize,
 i: usize,
 sqrt_n: usize,
 inner: Option<Box<MulPar>>,
}
impl Iterator for MulPar {
 type Item = Vec<usize>;
 fn next(&mut self) -> Option<Self::Item> {
 if self.k == 0 || self.i > self.sqrt_n {
 None
 } else if self.k == 1 {
 self.k = 0;
 Some(vec![self.n])
 } else if self.k == 2 {
 while self.i < self.sqrt_n + 1 {
 if self.n % self.i == 0 {
 let i = self.i;
 self.i += 1;
 return Some(vec![i, self.n / i]);
 }
 self.i += 1;
 }
 None
 } else if let Some(mut inner) = self.inner.take() {
 if let Some(mut next) = inner.as_mut().next() {
 next.push(self.i);
 self.inner = Some(inner);
 Some(next)
 } else {
 self.inner = None;
 self.i += 1;
 if self.i > self.sqrt_n + 1 {
 // no more partitions to yield
 None
 } else {
 while self.n % self.i != 0 {
 self.i += 1;
 }
 self.inner = Some(Box::new({
 let sqrt_n = ((self.n / self.i) as f64).sqrt() as usize;
 MulPar {
 n: self.n / self.i,
 k: self.k - 1,
 i: self.i,
 sqrt_n,
 inner: None,
 }
 }));
 self.next()
 }
 }
 } else {
 if self.i > self.sqrt_n {
 None
 } else {
 while self.n % self.i != 0 {
 self.i += 1;
 }
 self.inner = Some(Box::new({
 let sqrt_n = ((self.n / self.i) as f64).sqrt() as usize;
 MulPar {
 n: self.n / self.i,
 k: self.k - 1,
 i: self.i,
 sqrt_n,
 inner: None,
 }
 }));
 self.next()
 }
 }
 }
}
fn main() {
 let mut unprocessed = LIMIT - 2 + 1;
 let mut n = 4;
 let mut results = vec![None; unprocessed];
 while unprocessed > 0 {
 for j in 2..(LIMIT - 1) {
 for mp in multiplicative_partitions(n, j, 2) {
 let mp_sum = mp.iter().sum::<usize>();
 if n >= mp_sum {
 let k = n - mp_sum + mp.len();
 if k <= LIMIT && results[k - 2].is_none() {
 results[k - 2] = Some(n);
 unprocessed -= 1;
 }
 }
 }
 }
 n += 1;
 }
 let set: HashSet<usize> = HashSet::from_iter(results.into_iter().map(|x| x.unwrap_or(0)));
 println!("{:?}", set.iter().cloned().sorted().collect::<Vec<usize>>());
 let answer = set.into_iter().sum::<usize>();
 println!("The answer is: {answer}");
}
fn multiplicative_partitions(n: usize, k: usize, i: usize) -> MulPar {
 let sqrt_n = (n as f64).sqrt() as usize;
 MulPar {
 n,
 k,
 i,
 sqrt_n,
 inner: None,
 }
}