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

私は視認していませんが今日は月食があったそうで。

友人の発言

「満月だけじゃなくて三日月とかも変な方向から欠けたりすると面白いのに」
地球の代わりに影を作ることのできる大きなものを飛ばせばできます。つまり無理ですね。

しかしよく考えたら、そんなたいそうなものを作らなくても良いと気づきました。月食のときに地球外に出るのです。影を作る役目は地球に任せておき、観測者を動かします。地球以外の位置から見た月食は、まったく新しい姿を見せるでしょう。

実際、別方向から見たら月食はどうみえるでしょう。月食の満月を三日月にしたような、三日月の前を黒いものが通る感じではないはずです。誰か計算してください。

スポンサーサイト

via http://www.jmuk.org/diary/2007/08/27/0

via http://shinh.skr.jp

手元に数学セミナーがないのにゴルフです。とりあえず計算規則と問題は覚えました。 しかしきれいに終了しないとペナルティがあるといった記述を忘れています。 そのため正確なスコアが計算できません。

うっかり週末のかなりの部分をblockus AIに費やしてしまいました。しかも結果はAIじゃなくてHaskellによるblockusゲームの実装。

~系、~系?と口癖のように繰り返す人が出てきて聞き手が逆上する動画があると聞きました。しかしタイトルを知りません。 とりあえず"~系", 動画, うざい, あたりで検索するも撃沈。

main関数にプロトタイプ宣言をするという話にかこつけて、C++のmain関数の話をします。 しかしよく覚えていないのでC++ 3.6.1 Main Functionをざらざらとチェック。ところでこれは正しいspecificationなんでしょうか。よく知りません。

意味のわからない文章を発見。英語は難しいです。

It shall have a return type of type int, but otherwise its type is implementation-defined.
このotherwiseってどういう意味なんでしょう。

わかったことは次のとおりです。

  • main関数をプログラム中で使用してはいけない。
  • main関数をstatic やinlineで宣言してはいけない。
  • mainという名前はmain関数と衝突しない限りにおいては使える。(この記述はどこまで可能なのかよくわかりません)
  • main関数はオーバーロードできない。
  • main関数がreturnなしに終了したら、return 0;されたのと同じことがおきる。

私の使うコンパイラでは、main関数が変な引数を受け取ったり、mainが再帰したりするのはかまわないです。 正確に言うと、少なくともgcc3.4.4とvcの最近のバージョンでは。 ゴルフから得られた貴重な知見です。しかしもともとはiocccのコードからかもしれません。 ということはつまり、ゴルファーやioccc参加者はmainとして奇妙な型の関数を宣言することがあるため、プロトタイプ宣言をすることによってmainの型を明示することが望ましいといえます。

一方、mainをオーバーロードするのは普通にだめです。gcc3.4.4では次の警告が出ました。

% cat iya.cc
#include <iostream>
int main(void) {std::cout << "humu";}
int main(int c, char** v) {std::cout << "hoge";}
% g++ iya.cc
iya.cc: In function `int main(int, char**)':
iya.cc:3: error: declaration of C function `int main(int, char**)' conflicts with
iya.cc:2: error: previous declaration `int main()' here
%
一方VCでは次のとおり。
>type iya.cpp
#include <iostream>
int main(void) {std::cout << "humu";}
int main(int c, char** v) {std::cout << "hoge";}

>cl /EHsc /Ox /W3 iya.cpp
Microsoft(R) 32-bit C/C++ Optimizing Compiler Version 14.00.50727.762 for 80x86
Copyright (C) Microsoft Corporation.  All rights reserved.

iya.cpp
iya.cpp(3) : error C2731: 'main' : 関数はオーバーロードできません。
        iya.cpp(3) : 'main' の宣言を確認してください。

>

Thinkpadの十字キーの近くにある「前のページへ移動」キーをうっかり触ってしまって記事を全消去しました。*scratch*で書かないからこんなことになるのです。

Effective STLを読んでみました。

More Exceptional C++と同じ記述がいくつかあって驚きました。よく考えるとソースが同じなので当然ですが。

ちなみにこの本を買ったのは大分前、さらにちょっと読んだだけで放置していたので、ほとんどの記述は覚えていませんでした。

STLで二番目に長い名前のアルゴリズムlexicographical_compareに
これは知っていました。

Mother 3をクリアしました。七章の途中まできていたので、週末にクリアしようと思ったところ、八章、正確にはラストダンジョンが長くて危うく週末をはみ出すところでした。 以下、Mother 3とリヴィエラの両方についてのネタバレを含みます。

途中経過です。詳しいことは省略。

とりあえずpattern, templateは結構酷使されることがわかったので、なるべく軽くしてみようとlistで確保。

プロファイル。例によって詳細は続きに。実行時間が17秒とか減りました。効果ありです。といってもたいした改善にはなっていません。実時間で測定したところ102秒でした。

プロファイリングで時間のかかるところがわかったとはいえ、改善はまだまだこれからの模様です。次はRNAをすぐ出力したり、searchを速くしてみたりしてみます。

ところで、プロファイルの結果に経過時間の絶対値が出ないのは、あまりよくないような気がします。コードの変更でどの程度速度が向上したかわかりません。そのような情報も出すオプションがあるかも知れませんが。

前回さらしたソースコード、ところどころ正則評価をしてみたのが残っていました。それらを除いてprofilingしてみましたが、結果は変わりませんでした。

重い箇所はmatch, replaceとのことですが、具体的にどの処理が重いのかはよくわかりません。プロファイリングの粒度を細かくすることによって原因を突き止めます。

ghcのプロファイラでは、{-# SCC "hoge" #-}というコメントを入れることによって任意の箇所での計算時間を測ることができます。これを利用。match, replaceをpattern, templateの種類ごとに分割してプロファイリングしてみます。

結果は圧縮して続きに貼りました。 プロファイルの結果、matchRやreplaceBaseが重いことがわかってきました。matchRはDNAの分割を伴うので、重いことはわかっています。一方replaceBaseは非常に軽い処理ですが、呼ばれる回数が非常に多いので全体で時間がかかっています。また、match, replaceそのものもまだ結構時間がかかっています。

次回はこのコードを速くしてみます。できれば。

プロファイリングをしてみました。

とりあえずここまでの記録としてソースをさらします。Dna2rna.hs 。コメントとか全然ないのでごめんなさい。

まず、GHCのマニュアルのプロファイリングの部分を読みながら再コンパイルします。

> ghc --make -prof -auto-all Dna2rna.hs
[1 of 1] Compiling Main             ( Dna2rna.hs, Dna2rna.o )
Linking Dna2rna.exe ...

> Dna2rna.exe +
RTS -K67108864 -p -RTS < ..\..\icfpcontest.org\endo.dna > test.rna
すると.profというファイルに結果が出てきます。結果は次のとおり。
total time  =      175.90 secs   (3518 ticks @ 50 ms)
total alloc = 51,094,671,140 bytes  (excludes profiling overheads)

COST CENTRE       MODULE   %time %alloc

matcher           Main      27.2   16.4
replacer          Main      23.1   25.6
consumeTemplate   Main      16.8   24.9
consumeNat        Main      12.3   16.1
consumePattern    Main       6.9    7.3
searchSequence    Main       4.1    4.1
executeOnceIO     Main       2.4    0.9
debugPrintTag     Main       1.4    0.1
main              Main       1.3    2.0
executeIO         Main       1.2    0.2
outputRNA         Main       1.1    0.3
quoteDNA          Main       0.7    1.1

プロファイラによると、重いのはmatchReplaceです。 しかも、そのなかでも重いのはbrute force searchをしているsearchSequenceでも、重そうに見えるprotectでもなく、matchreplace本文です。

前回の予想は外れでした。 RNAのかかわる部分であるoutputRNA, consumePattern, consumeTemplateは別に重くありませんでした。

ICFP2007:execute@AyaCFPのコードを眺めてみました。実行速度が80秒と書いてあったので、その秘策を解読。

実はやっていることはほとんど変わりませんでした。Eager評価とかを使っているかと思いましたがそのへんもありません。目立つ違いとしては、私のコードはRNAはまじめに保持しているのに対し、AyaCFPのコードではRNAをすぐに出力しています。これがどの程度速度に影響を与えるのかはわかりませんが。

というわけで、私が期待していたような黒魔術はありませんでした。やはり正道のプロファイリングをするのが近道ということでしょう。

以前実装したdna2rna.hsを修正してちゃんと動くようにしました。 ちなみに間違いはconstの結果がまったく反転していたというひどいミス。searchの書き換え先を間違えることになりますが、そうなっても初期の命令ではほとんど影響は出ないので気づきませんでした。ちゃんとテストを書けば...

速度はThinkPad X60sで 106 seconds。一分は切れませんでした。おおよそ18 k steps/secです。もっと速くなるはず.そもそもまだ全部遅延評価です。

昨日、LL魂の裏番組として開催していたので本参加。 通知

Maximum CupはICPCとほぼ同じ形式のプログラムコンテストです。 ICPCとは次の点で異なります。

  • 個人戦
  • 解答提出はWeb経由
  • 埼玉大学Maximumの人が作成
  • 問題文に罠が仕組まれている
今回も「問題文の罠」が非常に秀逸でした。特に問題Bが異常。数字をソートして大きいほうからN個ずつ足し合わせて出力するだけなのに、さっぱり正解が出ません。ロシアからの参加者が16回も解答を投げてやっと正解するとか非常に骨のあるところを見せていました。
  • A. 罠のないのが罠。
  • B. 罠。
  • C. たぶんsticks
  • D. DP。普通にMemoizeで。
  • E. 実装系。解答0
  • F. 凸包を思い出せても解けない人。よくわからず黄金分割してはずれ。
  • G. 解法覚えてません。
  • H. 拡張互除法。
結果~.結局私はBを正解できませんでした。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。