プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
750(3): デフォルトの名無しさん [sage] 04/11(金)07:38 ID:oaeJuxMT(1)
>>738 に手を加えて10倍速くしてみた
fn solve(n: usize, limit: usize) -> Vec<usize> {
let mut answer = Vec::new();
let mut pnt = generate_primes(n).windows(2).rev().map(|s| (s[1], s[0], 0, 0)).collect::<Vec<_>>();
let (mut ci, mut cn, mut ct) = (0, n, 1_usize);
'advance: loop {
pnt[ci..].iter_mut().for_each(|(_p, _q, n, t)| (*n, *t) = (cn, ct));
if cn & 1 == 0 && ct.leading_zeros() >= (cn >> 1) as u32 {
ct <<= cn >> 1; if ct <= limit { answer.push(ct); }
}
'back: for (i, (p, q, n, t)) in pnt.iter_mut().enumerate().rev() {
'again: loop {
if *n < *p { continue 'back; }
*n -= *p; *t *= *p;
if *n ==1 || *t > limit { continue 'back; }
if *n == 0 { answer.push(*t); continue 'back; }
if *q > 3 {
let mut tt = *t * (*n % *q);
for _ in 0..(*n / *q) { tt *= *q; if tt > limit { continue 'again; } }
}; break 'again;
}; (ci, cn, ct) = (i, *n, *t); continue 'advance;
}; break 'advance;
}; answer.sort(); answer
}
752: デフォルトの名無しさん [] 04/11(金)22:44 ID:4wK2/GRg(1)
>>750
これはとても速いな。ローカルで実行してみたら、>>738のRustプログラムと比較して
2000万以下で16倍、20億以下で55倍の速さだった。
755: デフォルトの名無しさん [sage] 04/12(土)21:26 ID:csJOBVaF(1)
>>754
それに気づいたけど
まだ>>750と比べて20倍遅いからメモ化の方針が徒となってるのかな
761: デフォルトの名無しさん [sage] 04/17(木)00:32 ID:dz0qzhSq(3/3)
>>738
これも2025以下の素数を組み合わせて和が2025になる解を調べる方法。
解一覧を収めるベクタ以外は、固定の長さ305のベクタのみが使われている。
この長さの 305 とは2025以下～3以上の素数[2017, 2011, ... 5, 3]の数になってる。
各素数の冪乗の和 2017^e2017 + 2011^e2011 + ... + 5^e5 + 3^e3 及び積を計算していくが、
各指数のe2017などは解に不要なので使われておらず、
各冪乗の和自体も不要なので2025までの残りの数が使われていて、
固定長ベクタの値は(素数, 残りの数, ここまでの積)の3つ組となっている。
その素数を1つ使うと残りの数が減算されてて積が乗算されるのを繰り返していく。
素数2だけ特別扱いされており、残りの数の半分だけ左シフトすると解の積が出来上がる。
各if～continueが枝刈りとなっていて、残りの下限(=和の上限)や積の上限などがある
この改良版>>750では、次の素数以降の組み合わせで起き得る積の下限で枝刈りしている。
例えば7以下の素数で残り21ならば積の下限は7*7*7=343となるため、
ここまでの積に343を掛けた値が2000万(または20億)を超えていれば枝刈りできるようだ。
このアルゴリズムは作業メモリが固定で小さく常にL1キャッシュに乗り有利と思われる点と、
様々な枝刈りがしやすく処理する組み合わせを大きく減らしている点により、
他のアルゴリズムより桁違いに高速になっていると推測される。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.033s