動機久しぶりのブログエントリになります。 休んでる間何もしてなかったかというと、勿論そうではなくて、比重がインプットに偏っていたのが原因でした。 偏りなくできるのが理想ですが、あまり時間がない時はひとつのことに集中するのが、経験上効率的だと…

導入 Giraphのソースコードを読んで見たので、そのメモとして残しておきます。 GiraphというのはHadoop上で動作する大規模グラフ処理システムのことです。 オリジナルはPregelといわれるGoogleが論文を出したBulk synchronous parallel(BSP)を用いたグラフ処…

前置き 少し時間が立ってしまいましたが、Hadoop開発者/管理者向けトレーニングに参加してきましたのでその感想をつらつらと書きたいと思います。 なお、Hadoop開発者/管理者向けトレーニングというのは、Clouderaという会社が実施しているセミナーです。 Cl…

どうでもいいことですが、山本一力の作品に「大川わたり」という作品があります。 この作品は借金が原因で大川(現在の隅田川)をわたれなくなり、新しい生活を送ることになった大工のお話です。 そして、これまたどうでもいいことですが、１ヶ月程前、ヤフー…

動機 数年前Cuckoo Hashingも知らないの？と友人から信じられないという目で見られた経験から、いつかCuckoo Hashingを超えるアルゴリズムを実装してやるという(考案してやるという程は高くない)野望を持っていました。 そこで今回はHopscotch Hashingを実装…

動機 ふと、自分が全探索な問題を解く時にどう解いているかをまとめて見ようと思った。 もちろん自分もまだまだなわけなので、解説というものにはならないし、あくまで自分の考えをまとめただけである。 ちなみに自分が少しでも全探索についてちゃんと理解で…

リストの循環チェックアルゴリズムといえば、兎と亀のアルゴリズムが有名だけど、ふと疑問がわいたのでさらっと検証してみた話。 時間も労力もかけたエントリではないけど、まぁいいかと。 兎と亀のアルゴリズムというのは、リスト構造を２つずつ辿るポイン…

前々から、LSHとか最近傍探索に興味があったので、下記の論文をちょっと実装してみた。 面倒なので、ちゃんとした評価はしていない。 Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures (WWW 2011) Fast Approximate Neares…

背景と動機 Emacsはエディタではない。環境である。 最近のIDEは非常に優秀で、IDEを使うか使わないかで生産性に大きな差が出てしまう、そういう状況が整いつつあるのかなという気がしています。 それでもやはり、動作の軽さやきめ細かいカスタマイズ性にひ…

先行き不安ながらもなんとかDiv1で戦うことができるようになったのを記念して、TopCoderに参戦してからこれまでのことを、つらつらと振り返りたいと思います。まぁこれが読まれる頃には次のSRMに参加してDiv2に落ちているかもしれないのですが・・・。 最初…

Preface 前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。 で、そっちを説明しようと思った…

最後です。 これも@machyさんから、2の冪乗での除算の場合、intとunsigned intで発行される命令数が違うという話を聞いて、詳しく調べてみた話です。 で、実際に検証するために、以下のコードをコンパイルしてみました。 int main(int argc, char *argv[]) {…

今回は負の剰余の話です。 剰余は正の数同士の場合は何も問題ないのですが、負の剰余をとってしまうとはまることがあります。 なぜなら言語処理系依存だからです。C++, pythonのそれぞれを比較すると下記のようになります。 (C) -2 % 5 = -2 (python) -2 % 5…

パイプライン処理といった技術の発達した最近のCPUでは、条件分岐を減らすことで最適化が可能な場面があります。 こういった場合に稀に利用されるのが、算術演算を利用したテクニックです。 算術演算を上手く利用することで、場合によっては必要だった条件分…

僕がC++をいいなぁと思う理由の一つに、RAIIが使えるという点がありました。 ただ最近RAIIに対して懐疑的に思えてきたので、そのことを書きたいと思います。 RAIIというのはオブジェクトのコンストラクタでファイルの初期化やロックの取得などリソースの獲得…

ほぼタイトル通りですが、flock(2)はスレッド排他するようですがfcntlを使ったPOSIXアドバイザリロックはスレッド排他しないんだなーということを検証してみたのでメモ。 以下がその検証のコード。上記のリンク先のコードがベースです。 一瞬で止まりました…

少し間があいてしまいました。 前回、次はC++じゃない話を・・・と書きましたが今回もやっぱりC++の話です。 C言語やC++でも、日本語のようなマルチバイト文字列を扱おうという話になった時に、まず選択肢としてあがるのがwchar型でしょう。 wchar型で扱えば…

つい最近、C++の文字列splitが必要な場面がありました。 いい加減C++のsplitを毎回書くのが面倒になってきましたので、忘れないようにメモっておきたいと思います。 C++でsplitを書く方法はいくらでも方法があると思いますが、代表的な実装例をあげてみます…

日曜日は、モンスターハンターを新宿ヨドバシまで買いに行ったら売りきれていて、仕方なくプログラミングしてました。 そういえば、僕はずっと前から日本語文字コードを判別するプログラム書きたいなーと思っていたのでした。 まぁ、実はNKFやらICUやfirefox…

つい最近、UTF8文字列を扱う処理を書いたのでその実装方法についてのお話です。 今日の問題設定は、天下一プログラマーコンテストの例題でも有名になりましたが、UTF8の文字数カウントです。 UTF8の文字列形式について詳しくはWikipediaを見て頂ければいいか…

動機 一般的なブログサービスを利用していれば、データが消えたりといった問題を気にする必要はありません。 ですが、私の場合、ブログのデータ及び、.zshrcや.emacs各種設定ファイルもレンタルサーバ上で管理しているため、データが消えた場合の復旧方法を…

前回使用したプリプロセサの話をちゃんと解説した方がいいかなと思ったのですが、下記の参考文献がわかりやすく、そちらを参照して頂ければ十分かと思うので省かせてもらいます。 Cプリプロセッサメタプログラミングで、文字列系泥沼関数型プログラミング Di…

Motivation 動機は構造体をバイナリ形式でファイルに書き出したい、ただそれだけの他愛もない話です。 何も考えずに書くと以下のようになります。 struct A { uint8_t b; uint32_t c; }; A a = {'a', 3}; fwrite(&a, sizeof(a), 1, fp); このコードを実行す…

今日は会社でコードレビュー(僕が書いたコードではない)があったのだが、その中であった指摘にconstを使うと読み出し専用領域に置かれるけど別にconstつけずにスタックに置いてもいいんじゃないか？という話があった。 ちなみにコードは下記のような感じ。 #…

このリンクからダウンロードしてください。 最近買ったmacbook airではGoogle ChromeやFirefoxではなくApple純正ブラウザのSafariを利用しています。 同じWebkitエンジンということで、普段使っているGoogle Chromeと使用感はあまり変わらず、快適です。 た…

ふと思い立って、C++ pitfallsを翻訳してみました。 原文は1997年に書かれたもので、時代を感じさせますが、今現在でも通用するC++の問題点、対処法が書かれているのではないでしょうか。少なくとも僕は、このドキュメントを読むまで知らなかったことがいく…