Longest Increasing Subsequence
O(nlogn) なアルゴリズムも書いてある
chmod には -R オプションという再帰的に処理するオプションがあるが、なんでディレクトリだけという指定がないのだろう？ (また、ディレクトリ以外、というのも)
なんか考えれば考える程そこにないのは奇妙な気がする
... さらによく探したら、X という指定があることに気がついた。うぅむ、しかしこれだけでは
FSIJ の月例会の話者を募集しようという話を相談する (いままではとくに募集していなかった)
とりあえず、今月末の月例会の案内をそろそろ流すので、その案内に募集を入れることになった
もし即座に応募があれば、9月の月例会 (9/14) に入れられるが、さて、応募はあるか?
フリーソフトウェア関連についての話ならなんでもいいのだが、どうなることやら
募集したらどうか、というのは一応わたしの案なのだが、応募がなかったらどーしよっかなぁ
ここしばらく、chkbuild をいじくりまわしていた。
この実装のいいかげんさは結構なもので、普段だったら投げ捨てて再実装するところだが、すでに autobuild -> chkbuild で一回再実装した結果がこのざまなうえに、実際に運用している都合上それなりに互換性というかせめて新旧の対応がつくと便利なので、今回は refactoring でどうにかすることにした。
結果、なんというかコードがどんなにひどくてもなんとかなるもので、ある程度ましな構造になった気はする。で、(デバッグのために) build せずに title を生成する機能をつけることもできた。
速くて小さい記憶領域と、遅くて大きな記憶領域があるとしよう。キャッシュとメモリと考えてもいいし、メモリとディスクと考えてもいいし、あるいはレジスタとキャッシュと考えてもいい。
入力(と出力)が小さい方には入りきらず、大きい方にはいっているとしよう。また初期状態において、小さい方は空だとしよう。
あと、出力を全部求めるためには入力を全部読まなければならないとしよう。
さて、この場合、処理が終わるまでには大きい方から入力を全部読み込まなければならない。それだけの時間はどうしても必要になる。
そして、入力を読んでいる間、小さい方や CPU はそれなりに暇である。その暇の中で処理を全部済ますことができるのであれば、その処理はそれ以上高速化できない。
その限界の速度を出すためには、処理中に必要な中間状態を小さい方の中だけで表現できることと、中間状態の更新速度が入力の到着速度を上回ることが必要である。
この限界速度をどうにかすることを考えると、まぁ本質的には避けられないわけであるが、いくらかは工夫することができる。
まず、遅い方にはシーケンシャルにアクセスすることである。これはとくにディスクに顕著であるが、シーケンシャルアクセスはランダムアクセスよりも速いということがある。メモリについても、シーケンシャルにアクセスすればプリフェッチがうまくはたらくかもしれない。
また、それでも CPU が暇になる、というのであれば、データを圧縮することが考えられる。遅い方に格納しておくときにはデータを圧縮しておけば、同じ速度で読み出すにしてもより多くの情報を読み出すことができる。
たまに、host コマンドが動かないことがある。
% host www.codeblog.org ;; connection timed out; no servers could be reached
これは DNS が動いていないのであればべつにおかしくないのだが、DNS 自体は動いていて、telnet では名前解決できる。
% telnet www.codeblog.org 80 Trying 211.14.6.122... Connected to www.codeblog.org. Escape character is '^]'.
まず、strace でたどる。
% strace host www.codeblog.org
...
rt_sigaction(SIGHUP, {0xb7c6f0d0, ~[RTMIN RT_1], 0}, NULL, 8) = 0
rt_sigsuspend([];; connection timed out; no servers could be reached
<unfinished ...>
--- SIGTERM (Terminated) @ 0 (0) ---
<... rt_sigsuspend resumed> ) = -1 EINTR (Interrupted system call)
sigreturn() = ? (mask now [HUP INT TERM])
...
んー。ソケットまわりが出てこない... あー、子プロセスになってるのか。
% strace -f host www.codeblog.org
...
[pid 10801] sendmsg(20, {msg_name(16)={sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.0.1")}, msg_iov(1)=[{"\31\264\1\0\0\1\0\0\0\0\0\0\3www\10codeblog\3org\0\0\1"..., 34}], msg_controllen=0, msg_flags=0}, 0) = 34
...
sendmsg で送ってるようだ。
% strace -fe sendmsg host www.codeblog.org
Process 10816 attached
Process 10817 attached
Process 10818 attached
[pid 10816] sendmsg(20, {msg_name(16)={sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.0.1")}, msg_iov(1)=[{"YS\1\0\0\1\0\0\0\0\0\0\3www\10codeblog\3org\0\0\1"..., 34}], msg_controllen=0, msg_flags=0}, 0) = 34
[pid 10816] sendmsg(21, {msg_name(28)={sa_family=AF_INET6, sin6_port=htons(53), inet_pton(AF_INET6, "::1", &sin6_addr), sin6_flowinfo=0, sin6_scope_id=0}, msg_iov(1)=[{"YS\1\0\0\1\0\0\0\0\0\0\3www\10codeblog\3org\0\0\1"..., 34}], msg_controllen=0, msg_flags=0}, 0) = 34
[pid 10816] sendmsg(20, {msg_name(16)={sa_family=AF_INET, sin_port=htons(53), sin_addr=inet_addr("127.0.0.1")}, msg_iov(1)=[{"YS\1\0\0\1\0\0\0\0\0\0\3www\10codeblog\3org\0\0\1"..., 34}], msg_controllen=0, msg_flags=0}, 0) = 34
[pid 10816] sendmsg(21, {msg_name(28)={sa_family=AF_INET6, sin6_port=htons(53), inet_pton(AF_INET6, "::1", &sin6_addr), sin6_flowinfo=0, sin6_scope_id=0}, msg_iov(1)=[{"YS\1\0\0\1\0\0\0\0\0\0\3www\10codeblog\3org\0\0\1"..., 34}], msg_controllen=0, msg_flags=0}, 0) = 34
;; connection timed out; no servers could be reached
[pid 10815] --- SIGTERM (Terminated) @ 0 (0) ---
Process 10816 detached
Process 10818 detached
Process 10817 detached
Process 10815 detached
んー、127.0.0.1 と ::1 にしか送ってない。
resolv.conf にはちゃんとサーバを指定してあるのに。
% cat /etc/resolv.conf search nameserver 192.168.2.1
resolv.conf をいじってみる。
search が空なので消してみると動いた。
% cat /etc/resolv.conf nameserver 192.168.2.1 % host www.codeblog.org www.codeblog.org has address 211.14.6.122
search の行末に空白を入れてみると parse failed になる。 (もともとは入っていなかった)
% cat -e /etc/resolv.conf search $ nameserver 192.168.2.1$ % host www.codeblog.org host: parse of /etc/resolv.conf failed
ぬぅ。
ところで、resolv.conf は dhcp で生成されている。
生成するスクリプトは /etc/dhclient-script であるが、もともとは以下のところにあるようだ。
https://www.codeblog.org/gonzui/markup/dhcp-2.0pl5/client/scripts/linux
resolv.conf は以下の所で生成されている。
dhcp-2.0pl5/client/scripts/linux:130-133
130: echo search $new_domain_name >/etc/resolv.conf 131: for nameserver in $new_domain_name_servers; do 132: echo nameserver $nameserver >>/etc/resolv.conf 133: done
$new_domain_name が定義されていないか空であると、search が単独ででてくるようである。
ここで $new_domain_name はクォートされていないので、ワード分割が適用され、空なのでワード自体がなくなり、echo には search というワードだけが渡され、search の直後に改行がでてくる。
なので、parse failed にはならない、と。
chkbuild で、svn を使ったときに出す ViewVC へのリンクについていろいろ考える。
うぅむ。move があるせいでいろいろムズい。
Note PC を 24時間稼働させておくときに、リモートから (計画的な) 停電に対応するにはどうしたらいいか？
停電前に shutdown するよう at でしかけておくのはいいとして、停電後に自動復旧させるにはどうしたらいいか？
あるいは、Note PC でなくても UPS がある場合でも。
バッテリを抜いておく？ UPS を使わない？
うぉ、Dell のバッテリのリコール対象に引っかかった。
Wake-On-LAN はたしかに一案です。
etherwake を入れて試してみましたが、たしかに起動します。
ただ、そういう Note PC が 2台あって、1台はそれで済むんですが、もう 1台は同じネットワークに送出できるマシンがないんだよなぁ。
ssh で特定のユーザを chroot させる方法について調べる
Securing Debian Manual - Chroot environment for SSH
うぅむ、PAM はよくわかってないので避けたい。パッチをあてるのは手間の点から却下。
そのユーザの (/etc/passwd における) uid を 0 にするのもいやとすると、そのユーザになってからどうにかして root 権限を得ないと chroot できない。
というわけでどこかに setuid-root なプログラムが必要なのだが、さりとて自前で setuid-root なものを自分で書くのはいやだし、sudo と chrootuid を組み合わせてみるか...
Debian Bug 383559: "host" timed out with empty "search" directive in resolv.conf
chkbuild で ruby を作ったときに、builtin なメソッドのリストを出すことにする。
これで、diff を見張っていればメソッドの増減を見逃すことはなくなるかもしれない。
chkbuild で、subversion からとってきたときに対応する ViewVC の URL を出す、というのをしばらく前からいじっているのだが、svn status -v の挙動に納得できないものがあったので尋ねたのだが、どうも修正困難な模様
<URL:http://subversion.tigris.org/servlets/BrowseList?list=dev&by=thread&from=504673>
Debian Bug 322860 dhcp-client: dhclient-script breaks resolv.conf is $new_domain_name is undefined/empty
うぅむ。dhcp-client 側で報告されていたか。
の項を上から下まで読んでみた。
いろいろと発見がある。
あーつーいー
ので、ついクーラーを買ってしまった
<URL:http://www.sanwa.co.jp/product/syohin.asp?code=TK-CLN3&cate=1>
メモリ使用量 (の最大値) を調べるプログラムを作る (Linux で)
% ./procmemsize sh -c 'sleep 1; /bin/sleep 1; ruby -e "sleep 1"; perl -e "sleep 1"' sh (25138): VmData=724kB VmExe=648kB VmHWM=1604kB VmLck=0kB VmLib=1636kB VmPTE=12kB VmPeak=5264kB VmRSS=1604kB VmSize=5264kB VmStk=88kB sleep (25139): VmPTE=16kB sh (25138): VmHWM=1608kB VmRSS=1608kB ruby (25141): VmData=748kB VmExe=820kB perl (25142): VmExe=1016kB VmData: 748 kB VmExe: 1016 kB VmHWM: 1608 kB VmLck: 0 kB VmLib: 1636 kB VmPTE: 16 kB VmPeak: 5264 kB VmRSS: 1608 kB VmSize: 5264 kB VmStk: 88 kB
/proc/*/status を定期的に scan して、起動したコマンドおよびその子孫を調べ、VmXXX それぞれについて最大値が更新されたら表示する。あと最後に全部表示する。
しょせん定期的 scan なので、scan の間に大量にメモリを消費してすぐに終わってしまうプロセスは観測できないが、まぁしかたない
また、親が死んで init にひきとられたプロセスもわからないが、これもまたしかたない
ruby のビルドに適用すると、dl のところでの消費がきわだって多いことがわかるのは予想通りであるが、まぁ、そういう相対的なのはともかく、絶対的な値がわかるのがおもしろい。
・ 親プロセスから継承されない ・ 変数とかの展開結果にしか適用されない
買ったクーラーであるが、これはファンにより空気の流れを作るものである
ここで思ったのであるが、これをクーラーと呼ぶのであれば、普通の扇風機もクーラーと呼ぶべきではないだろうか
SSL のクライアント証明書について (たいして調べもせずに) いろいろと想像してみる。
勝手に想像したところから思うに、期限と失効の扱いが面倒？
東京駅の京葉線ホームにいってみる
たしかに遠い
SPA の夜のセッションでいろいろと議論した
議論中に思い付いたのだが、サッカーの中継の動画の中からシュートの画面を検索するのに、2ch の実況を「シュート」で検索してその時刻の画面を表示する、というアイデアはなかなか
一般化すると、時刻情報はやはり強力、というところか
シェルの入力としては以下のものが考えられる
・ コマンドライン引数 ・ 環境変数 ・ 標準入力
ここで、コマンドライン引数と環境変数はシェル変数として参照される。また、標準入力も read ビルトインでシェル変数に代入される。
なのでシェルにおいては結局シェル変数に入力が入ることになる。
そして、シェル変数は $xxx などと書いて使用するわけであるが、その結果は (クオートされていない場合) 以下の展開フェーズが適用される。
1. ワード分割 2. パスネーム展開
展開された結果は、コマンドライン引数として他のコマンドに渡されたり、他の変数に代入されたりする。 (変数代入の右辺ではワード分割されないとかいろいろな話があるが)
シェルのコマンドは (いくらか単純化すると) 次のような構造になっている
var=val command arg >redirect <<heredoc
"var=val" という形で変数代入があり、 "command arg" の形でコマンド名とコマンドライン引数があり、 "> redirect" の形でリダイレクトがあり、 "<<heredoc" の形でヒアドキュメントがある
これらの場所によっては適用されない展開フェーズもあるが、一般には以下のフェーズがある
1. ティルド展開 2. パラメータ展開, コマンド置換, 算術展開 3. ワード分割 4. パスネーム展開 5. クオート除去 ・ command arg ではこれらのすべてが適用される。 ・ val, redirect ではティルド展開、パラメータ展開、コマンド置換、算術展開、クオート除去が行われる ・ heredoc ではクオート除去が行われる
(redirect では、対話的シェルでは、パスネーム展開も行われるかもしれないし、行われないかもしれない。非対話的では行われない)
まぁ、heredoc が変わるとヒアドキュメントの範囲が静的に決まらないのでクオート除去だけというのはよくわかる
val, redirect は複数の単語に分かれると困るので、ワード分割、パスネーム展開がおきないのもわかる
[latest]