プログラミングのお題スレ Part22 (863ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

309(1): デフォルトの名無しさん [sage] 2024/03/10(日)20:08 ID:6qxPF4Wx(1)
2pass案は多少工夫したらかなり速い

n ␣␣m ␣296␣ ␣301-1 ␣301-2 ␣303␣ ␣2pass
5k␣␣5 ␣ 0.5s ␣ 0.1s ␣ 0.5s ␣ 0.4s ␣ 0.1s
25k ␣5 ␣12.7s ␣ 2.5s ␣13.9s ␣11.1s ␣ 1.7s
100k␣5 ␣3m52s ␣49.3s ␣4m13s ␣3m26s ␣38.9s
1M* ␣6 ␣8h23m ␣2h50m ␣8h51m ␣6h43m ␣1h11m
*n=100万は1万サンプルの部分ループ500k≦r＜510kから100倍

>>301の296と301-2の比較記述と違う傾向があるのはキャッシュ階層の違いだと思う
2passは301-1に近いけど1pass目でのランダムアクセスサイズを落としながらも
誤判定率を低く抑える(0.2%～2%)工夫をするのがお楽しみだと思う

---

314: デフォルトの名無しさん [sage] 2024/03/31(日)11:57 ID:enek7T1c(1/2)
大幅に手直しした
特に前回数値が一部出てこない状態になっていたので色々と手動で最適化した
新しいアイディアを思いつかない限りはシングルスレッドでの限界に近いと思う

n m 301-1 303 2pass 2pass'
5k 5 0.1s 0.4s 0.1s 0.1s
25k 5 2.5s 11.1s 2.3s* 1.7s
100k 5 49.3s 3m26s 38.9s 27.7s
1M* 6 2h50m 6h43m 1h11m 48m10s
2M* 6 17h06m 28h27m 5h47m 3h13m
Max* 6 35h51m 51h23m 11h09m 5h47m

*前回>>309 2pass n=25kの再計測値
*n=1Mは部分ループ500k<=r<510kから100倍
*n=2Mは部分ループ500k<=r<505kから400倍
*Max:=2642245は3乗がUINT64に収まる最大
*n=Maxは部分ループ500k<=r<500k+3785から2642245/3785倍

ヒント含みの数値がこちら

n D1 D2 D3 = 5000 5001 5003 5009
false_positive = 23 / 5001 = 0.46%
total_t_pass1 = 64.220 ms 2.568 ns/iter
total_t_pass2 = 0.044 ms 0.381 ns/iter
real 0m0.097s

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

ぬこの手 ぬこTOP 0.049s