[Memo] 最近の疑問

  • 代数的変形による効率の向上を当てにして(予測して)プログラミングできるのか
  • 自動的な最適化(ヒューリスティックを含んでもよい)の結果がプログラマによる最適化(問題を「理解」して解く)の結果よりも優れた効率のプログラムを生むことがあり得るが、そのようなプログラミングは「統制」できるだろうか。
    • メンテナンス(最適化後のコードはわかりにくく、最適化前は速度のオーダーが違う)
    • 修正する度に予測不可能なパフォーマンスの変動がありうる

最大部分列和問題

Haskell

「与えられたリストの連続する部分列の内、和が最大となるものを求め、その和を返せ」というプログラムを書け
http://d.hatena.ne.jp/yokoyamatetsuo/20050224/p2

solve = maximum . candidates . preproc

preproc = map sum . groupBy (((>= 0).) . (*)) . dropWhile (<= 0)

-- [+,-,+,...] という入力を仮定
candidates (x:y:z:cs) = x:candidates (s:cs)
  where	s = if x + y + z > z then x + y + z else z
candidates (x:_) = [x]
candidates [] = [0]
Re:http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tdiary/?date=20050223#p05

5行目が違うと思います。g [-1,1]とか。

g xs = f xs ([], 0) ([], 0)
f (x:xs) (ys, sy) (zs, sz)
  | x < 0 = if sy > sz then f xs (x:ys, x+sy) (ys, sy)
                       else f xs (x:ys, x+sy) (zs, sz)
  | True  = if sy < 0  then f xs ([x], x)      (zs, sz) -- Corrected
                       else f xs (x:ys, x+sy) (zs, sz)
f []  (ys, sy) (zs, sz) = if sy > sz then reverse ys else reverse zs

Examples

Haskell

CPS, Continuation Monad, and Writer Monad の例。

part :: (a -> Bool) -> [a] -> [a]
part p l = let f []     z = z
               f (x:xs) z = if p x then x : f xs z
                                   else f xs (z++[x])
            in f l []

をいろいろに書いてみる*1。

*1:[id:yokoyamatetsuo:20050219#p5]より

続きを読む

CGIデバッグ用shスクリプト

1

#!/bin/sh
echo -e "Content-type: text/plain\n"
env

2

#!/bin/sh
decode () {
  awk 'BEGIN { RS = "&"; FS = "=" } {print $1 " = {" $2 "}\n"}' \
    | /usr/local/bin/urldecode -p 
}
echo -e "Content-type: text/plain\n"
env
echo -e "\n-- Get data --"
echo -n $QUERY_STRING | decode
echo -e "\n-- Post data --"
decode

urldecodeは/usr/ports/net/urlendecより。

><

関数型shスクリプトによる掲示板 

#!/bin/sh
DATAFILE="data/bbs.txt"
cat >> $DATAFILE; echo "" >> $DATAFILE
cat << EOF
Content-type: text/html

<html><body><form method="post" action="$SCRIPT_NAME">
<textarea name="msg" rows="5" cols="80"></textarea><br/>
<input type="submit" name="write" value="Write"/>
</form>
EOF
cat $DATAFILE | sed '1!G;h;$!d' \
    | sed 's/.*msg=\([^&]*\).*/<hr\/><pre>\1<\/pre>/' \
    | /usr/local/bin/urldecode -p
echo '</body></html>'

forとかつかわずにパイプで。