プログラミングのお題スレ Part22 (857ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
27: デフォルトの名無しさん [sage] 2023/08/11(金) 02:52:08.14 ID:45O+1i6X(1) AAS
そう、haskellの評価戦略はcall by need (の一種) で必要に応じて展開される、head . sort では 「sortした後の最初の項」を求めているのでそれを出すための必要最小限の事しかしない
件のData.Listにおけるsortでは
①与えられた列を1回目のバスで広義単調増大列いくつかに分割する、コストはO(n)
②できた列を２つずつマージして広義単調増大列の個数を半分にする、全部やればコストはO(n)
③②を列の数が1になるまで繰り返す、コストはO(log(n))
で全部の処理を要求してもO(nlog(n))でいわゆるクイックソートと同じコスト
しかしheadがこのsortの処理を呼ぶ時にはmergeする2列の中の最小値だけ残されてあとは捨てられる、なので最初の①の結果が最悪のケース、長さ1の列がn個できた場合でもmerge処理は最大n-1回だけ行われて終了する、すなわち事実上minimumと一緒
じゃあminimumBy ( on length )でいいじゃんという話なのだけど「遅延評価を利用すればほとんどコストレスでminimumByと同様の事ができる」というのがHaskellの面白いところ
なのでそっちを採用
これは遅延評価の文化に慣れてないと中々わからない
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 1.447s*