以前書いたけどいつもjavaのXMLライブラリの使い方とか忘れるので備忘録用に上げておく import java.io.File; import javax.xml.parsers.SAXParser; import javax.xml.parsers.SAXParserFactory; import org.apache.lucene.analysis.Analyzer; import org.ap…

岡野原氏の作成したwavelet木を使った高速配列処理ライブラリwat-arrayを利用して、2次元探索のプログラムを書いてみた。 なお、自分はwavelet木のアルゴリズムについては全く分かってないですが、wat-arrayでは配列に対して、操作を行うインターフェイスが…

タイトルは釣りです。id:mamorukさんの書いたHadoop で Wikipedia のテキスト処理を900倍高速化 - 武蔵野日記を読んで、そもそも1G程度のデータの単語頻度を数えるのに858分もかかるんだっけと思い、id:nokunoさんの資料を読んでみると単語頻度を求める際に …

プログラム上からPDFの文章を取り出したいと思うことがあったので、方法を調べてみた。 PDFBoxというツールを使うと結構いい感じに抽出できた。 以下に簡単なサンプルプログラムを示す。 import java.io.*; import org.apache.pdfbox.pdfparser.PDFParser; i…

マルチスレッドでのechoサーバのメモserver.cc #include <iostream> #include <sstream> #include <pthread.h> #include "ServerSocket.h" #include "Queue.h" using namespace std; string readLine(int sock){ char c; stringstream buffer; while(1){ int ret = read(sock, &c , 1); if(</pthread.h></sstream></iostream>…

圧縮のプログラムを書くときにはbit単位でエンコーディングをする必要があるため、bit単位でエンコードをするBitEncoderというものを書いてみた。 動作としては1byte変数にbitをバッファリングしていっぱいになったらファイルに書き出すという感じです。 #in…

Grand Prizeが達成されたNetflix Prizeですが、データの公開が停止されたりすると困るので登録してデータを確保した。Netflixのデータフォーマットは展開先のフォルダの下にtraining_setというフォルダができ、その中にmv_0000001.txt ...という形式で17770…

去年は出題側でしたが、今年は解く側で参加。結果は6問で(24)位(1問去年の問題案から使い回しがあるので順位は参考ということで) A やるだけ。Accept B 典型的なDP。ただ点ではなくエッジが通れないので２問目にしてはややめんどう。Accept C 一人の方の手を…

a.out: A.cpp g++ -o a.out A.cpp clean: rm -f a.out のようなコードを書いて、make cleanと行った場合にcleanというファイルがディレクトリにあると'clean'を最新版と判定するため実行されない。 明示的に実行させるためには以下の行を追加すればうまくい…

会津大学主催のプログラミングコンテストに参加してみた。 レジストしてからc,c++しか使えないことに気づいてどうしようかと思ったけど、勉強も兼ねて参加。 結果は６問中３問でした。 A：Traffic Analysis 経過時間をソートして最大の間隔のものをとるだけ …

DO++に紹介してあったleft-leaning red-black treeという赤黒木の一種で実装が簡単なものを実装してみた．get,put,deleteを実装したところ156行となった．アルゴリズムイントロダクションの実装が疑似コードで150行程度なので*1．また，JavaのTreeMapと挿入+…

http://mallet.cs.umass.edu/より class Digamma { public static final double EULER_MASCHERONI = -0.5772156649015328606065121; public static final double DIGAMMA_COEF_1 = 1.0 / 12; public static final double DIGAMMA_COEF_2 = 1.0 / 120; public…

http://www.spoj.pl/ZFUN08/ SPOJのコンテストに先週あたりから参加しています。あんまり長期間行うコンテストに参加した経験はなかったのですが、色々と文献調査とかしながら問題を解くのはなかなか面白いです。 一応、一通り手をつけて現在ランキング7位に…

今研究室で四年生の実験のTAをやっています。実験の題材は「パターン認識システムの製作」でパターン認識を使った何かシステムを作るというもの。テーマを相談させて決定させたところ言語の自動判別をやることになった。 言語の自動判別というと最近Google A…

複雑ネットワークを解析するためのグラフアルゴリズムなどをまとめたPythonのパッケージNetworkXを使ってみた． とりあえずNewmanのサイトからとってこれる，空手クラブのネットワークデータを読み込んで,Girvan-Newman algorithmにより，グラフがコミュニテ…

GNU makeでmake -j [jobs]とオプションをつけると並列にビルドを行ってくれる． cf: http://www.gnu.org/software/make/manual/html_node/Parallel.html#Parallel

入出力が公開されたので，前書いたのをテストしてみる．A,B,C,D,F,Hは一発で通る．Gはゴーストが1体しかいない盤面のときに交換チェックをするというバグがあってそれをとったら通った，実行時間は45秒ぐらい．Iはランダムっぽいデータだと正しい答えが出る…

研究室のPCにhttp://developer.nvidia.com/object/cuda.html:CUDAをインストールして走らせてみる．インストール時に手間取ったのはNVIDIA Linux display driverをインストールするところでXを止めてくださいとかいわれて止め方が分からず困ったんだけどinit…