プログラミングのお題スレ Part22 (858ﾚｽ)
プログラミングのお題スレ Part22 http://mevius.5ch.net/test/read.cgi/tech/1691038333/
上
下
前次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
抽出解除
必死ﾁｪｯｶｰ(本家)
(べ)
自ID
ﾚｽ栞
あぼーん
27: デフォルトの名無しさん [sage] 2023/08/11(金) 02:52:08.14 ID:45O+1i6X そう、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の面白いところ なのでそっちを採用 これは遅延評価の文化に慣れてないと中々わからない http://mevius.5ch.net/test/read.cgi/tech/1691038333/27
ﾒﾓ帳
(0/65535文字)
上
下
前次
1-
新
書
関
写
板
覧
索
設
栞
歴
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
AAｻﾑﾈｲﾙ
Google検索
Wikipedia
ぬこの手
ぬこTOP
1.299s*