我试图写的代码是在很多值上完成的，我的代码做了大量的额外工作，我甚至不太确定如何在数学上描述我想跳过的值，因为随着i变得越来越大，我想跳过越来越大比例的i s。
用psudocode来解释是最简单：
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 s中的所有循环，只尝试适用于g(n)的第一个循环的值。最佳情况下，我想在while循环中根本不需要任何if语句，而是有一个只尝试成功值的范围。
基本上，我想问的是，是否有一种方法可以尝试更少的值，以便代码中的大O与91有关，而不是250和288（或者如果你能从最后的if中加入一些逻辑，并使它甚至低于91，那就太棒了）。我得到了正确的输出，但这需要很长时间。我正试图在尽可能大的范围内运行它;最终目标是将其运行到大约250^40==8.27e95==2^319.7的值，因此在需要运行函数之前确定哪些值是可跳过的将保存大量计算。
来帮助我理解我想要的价值观，我已经画了一个网格，只考虑g（n）的情况下有效值和较小的数字[n%2和floor(n/6)]。突出显示的全蓝色列是在这种情况下将通过的数字，突出显示的白色行是值被丢弃的点。n%3和floor(n/6)]
这是f（n）函数，但其中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}");
}
}
}型
一位评论者建议我尝试一次保存一个向量值以摆脱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}"); } } } }型
1条答案
按热度按时间vof42yt11#
这是一个自我回答，而且是一个糟糕的答案，但是我在技术上得到了代码来做我说我想要的事情。本质上，这使得第一次检查范围，所以每次while都会在原始代码中循环，我只是做了一个新的for循环。在创建范围之后，第二个检查变成了一个过滤器，我把它分成了第二个函数，位于代码的末尾。只要你创建了足够的循环来捕获整个范围，同样的代码。
字符串
代码是愚蠢的重复和非常长，所以我觉得它应该能够被重写为一个循环的形式
型
等等，但我不知道如何用rust来表达。我仍然欢迎更多关于加速的评论，特别是这里的检查：
型
因为我怀疑这是计算机正在做的大量工作。我只是想检查两个vec之间的相似性，如果你知道一个更快的方法来检查“接近但不一定精确”，即使它是这个概念的不同实现，我会非常感激。