4

我正在尝试解决我的第一个项目 Euler 问题，只是为了玩 Rust 的乐趣，并且陷入了似乎需要很长的计算时间才能解决的问题

问题： https ://projecteuler.net/problem=757

我想出了这段代码来尝试解决它，我能够在约 245 毫秒内解决基本问题（最多 10^6）并获得预期的结果 2,851。

use std::time::Instant;

fn factor(num: u64) -> Vec<u64> {
    let mut counter = 1;
    let mut factors = Vec::with_capacity(((num as f64).log(10.0)*100.0) as _);
    while counter <= (num as f64).sqrt() as _ {
        let div = num / counter;
        let rem = num % counter;
        if rem == 0 {
            factors.push(counter);
            factors.push(div);
        }
        counter += 1
    }
    factors.shrink_to_fit();
    factors
}

fn main() {
    let now = Instant::now();
    let max = 10u64.pow(6);
    let mut counter = 0;
    'a: for i in 1..max {
        // Optimization: All numbers in the pattern appear to be evenly divisible by 4
        let div4 = i / 4;
        let mod4 = i % 4;
        if mod4 != 0 {continue}
        // Optimization: And the remainder of that divided by 3 is always 0 or 1
        if div4 % 3 > 1 {continue}
        let mut factors = factor(i);
        if factors.len() >= 4 {
            // Optimization: The later found factors seem to be the most likely to fit the pattern, so try them first
            factors.reverse();
            let pairs: Vec<_> = factors.chunks(2).collect();
            for paira in pairs.iter() {
                for pairb in pairs.iter() {
                    if pairb[0] + pairb[1] == paira[0] + paira[1] + 1 {
                        counter += 1;
                        continue 'a;
                    }
                }
            }
        }
    }
    println!("{}, {} ms", counter, now.elapsed().as_millis());
}

看起来我的代码在因式分解上花费的时间最多，并且在我寻找比我自己想出的更有效的因式分解算法时，我找不到任何已经生成的 rust 代码（我确实找到的代码实际上更慢。）但是我做了一个模拟来估计即使我有一个完美的因式分解算法也需要多长时间，并且使用非因式分解需要 13 天才能找到高达 10^14 的所有数字此代码的一部分。可能不是这个问题的创建者想要的。

鉴于我对编程比较陌生，是否有一些我不知道的概念或编程方法（比如使用哈希图进行快速查找）可以在这种情况下使用？或者解决方案是否涉及在数字中发现模式并进行优化，就像我迄今为止发现的那样？

4

1 回答 1

0

如果Vec::push在向量达到其容量时调用，它将重新分配其内部缓冲区以使大小加倍并将其所有元素复制到此新分配中。 Vec::new()创建一个没有分配空间的向量，因此它将进行重新分配。

您可以使用Vec::with_capacity((num/2) as usize)来避免这种情况，只需分配您可能需要的最大值。

于 2021-06-22T23:15:32.837 回答