我正在try 编写在很多值上完成的代码，而我的代码正在做大量的额外工作.我甚至不太确定如何从数学上描述我想跳过的值，因为随着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)，这样在命中丢弃时就不需要运行g(n)了.我正在寻找的是一种定义范围的方法，类似于.step_by(3)如何只try 对while中的所有循环的第一个循环g(n)有效的值.最好，我希望while循环中根本不需要任何if语句，而是有一个只try 成功值的范围.
基本上我想问的是，有没有办法try 更少的值，这样代码的大O与91有关，而不是250和288(或者如果你能从最后的if中加入一些逻辑，并使它甚至低于91，那就太棒了).我得到了正确的输出，但这需要很长时间.我试图在尽可能大的范围内运行它；最终目标是将它运行到250^40==8.27e95==2^319.7的数量级，因此在需要运行函数之前确定哪些值是可跳过的将节省大量计算.
to help me make sense of describing the values I want, I have drawn a grid for valid values only considering the g(n) case and with smaller numbers [n%2 and floor(n/6)]. the highlighted full blue columns are the numbers that would go through in this case and the highlighted white rows are the points where the values are discarded.
here's the same thing but with [n%3 and floor(n/6)]
here's the f(n) function but with 1<n%6<4
如果您想查看完整代码或推荐任何其他优化，您也可以在下面看到:
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}");
}
}
}
一位 comments 者建议我try 一次一个值地保存向量，以消除While循环，但由于While循环比for循环小得多，我认为更值得try 少做大循环.我试着实现它，但在我的计算机可以运行的所有范围内，它都慢得多；无论如何，如果你有什么建议可以加快它的速度，这里就是它.从数学上讲，这段代码与前一段代码完全相同.我见过有人说.clone()调用成本很高，但我对*和&的了解还不够多，无法在没有.clone()的情况下编译它
fn main() {
let mut base250known: HashMap<u64, ArrayVec<u8, 8>> = HashMap::from([(0u64,ArrayVec::new())]);
let mut base288known: HashMap<u64, ArrayVec<u8, 8>> = HashMap::from([(0u64,ArrayVec::new())]);
for n in 1..18446744073709551615u64 {
let mut check: bool = true;
if n%250-33 < 96 {
let mut old = match base250known.get(&(n/250)) { //get the value from the previous loop
Some(old) => old.clone(),
None => ArrayVec::from([255u8,255u8,255u8,255u8,255u8,255u8,255u8,255u8])
}; //max ArrayVec will never be set; we can use this to check if we hit a known value
if old != ArrayVec::from([255u8,255u8,255u8,255u8,255u8,255u8,255u8,255u8]) {
old.push((n%250-1).try_into().unwrap()); //add the new value
base250known.insert(n,old); //save it in the new spot
} else { check = false; }
} else { check = false; }
if n%3==0 {
let mut old = match base288known.get(&(n/288)) {
Some(old) => old.clone(),
None => ArrayVec::from([255u8,255u8,255u8,255u8,255u8,255u8,255u8,255u8])
};
if old != ArrayVec::from([255u8,255u8,255u8,255u8,255u8,255u8,255u8,255u8]) {
old.push((n/3%96+32).try_into().unwrap());
base288known.insert(n,old);
} else { check = false; }
} else { check = false; } //all these check=false s are to make sure we don't get an unassigned hash in this if
if check { if base250known[&n].iter().zip(base288known[&n].iter().rev()).filter(|&(a,b)| a==b).count() > 3 {
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}"); } } } } //inlining the close parens makes the scrollbar go away