週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

http://acm.ntnu.edu.tw/html/final_results.html
ICPC 台湾サイトに結果があがっていました。問題も載っています。

ところでfinal standingsはなぜ二年前なんでしょう.

スポンサーサイト

仮免許試験受けてきました。見極めのときは結構大変でしたが本番は何とか通過。学科で落ちるとかしてなければ合格で、来月は路上講習になります。年始には免許は取れているでしょう。

駒祭に行ってきました。知り合い遭遇コースを一巡。 遭遇したほとんどの知り合いに「久しぶりです」といっていました。 ちっとも久しぶりでない人にも「久しぶり~ではぜんぜんありませんね」とか言ってしまう始末。

柏葉の出演を聞きつつ、「上級生のステージが減ったかな」とか思っていました。よく考えたら「上級生」の線引きを間違えていただけでしたが。私は7年生7年生、と。

TSGでは同期に会えませんでしたがUTMCではなぜか知り合いに次々遭遇。にゃあさん以外のUTMCで知っている人殆どに会ったような気がします。にゃあさんは明日ICPC Regional@台湾ですね。

クリアしました。スコアはS:15489, K:8989, T:13650。

とりあえず最終面は音楽とか演出とかが楽しすぎます。最終面が練習できるようになってから、通しを無視してずっと最終面ばかりやっていました。おかげで最終面はあまりミスもなくクリアできました。一方6面や7面がひどいことに。それぞれで4機は失ったと思います。

もちろん6面や7面も楽しいです。こちらは楽しい上に難しいです。特に6面は厳しい。

次はDEAD-LIARです。こいつでクリアしないとストーリーがわかりません。

私の記憶に残っているタイピングソフトは、東大情報棟の計算機に入っていたtrrです。こちらはemacs上で動いていて、合衆国憲法か日本国憲法を文例として出題していました。実際の文章を使っているので単語列は奇妙なことにはなりません。しかし題材が題材なので言い回しが難しくて苦労しました。

今trrで検索したらtrr19 マニュアルがヒットしました。ちょっと読んでみましたが、「歴史」の項目にすごい記述が。

富士通の近山隆氏が初めてtrrをやってみたところ一発で500点以上をマークし(600点を越えていたという証言者もいる)

via もわ爛漫 v 3.0および val it : α → α = fun.

昨日あたりから、Speedtestなるタイピングゲームサイトがはやっているみたいです。ここのサイトで測ったタイピング速度を貼っている日記が散見されます。

上の二方も言及されていましたが、 このサイトでは、出題される単語がランダムです。隣接する単語間に関連がまったくありません。そのため、単語を入力しながら次の単語列のことを考えるのが難しく、通常に比べてタイピング速度が著しく遅くなる気がします。

そんなことよりむしろ以下の項目のほうが気になりました。

  • 時々こちらのタイピングに画面の処理が追いつかない。最終的には受け付けてくれるのでよいけど、ストレスです。
  • 出てくる単語が簡単すぎる気がします。

しかし、よく見たらこのサイトはjavascriptでできているんですね。ならどちらも仕方ないのかもしれません。単語もソースに手書きで書いてあります。


最後に自分の結果を貼ってしめます。

You reached 253 points, so you achieved position 29644 on the ranking list
You type 363 characters per minute
You have 61 correct words and
you have 1 wrong words

gwtのツールキットにはSuggestBoxがあります。これは一見普通のテキストボックスですが、文字入力するとgoogle suggest並に候補リストが出ます。

gwtのサンプルにSuggestBoxがあったので、とりあえず試してみました。

h → hammer, haskell

何でhaskellが。

てっきりリアルにgoogleの入力履歴でも見ているのかと思って、どうすればgoogleのapiが呼べるのかとソースコードを確認してしまいました。

private static final String[] words = new String[] {
    "1337", "apple", "about", "ant", "bruce", "banana", "bobv", "canada",
    "coconut", "compiler", "donut", "deferred binding", "dessert topping",
    "eclair", "ecc", "frog attack", "floor wax", "fitz", "google", "gosh",
    "gwt", "hollis", "haskell", "hammer", "in the flinks", "internets",
辞書でした..

今回はまず沼に、ついでエルフの大広間に行ってきました。どちらも首尾よく最後まで到達。

沼は前のときよりレベルが上がっていたので楽でした。実際通常よりも少し高めのレベルで挑戦していますし。苦戦した希薄な霧も大体通常攻撃で倒せます。 一方沼ドラゴンとヒドラには苦戦しました。ヒドラは前回と同じように召換で倒すので、召換したネズミが沼ドラゴンや沼ドレイクのブレスで死なない様にヒドラをすでに制圧した階に誘導して倒しました。失敗してバーサークと炎のシミターで倒したことも何度もあります。一方沼ドラゴンは楽勝だと思ったのですが、こちらの直接攻撃での火力が不足するため大体バーサークをかけないと倒せませんでした。

いずれにせよ特に何もせずにルーンを取得。それから必需消耗品である怪我の治療薬と瞬間移動の巻物をいくつか拾いました。収穫です。

沼の次はエルフの大広間に。こちらもなぜか問題なくすんでしまいました。エルフの大広間7階は宝物庫最終階と同じくらい危険で、通常ダンジョンを27階くらいまで降りられないと挑戦できないというだという認識があったのですが。

戦法はすべからく静寂。闇エルフの戦士や兵士ですら静寂で。

  1. 飛来物の防御と再生を常備しておく
  2. 接敵したら静寂
  3. 釣って通路で各個撃破。
    • 画面端の敵には静寂が効いてないことに注意。離れすぎないように。
  4. 撃破したら休息するなどで静寂を解除
静寂は闇エルフの術師に有効なだけでなく、戦士系にも補助魔法を封じるので有効です。 加速や瞬間移動を使えなければ、闇エルフの騎士といえどもオークの騎士よりも弱い雑魚と化します。

7階もほぼ同じ戦法で。7階の大広間は危険なので、私はちょっと大広間から顔を出しては敵を釣って通路で倒すという方法を取りました。また、戦闘が終わったら、エルフの死体はすべて解体しました。残しておくと闇エルフの死の魔術師に不意を突かれるとすべてゾンビになります。危険です。

上記の戦法で、エルフ7階の広間はすべて制圧できました。つまり、エルフの宝物がこのタイミングで手に入りました。収穫は以下のとおり

  • 保全の護符
  • 悪食の護符
  • 早業のシミター
    • ルイーズが落としたのかもしれません.
  • 神罰のグレートソード
  • ☆指輪 r火
護符が非常にありがたいです。早業のシミターもかなりの戦力アップになりました。

今回は結構深くまでもぐりました。メインを22 F, 宝物庫を4 Fまで降り、その過程でラビリンスをひとつ見つけるなど、多くの収穫がありました。

前回は力不足だった小動物の召換が今回非常に役に立ちました。バーサークしてやっと倒せるかどうかだった上級トロルやそのゾンビ、ストーンジャイアントやストームドラゴンのスケルトンなども、ネズミとコウモリで囲めば安全に倒せます。さらにはセントールやヤクトールに対する障壁にもなります。

しかし一回ドラゴンと遠距離で遭遇して死に掛けました。ドラゴンの炎は貫通するので、召換ではあまり防げません。

収穫は☆レザーアーマー[r冷毒]。これで指輪枠がひとつ空きます。ドラゴンが怖いので耐火の指輪をつけました。 それから魔法書が大量に手に入りました。

  • 猛火の魔法書
  • まじないの魔法書
  • 炎の魔法書
  • 予知の魔法書
ここからモンスター感知と静寂を覚えました。静寂が手に入ったのでコボルドの悪魔術師も雑魚になります。

そろそろ沼に突入できるでしょうか。ルーン以外の収穫があまりないのでちょっと行く気がしませんが。あるいは静寂が手に入ったのでエルフに行くという手もあります。おそらく静寂で戦うので、できれば静寂中に逃げられる加速のワンド/癒しのワンドあたりを拾ってからのほうがいいですが。

gwtをインストールしてみました。

gwt getting startedを読むとインストールとサンプルの閲覧、それからプロジェクトの作成まではすぐにできました。しかし自分のプロジェクトを作る際のドキュメントがわからなくてはまってました。

結局gwtで遊んでみました by 原田さんのソースからAPIリストをたどって解決。とりあえずawtとある程度同じように使えそうなので適当に書いています。

Programming in Haskell by Graham Huttonは どう見ても入門書なのでスルーしていました。 しかしInemuri nezumi diary 06/09/2007を読んでしまうと読まざるを得ないような気がしてきます。でも、買うとがっかりするのが想定できて微妙です。

何だっけ今日のどこかで出た話。テニスボールを第三宇宙速度で相手にぶつけるとどうとか。それを聞いたとき以下の動画を思い出しました。

クーガー名言 大は小を兼ねるのか@nicovideoクーガー名言@youtube

こんな感じに砕け散ると思います。計算してはいませんが。

池袋の丸井サンシャインバザールへ突撃してきました。

大学の知り合いで丸井のバザールに行くイベントがあり、それに参加してきました。冬服が足りなくてこのままでは冬が越せそうになかったので、とても渡りに舟です。

実はこのイベントに参加したのは二回目。バザールも二回目。人込みには慣れたものの少々品定めが狂ったかもしれません。はじめは結構吟味をするものの、後半には疲れてきたのでとりあえず数をそろえる方向に走ったような感じが。

その後はなんかひたすらだべってました。

あとDDRのダブルプレイを見せてもらいました。DDRって、足元ばかり高速な変なじたばたをやっている印象がありましたが(失礼)、ダブルプレイはこう、体全体が左右に動くので素敵でした。非常に大変そうですが。

エルフ3F →獣10 F →沼 1Fと巡回。レベルを上げてから沼に突入しようとしましたが、ちょっと無理でした。

まずオークを突破してエルフの大広間へ。オーク 4Fが分断されていたのでテレポートと掘削を駆使してエルフへの道を開きます。オークの魔道士は隣接してバーサークすれば余裕でした。

そしてエルフの大広間へ。保全がないので、薬と巻物の多くをオークにおいて突入。3 Fまで降りましたがそこで闇エルフの破壊者が出てきたので撤退。エルフの騎士が何とか倒せる上に経験値が多くて助かりました。しかし薬を置いてきているので危機を回避することが困難です。もっと深層まで行っていたら危なかったと思います。

帰還後は獣の深層を突破。ヒドラは召換鼠で囲めば余裕で倒せました。また、人食いヤクが結構出てきて、すべてバーサークと毒針の餌食になりました。経験値たくさんです。しかしオクロブ草が8 Fで出たのには参りました。邪魔だし。

道に召換の杖が落ちていました。これを使うと、小動物の召換が複数召換になります。さらにオレンジ鼠を召換できます。やっとヒドラに勝てる...っ。あと探索の魔法書を購入しました。

ここで沼に突入。小動物に囲まれつつ制圧していったのですが、ヒドラ以前に希薄な霧に苦戦する始末。仕方ないので撤退しました。火力が低く、装甲も弱いのがつらいですね。

次はどこでしょう。おそらくメインダンジョンを 20 F位まで降りるのが正解です。

ダンプは続きに。

蛇穴を突破しました。

当面の行き先として最も簡単な蛇穴に突入したところ、そのままルーンを拾って帰ってくることに成功しました。異常に簡単でした。概略は次のとおり。

  • 再生などの補助があれば、茶色蛇、ナーガの戦士までのモンスターはそのまま倒せました。回避が高いのが幸いしています。
  • 黒蛇はことごとくバーサークで討ち取りました。黒蛇は動きが速く、バーサークしても逃げられると追いつきません。
  • 危険なのはナーガの猛者だけ。最下層に固定で出るので、召換などを利用して適宜かく乱させて各個撃破しました。爆裂球がダメージ40とか出ても、バーサークしていれば怖くありません。
  • 途中でユニークが出ましたが、普通に撲殺しました。
  • なぜかエゴシミターが三本も出ました。今のところ電撃が最も強い気がします。

こんなに簡単だとは思いませんでした。レベルも上がりましたし、この先も何とかなる気がします。スキルは少々を召換術に、残りはほぼ戦闘技能に費やしました。長剣がもう少しうまくなれば最後まで安定するはずです。

しかしこのタイミングではまだ沼は無理かもしれません。とりあえず獣にいたヒドラが倒せるかどうか見てみますが、おそらくACが少なすぎて厳しいと思われます。召換で囲めば何とかなるかもしれませんが。

よく考えたら、沼竜のブレスを食らったら召換された小動物は一網打尽になるような。ぜんぜんだめですね。沼ドラゴン/ドレイクとヒドラとをうまく分離できればいいのですが。

ダンプは続きに。

ゲームのディレクトリを見たらやりかけのDungeon crawlのセーブデータを発見しました。しかも起動してみたら神々の末裔 聖戦者という妙に面倒な種族/職業で。以前このゲームを結構やっていましたが、そのころでもこの組み合わせで勝利したことはありませんでした。正直無理です。

見たら就職前の日記にログがありました。Dungeon crawl プレイ日記リンク。獣の深層と蜂の巣は荒らし済みで、蛇穴や沼はまだ無理のようです。日記では武器に文句を言っていますが、その後でシミターやグレートソードが出て、武器には見通しがついたようです。

ちょっと起動してみました。

  • 普通にメインダンジョンを降下。15階を制覇。腹減りが速くてかないません。しかし戦いは楽です。バーサークと耐減速のおかげで1 on 1 では結構強い敵も倒せます。
  • 浮遊の薬を見つけたので黄色蜂の巣を荒らしに。手に入ったのはのろわれた兜と、それから力の魔法書。力の魔法書って鉄塊弾以外はあまり使い出がないような気がします。
  • 17階でドラゴンさん登場。いきなりHPを半減させられてびびりました。瞬間移動の巻物で視線をさえぎって、スピードの薬、怪我の治療の薬、再生の魔法、テレポートのワンドを順に使って安全に逃走。その後HPが回復してから、飛来物を防御した上で凍結ワンド3発で処理しました。17階はほかにも銀色の像や怪しげなpitっぽいものがあって危険です。
  • 16階にもドラゴンを発見。こちらは無視しました。
  • 火柱の載っている下級魔術書を取得。瞬間移動を覚えました。これで人食いヤクも倒せます。
  • 16階で拾ったクロークに電撃耐性。クリアに必要な耐性がそろいました。

メインダンジョンに強い敵が出てくるようになったので、そろそろ獣か蛇穴に行かないといけません。長剣スキルが弱いとか、俊足やオゾグブの鎧がないなど、軽装歩兵が持っているべき技能が不足しているので危険ですが。

手持ちの魔法書で何とかするなら、小動物の召換か死霊の蘇生を覚えるとうまく行くような気がします。どちらもヒドラに有効です。もっとも、死霊の蘇生は習得には使いこなすにはまだレベルが不足していますので、おそらく小動物の召換が有効です。

ダンプは続きに。

よく見たらノートパソコンに空き容量が20 GBくらいあったので、vmware playerを入れてみました。今まで使ったことないので。

  • http://www.vmware.com/jp/download/player/からvmware playerをダウンロード。
  • インストール。再起動を要請されます。
  • http://www.vmware.com/appliances/からイメージをダウンロード。
    • ubuntu 7.10 Gutsy Gibbonを入れてみました。
    • qemuでイメージを作るというのははるか昔の話のようです。
    • torrent clientをインストールしてからdownloadしました。http downloadもできます。torrentも、使ったことがなかったので使ってみました。
  • イメージを解凍
  • vmware playerを起動してイメージを選択。
  • 起動!!
    • 「以前の設定からコピーまたは移動しましたか」と、よくわからない質問が来ました。適当にコピーしたとか答えました。
    • 何も設定してなくてもvmware内からは外につながりました。感動。
今日はここでおしまい。続きはまたいつか。

Sedgewick, R., "Implementing Quicksort Programs," Comm. ACM, 21, 10 (1978) 847--857.を斜め読みしました。

Median-of-three partitioning reduces the number of comparisons by about 14 percent,

本家でもその程度でした。私の結果より少し数字がよくなっているのは、たぶん私の三項の選び方が適当だからだと思います。適当というのは3つ同じものを選ぶ可能性があるとか。

あと、この論文だと、先頭、最後尾、真ん中の三つの要素から三項メジアンを取っています。さらに、三項メジアンをとらない場合、ピボットは先頭の値を採用しています。 私の認識だとこれはまずいです。ピボット選択にはまじめに乱数を用いないと、O(N2)になるはまりケースを作ることが可能になるので。 このケースだと(1,2,...,N, N,N-1,...,1)みたいな、中央が最大、両端が最小となる入力で、O(N2)にできるはずです。

そもそも、1978年にrandomized algorithmの研究はすでになされてたんでしょうか。Rabin-Miller素数判定法が1978年なのを考えるとまだあまり深い研究はなされていなかったのかもしれません。誰か詳しい人いらっしゃいませんか。

ACM/ICPC行ってきました。

表彰式だけ。

Asia site directorのProf. C. J. Hwang さんの話に感動。

"This is the first time for ten years that Japanese team got #1 in the contest in Japan. Congratulations!"
本当にcongratulationsです。

あと、問題の公開はいつでしょうか..

なんかちゃんと実装して速度を測って、あと論文だけ見ればいいような気がしてきました。しかしACMの会員はもう切れていて、古い論文はなかなか手に入りません。ようやく Sedgewick, R., "Implementing Quicksort Programs," Comm. ACM, 21, 10 (1978) 847--857.は見つかりました。

ここまで、比較回数の平均や分散を表す漸化式は自分で計算してきました。同時に これらを検算するために、次のような、比較回数をランダムに計算するコードを作っていました。

def comp(n):
  if n == 0:
     return 0
  k = random.randrange(n)
  return n - 1 + comp(k) + comp(n - 1 - k)

これを利用する際にさまざまなイベントが。

  • 乱数のためにメルセンヌツイスタを導入。検索したら、SIMD-oriented Fast Mersenne Twisterなるより速いMTが存在することを発見。
  • 標本分散は標本数NじゃなくてN-1で割るのが正しいはず、と思って統計の本を探しまくる。Χ二乗分布をまったく忘れていました。

ひょっとして三項メジアンの利点は単純な高速化だけでなく、やたらと遅いケースを排除することにあるのではないでしょうか。たとえば、比較回数の分散が、普通のquicksortに比べて少ないなどです。

同じように計算式を作って調べてみました。

quicksort比較回数の標準偏差

横軸が要素の数。縦軸が標準偏差つまり分散の平方根です。ほぼ半分になっているのがわかります。比を取るとよりわかります。

quicksortの比 ver2

ところで、三項メジアンの場合、比較回数はどれだけ少なくなるのでしょう。 三項メジアンはquicksortの高速化手法の一つです。 ピボットを単にひとつランダムに選ぶ代わりに、要素を三つ選んでその中間の値をピボットに採用します。たしかSedgewickのalgorithmsかどこかにありました。

比較回数は、普通のquicksortと比較して高々定数倍の違いしかないはずです。なぜなら、O(N log N)はソートの計算量の下限なので、三項メジアンを採用しても比較回数は少なくともO(N log N)になるためです。しかしどのくらいでしょう?

次のような関数を想定してみます。

def qsort_median3(elements):
  n = len(elements)
  p = random.randrange(len(elements))
  q = random.randrange(len(elements))
  r = random.randrange(len(elements))
  if elements[p] < elements[q]:
    if elements[q] < elements[r]:
       i = q
    elif elements[p] < elements[r]:
       i = r
    else:
       i = p
  elif: # cut
  # cut
  # pivot = elements[i]
  k = partition(elements, i)  # partition: needs n-3 comparison
  # k is the position of the pivot
  qsort_median3(elements[0..k])  # comparison comp(k)
  qsort_median3(elements[k+1..n])  # comparison comp(n-1-k)

この場合、比較回数関数comp(n)は次のようになるはずです。

comp(0) = 0
comp(n) = n + 1/(n*n*n) * sumk((1 + 3*(n-1) + 6*k*(n-k-1)) * (comp(k)+comp(n-k-1))

k はピボットの値です。(1 + 3*(n-1)...のところで、ピボットがkとなる場合の数を計算しています。

計算結果です。

三項メジアンつきquicksortの比較回数

少しだけしか速くない。比を取ったほうがわかりやすいかも知れません。

三項メジアンと普通のquicksortとの比較回数の比
N = 100とか短いところは無視して,N <= 10000のところを注目すると、およそ1割速くなっています。こんなもんでしょうか。それともプログラムが間違っているかもしれません。

プログラムがあっているとすると、

  • 性能向上はこの程度
  • ほかの最適化と組み合わせると有効
  • 比較回数で性能向上は測れない

このあたりが思い当たります。実測もしないとだめですね。

少し前にquicksortの比較回数を推定する話を聞きました。n個の要素をquicksortする場合の比較回数の平均comp(n)は次の式で表せます。

comp(0) = 0
comp(n) = n-1 + averagek(comp(k)+comp(n-1-k))

想定しているクイックソートのコードはこんな感じです。

def qsort(elements):
  n = len(elements)
  i = random.randrange(len(elements))
  # pivot = elements[i]
  k = partition(elements, i)  # partition: needs n-1 comparison
  # k is the position of the pivot
  qsort(elements[0..k])  # comparison comp(k)
  qsort(elements[k+1..n])  # comparison comp(n-1-k)

計算すると、comp(n) ~ n log nという関係が出てきます。 randomized quicksortの計算量ですね。

普通のquicksortの比較回数

横軸をlog scaleであらわし、縦軸をNで割っています。なので直線になっていれば y ~ x log x です。

かなり鼻と喉と頭が痛いのでじっとしてました。たぶん先週末の台風のときに風邪を引いたと思います。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。