为高开销循环构建筛选器：优化大数值范围的Rust代码

我正在编写一段需要遍历大量数值的代码，但存在大量无效计算。我甚至无法用数学语言准确描述需要跳过的数值——随着i增大，需跳过的i占比越来越高。

核心逻辑（伪代码） #

f(n)
    while n > 0
        if 32 < n%250 < 129 do work, else discard
        n = floor( n/250 )
        
g(n)
    while n > 0
        if n%3 == 0 do work, else discard
        n = floor( n/288 )

main()
    for i in range
        print f(i) and g(i) if neither function hits discard & both same total # of loops

优化需求 #

我希望构建一个尽可能减少无效计算的range。目前已想到的优化包括使用(0..n).step_by(3)确保g(n)首次循环有效，以及先执行并检查f(n)，若触发discard则无需执行g(n)。

我需要一种类似.step_by(3)的方式，定义一个仅包含能通过while所有循环的数值的range，理想状态下while循环内无需任何if判断，直接遍历有效数值。

本质上我想知道能否通过减少遍历数值，将代码的时间复杂度从基于250和288优化到基于91（若能结合最终判断逻辑进一步降低至91以下则更佳）。当前代码输出正确，但执行耗时极长，我希望能运行至超大数值范围（目标为250^{40≈8.27e95≈2}319.7），因此提前确定可跳过的数值能大幅减少计算量。

有效数值可视化说明 #

为便于理解所需数值的特征，我绘制了几个场景的有效数值网格：

• 仅考虑g(n)场景（使用更小数值：n%2和floor(n/6)）：高亮蓝色整列代表可通过的数值，高亮白色行代表被丢弃的节点。
• 使用n%3和floor(n/6)的同场景：视觉上与上一个网格类似。
• 使用1<n%6<4的f(n)函数场景：展示了对应f(n)逻辑的有效数值分布。

现有优化后的代码 #

use arrayvec::ArrayVec;
fn main() {
    'outer: for n in (0..18446744073709551615u64).step_by(3) { //2^64-1; make smaller if you want the code to finish
        let mut base250: ArrayVec<u8, 8> = ArrayVec::new(); //using ArrayVec makes reallocation slowdowns go away
        let mut tmp:u8;
        let mut m = n;
        while m > 0 { //f(n) of the psudocode; inlined here
            tmp = (m%250).try_into().unwrap(); //type goes from u64(n) into u8(tmp)
            if tmp-33 < 96 { //takes advantage of uint rollover to just do 1 comparison
                base250.push(tmp-1);
            } else { continue 'outer; } //condition broke; discard this run and try the next value
            m /= 250;
        }
        m = n;
        let mut base288: ArrayVec<u8, 8> = ArrayVec::new();
        while m > 0 { //g(n) of the psudocode; inlined here
            if m%3==0 {
                base288.push((m/3%96+32).try_into().unwrap()); //type goes from u64(n) into u8(t)
            } else { continue 'outer; } //condition broke; discard this run and try the next value
            m /= 288;
        }
        base250.reverse();
        if base250.iter().zip(base288.iter()).filter(|&(a,b)| a==b).count() > 3 { //checks how many values are matching
            let long:String = base250.iter().map(|&c|{if c == 127u8 {'¶'} // convert the vector to a string
                                                  else if c == 32u8 {'█'} // with readable newlines and spaces
                                                  else {c.try_into().unwrap()} }).collect();
            let short:String = base288.iter().map(|&c|{if c == 127u8 {'¶'}
                                                  else if c == 32u8 {'█'}
                                                  else {c.try_into().unwrap()} }).collect();
            println!("{long}   {short}   {n}");
        }
    }
}

缓存向量的尝试代码 #

有评论者建议我尝试逐个保存向量以消除while循环，但由于while循环远小于外层for循环，我认为减少外层循环次数更有价值。我已尝试实现该方案，但在所有可运行的范围内速度都慢得多。从数学角度看，此代码与前一代码完全等价，即输出完全相同。我了解.clone()调用开销较高，但对*和&的使用不够熟悉，无法在不使用.clone()的情况下编译通过：

fn main() {
    let mut base250known: HashMap<u64, ArrayVec<u8>> = HashMap::from([(0u64,ArrayVec::new())]);
    let mut base288known: HashMap<u64, ArrayVec<u8>> = HashMap::from([(0u64,ArrayVec::new())]);
    for n in 1..18446744073709551615u64 {
        let mut check: bool = true;
        if n%250-33 < 96 {
            match base250known.get(&(n/250)) { 
                Some(old) => {
                    let mut new = old.clone();
                    new.push((n%250-1).try_into().unwrap()); 
                    base250known.insert(n,new);
                    },
                None => { check = false; }
            };
        } else { check = false; }
        if n%3==0 {
            match base288known.get(&(n/288)) {
                Some(old) => {
                    let mut new = old.clone();
                    new.push((n/3%96+32).try_into().unwrap());
                    base288known.insert(n,new);
                },
                None => { check = false; }
            };
        } else { check = false; } 
        if check { if base250known[&n].iter().zip(base288known[&n].iter().rev()).filter(|&(a,b)| a==b).count() >= 0 {
            let long:String = base250known[&n].iter().map(|&c|{if c == 127u8 {'¶'}
                                                                else if c == 32u8 {'█'}
                                                                else {c.try_into().unwrap()} }).collect();
            let short:String = base288known[&n].iter().rev().map(|&c|{if c == 127u8 {'¶'}
                                                                    else if c == 32u8 {'█'}
                                                                    else {c.try_into().unwrap()} }).collect();
            println!("{long}   {short}   {n}");   }   }   }   }

内容的提问来源于stack exchange，提问作者user23090748