2008/12/02

らむ太語録。

昼寝せずに遊んでいたせいで夕方はやいうちに眠ってしまい、夜中の2時に目を 覚まして遊び始めた。

• かみさん：もうねんねしなさい！
• らむ太：らむたはおしごとです。ちょっとあっちいっててください。

お父さんは寝たくなくて仕事してるわけじゃないんだよ、息子よ。

Tag: 生活

2008/11/30

ループ検出(2)

おお、昨日の話題をいけがみさんより丁寧な解説が。 確かに「木の循環」は変ですね。有向グラフにサイクルがあるかどうかの判定という ことですね。

O(m+n)の全走査アルゴリズムだけど、隣接グラフか行列を走査するにつれ マークしてく必要はやっぱりあるのですよね。

TAOCPの4巻で カバーされるんだろうか。このへんは。

(追記2008/11/30 19:13:09 PST):

Korte-Vegen の教科書によれば、topological sorting は TAOCP(Knuth, D.E. "The Art of Computer Programming; Vol.1; Fundamental Algorithms, Addison-Wesley, Reading 1968 (3rd ed. 1997) に言及されているとのことです。

ああ、topological sortingについては確かに1巻にありました。 Gaucheのutil.toposortモジュールはそのままTAOCPのやつを実装していたような。 うは、それでまさに循環が検出された時には "graph has circular dependency" ってエラーを出すようにしてる。 これそのまんまで良かったんだ。 入力形式が違っても同型になる問題に気づくってことは大事なのですなあ。

Tags: Programming, Gauche

2008/11/29

ループ検出

リンクつきリストにループ部分があるかどうかを確かめる - ときどきの雑記帳

最後の "Best solution" にあげられてる「うさぎと亀」は あらゆるLisp/Scheme処理系で使われていると思う。list?は 循環リストについても停止しないとならないため。 (CLのlistpは最初のペアしか見ないのでちょっと違うが、 lengthなどは循環リストを検出しないとだめ)。

難しいのはcar方向にも循環する場合、つまり木の場合で、 これはvisitした全ノードを何らかの方法で区別する (マークをつける、 ハッシュテーブルに記録する、みつけたものから移動してゆく、など) しかないと思うのだけれど、もっと効率の良い方法はあるのだろうか。

循環がある場合も停止する必要はあるけれど、必ずしもタイトに循環を検出しなくても良い、 という用途はあって、その場合は適当なところまで循環を気にせずに処理を進めて 怪しくなったら循環検出モードに切り替える、という手はある。 Adams&Dybvigのr6rs equal?実装とか。

(追記2008/11/30 01:47:30 PST): 木の循環検知、こんな感じだとどうでしょうか？

木の場合も結局、「何とか優先」で順番に辿るわけなんで、うさぎを作っちゃうという考え方です。

なるほど。考え方としてははたと膝を打った。ただ全ノード記録に比べて良いかどうかは疑問。

空間計算量については、全てのノードについて非末尾再帰が入るからO(D) (D=非循環部分の木の深さ)。 ランダムな木だとだいたいO(D) = O(logN) とみなせるかなあ。 で、リストに対する亀とうさぎ (空間計算量O(1)) にはかなわないけど、 全ノードを記録する (空間計算量O(N) (N=ノード数)) に比べればかなり良い。

ところが、このアルゴリズムは全ノードについて探索が2分岐するから 時間計算量はO(2^N)になる。全ノードを記録する場合はO(N)。 Nの上限がわりと小さい値であって、空間計算量をケチりたい場合くらいにしか使えなさそう。 (訂正：O(2^N)にはならない。上記リンク先の追記参照。)

(追記2008/11/30 02:58:44 PST): miuraさんの解にヒントを得た。 時間計算量が爆発するのはうさぎが増えまくるからで、 あくまで一匹を追いかけるようにすればよい。つまり木の全ノードの列挙を シリアライズしてその列について亀とうさぎを適用すればいいわけだ。 ちょっとsamefringe problemに似てる。遅延ストリームを使ってみるが、 samefringeと同じように、コルーチンとか継続渡しでも書けるはず。

(use util.stream)

(define (acyclic-tree? t)
  (define (traverse tree)
    (stream-delay
     (if (pair? tree)
       (stream-append (stream tree) (traverse (car tree)) (traverse (cdr tree)))
       (stream tree))))

  (let1 str (traverse t)
    (or (stream-null? str)
        (let loop ((tortoise str)
                   (hare     (stream-cdr str)))
          (cond [(stream-null? hare) #t]
                [(stream-null? (stream-cdr hare)) #t]
                [(eq? (stream-car tortoise) (stream-car hare)) #f]
                [else (loop (stream-cdr tortoise)
                            (stream-cddr hare))])))))

どうかな?

あ、だめだ。

gosh> (acyclic-tree? '((a . #1=(c . d)) #1#))
#f

そうか、部分共有があるとeq?なノードに出会ってしまうんだ。 だから元の木構造の情報を失ってしまうと間違える。 ということは各ノードへの元の木構造のパスをストリームの各要素とする? むー、結局余分な空間を食いそうだが…

やっぱだめだ。パスの等価性判定のところで循環を考慮した比較が必要になるので 堂々めぐりだ。

まてよ、全ノードマークっていうのも勘違いしてたかも。全トラバースしてハッシュテーブルに 登録してゆく方法だと上のように部分共有があるケースを循環と間違える。 マークするのは各パス内だけ (現在いるノードからルートまでが見える状態) にしとかないと。 そうすると、ハッシュテーブルは使いづらい。リストを使うとして時間O(N・D)、 空間O(D)か?

Tags: Programming, Gauche

2008/11/27

「御社が第一志望です」

Exploding Offer Season - Joel on Software

You ace the interview, of course. They make you an offer.

“That sounds great,” you say.

“So, when can you let us know?”

“Well,” you tell them, “I have another interview coming up in January. So I’ll let you know right after that.”

“Oh,” they say. “That might be a problem. We really have to know by December 31st. Can you let us know by December 31st?”

Tada! The magnificent “exploding offer.”

新卒就職者に対するJoelのアドバイス。企業のリクルータはオファーを出した後、 あなたを他の企業に取られないようにするために、他社の面接の結果が分かる前に 返事をさせようとする。そんな「時限付き内定」をもらった時にどうすべきか。

Joelの言っていることは至極まっとうなことなんだけれど、おもしろいと思ったのは、 きっと日本の「新卒就職活動」ではこういうアドバイスはまずなされないだろうなってところ。

Joelのアドバイスは原文を読んでもらうのが一番だけど、ざっと要約すると

• そもそもそのようなオファーはunethicalである。
• だからまずは返事の期限を伸ばしてもらうように押すべき。 ほとんどの会社はそれで気を悪くするようなことはない。 むしろ、あなたを他の会社も狙っているとわかった後の方があなたを欲しがるはず。
• どうしても期限を伸ばしてもらえないなら、期限ぎりぎりに口頭でのみ返事をしておく。 契約書にサインしてはいけない。そして別の会社の面接を受けにゆくべき。
• オファーを受けといて後で蹴るのは非常に失礼だと思うかもしれない。 それは確かにそうなんだが、他の面接を受けさせないための時限付きオファーというのは そういう学生の倫理観を利用しているのだ。交渉の結果どうしても期限を伸ばしてもらえなかった というケースに限り、蹴るのは止むを得ない。

私はこのような態度は企業にとっても学生にとっても極めて健全だと思うが、 どうも日本の新卒就職活動の現場では、 そもそも就活が「当事者間の契約交渉である」という意識自体薄いという気がしている。 いわゆる新卒就活をやったことがないので単なる気のせいかもしれない。 けれど、例えば「面接で『第一志望か』と聞かれたらもちろんはいと答える」みたいな アドバイスをたくさん目にすると、気のせいではないと思われるのだ。

何でも米国風にするのが良いと言うつもりは全く無いが、 日本のこの就活における奇妙な空気は、「これが日本の文化だから」と 守るようなものではないと思う。 就職あるいは採用活動を大事にとらえるならなおさら、 その場で不誠実になることを称揚するアドバイスが蔓延するのは害にしかならないだろう。

(なお、「誠実になる」というのは何も「御社はすべり止めです」と答えるのが良いという ことじゃない。あなたにその会社に入る気があるということは、少なくともある程度の期間に わたって会社にあなたの人生の多くを預けても良いと既に思っているってことだから、 素直にそう答えればいい。「第一志望」「第二志望」「すべり止め」という考え方自体が おかしいのだ。就職活動は受験ではない。 一定のルールのもとでゲームをして順位を決めるものではなく、 どうすればお互いにメリットを得られるかという落としどころを探す社会的な活動なんだから。)

Tag: Career

2008/11/26

Acting classの先生のことば：

Often, a mark of an inexperienced actor is a tendency of giving suggestions to other fellow actors. So, if you absolutely need to offer a suggestion or a criticism to your fellow, do that with most respect and humility. Never, ever assume you know more.

Tag: 芝居