Rust part31 (631ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
585(1): 07/30(水)15:55 ID:gxsH3v1Z(1) AAS
>>579
データが大きくても係数の差が次数の差より影響することは普通にありえる
キャッシュミスしまくるがO(n)で済むアルゴリズムと
ほぼキャッシュヒットしまくるがO(n·log(n))かかるアルゴリズムがあるとしよう
両者のアルゴリズム自体の係数差は単純にnとn·log2(n)とする
例えばn＝2^30≒10億の場合はアルゴリズムの差でlog2(2^30)＝30倍の差が生じる
ところがキャッシュミスするとメモリアクセスの差で300倍遅いことが現代のCPUでありえる
そのためキャッシュミスしまくるO(n)よりもO(n·log(n))が速く実行されることが起きる
587: 07/30(水)16:28 ID:zYz0+G1r(2/4) AAS
>>585
はいはい
計測してからほざけ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.261s*