blog2013年6月28日金曜日2013年の目標振返りもうそろそろ7月か。2013年も半分終わり。いうことで、年始に立てた目標がどれだけ実現できたのかを振返り、後半をどのように過ごすか考えてみたいと思います。年始に立てた目標はこんな感じでした。1つずつ振り返って行きますか。週に4話英語の漫画を読むこれは余裕で達成できてますね。この調子で続けたいです。「めぞん一刻」英語版アニメを全話見るこれもいい感じです。オープニングテーマが『陽だまり』に変わる回くらいまでみました。このくらいのスピードのラフな感じの英語でもだいぶ聞き取れるようになりました。PODのビハインド分(1年半分くらい)をきちんとやるこれは遅れ気味です。目標立てたのは3月ですが、1月時点では2年分くらいビハインド分がありました。今年の分もやると考えると3年分やることになるのですが、正直難しいです。1日で1週間分の教材をこなす日もありましたが、集中力が持続せず逆効果という感じでした。『年末までに2013年3月分までの教材を終わらせる。』という目標に変えようと思います。PODにはすごく助けられましたが、現時点ではレベルがあってないような気がするので(スピードが遅くて眠くなることがしばしば。)来年は別の教材を探す必要があるかもしれません。土日でその週に行われたCodeforcesの問題をすべて(div2のみ)解く40点くらい。31コンテスト中13コンテストのみ問題を解きました。すべての問題を理解できるようにしようとすると、今の実力では1コンテスト1日くらいかかってしまいます。週に1回時間が取れるか取れないかくらいな感じなので、現実的な目標じゃなかったかもしれません。あと、これは趣味なのでノルマを課してやるべきものじゃなくて、時間のあるときにやるくらいのスタンスの方がいいのかなと考えたりもします。後期は『毎週1コンテスト分の問題をすべて解く』という目標で頑張りたいと思います。treeを実装してみた。treeのアイディアはシンプルで簡単に言うと二分探索木のk次元空間拡張バージョン。節点の高さごとに軸を選んで、軸と交わる超平面でk次元空間を二つに分割する。1.で選んだ超平面より左にあるデータは左部分木に、右にあるデータは右部分木に格納していく。データ集合の中央値を通るように1.の超平面を選ぶことで、平衡二分探索木にすることができる。neighborで最近傍を見つけるときの計算を高速化することができる。詳しく知りたいひとは、ここ。treeを用いると高速に解くことができそうな問題を考えてみた。『二次元平面上にN個の点が与えられる。その後L個の点が与えられる。L個の点それぞれについて、先に与えられたN個の点のうちどれに最も近いのかを求めよ。普通に書くとこうです。treeを使うとこんな感じ。0;}速度比較N=1,000,000、L=100,000とすると、straightforward解は240秒弱。treeを使った解法は8秒くらい。真面目にコードを書けばさらに10倍くらいは速くできると思う。アルゴリズム2013年6月21日金曜日JUnitを使って単体テストをする(2)djUnitを使って遊んでみました。objectといった便利な機能を提供してくれるテストフレームワークです。reportはその名のとおり、テストのカバレッジを可視化してくれる機能です。テスト対象のソースで実行されていない行にマーカーを表示してくれます。objectは、メソッドの戻り値を自由に設定することでテスト用のモックを作成せずともテストができるという素晴らしい機能です。具体的な使用方法は、以下のサンプルを見てください。想定Serviceクラスの単体テストをしたい。Serviceクラスは外部システムから情報を取得していて、取得した情報によって挙動が変わる。単体テストなので、実際に外部システムには接続せずにテスト用のモックを使って動作確認をしたい。テスト対象のServiceクラスです。doSomething()メソッドのテストを行うこととします。}}以下がユーザー情報を格納するBeanです。}}次に、外部システムと通信を行ってユーザー情報を取得する機能。実際は外部システムと通信をしてユーザー情報を取得するという想定。}}djUnitを使ったテストExternalSystemLibMockのようなモックは作成せずともテストができます。仮想モックオブジェクトの機能を利用してテストを行います。指定したクラスのメソッドが必ずnullを返すように設定できる。指定したクラスのメソッドが必ず指定した値を返すように設定できる。他にもいろいろ便利な機能があります。実行結果Eclipseでテスト実行した結果です。テストで実行されていない行にマーカーが設定されます。カバレッジの情報を外部ファイルにExportする機能もあります。サマリーレポートも一緒にExportしてくれます。JavaJUnitを使って単体テストをする(1)適当にテストして遊んでみた。適当なクラスを作ります。コイツをテスト対象として使います。}}テストクラスは以下のとおり。}}Eclipseでテスト実行した結果。JUnit便利ですねー。reportとかやってみようかと思います。Backするときの条件についてちょっと気になったので、考えてみました。Trickについてですが、ここに詳しい解説があります。b_iという直線集合が与えられて、あるx(複数のxが与えられる)についてy_iが最小になるiを求めよ。いうクエリーを効率よく求めるためのトリックで、その応用としてDPの計算を高速化する際にも利用できることがありますよ。下の3問を解いてみると、どんな感じか感覚がつかめると思います。Trickに気づくとDequeを使って計算量を落とすことができます。Sequenceは蟻本にも載ってます。)で、何が気になったかというと、Dequeから直線L2をpop_backする条件です。b_3として、今L3をDequeに入れようとしているとします。L1とL2の交点」です。