サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
大谷翔平
shnya.jp
導入 Giraphのソースコードを読んで見たので、そのメモとして残しておきます。 GiraphというのはHadoop上で動作する大規模グラフ処理システムのことです。 オリジナルはPregelといわれるGoogleが論文を出したBulk synchronous parallel(BSP)を用いたグラフ処理システムのようです。 もう少し詳しい導入が必要な方は、smly先生のTokyoWebMiningでの発表を見てください。 さて、あまりに適当な導入を飛ばしてまずはコード例を見ていきます。 コード例を見てみる Giraph自体は、グラフ処理を行うためのフレームワークですので、具体的なアプリケーションコードは用途に合わせて書いてあげる必要があります。 具体例として、Giraphのソースコードにはたくさんのexampleがあるので、その中で最短経路を求めるプログラムを見てみます。 細かい部分は
動機 数年前Cuckoo Hashingも知らないの?と友人から信じられないという目で見られた経験から、いつかCuckoo Hashingを超えるアルゴリズムを実装してやるという(考案してやるという程は高くない)野望を持っていました。 そこで今回はHopscotch Hashingを実装してみました。 Herlihy, M., N. Shavit, and M. Tzafrir, “Hopscotch Hashing,” Proceedings of the 22nd International Symposium on Distributed Computing (DISC), pp. 350-364, Arcachon, France, September 2008. Hopscotch HashingはCuckoo Hashingと同様、定数時間での検索を可能にするハッシュテーブ
リストの循環チェックアルゴリズムといえば、兎と亀のアルゴリズムが有名だけど、ふと疑問がわいたのでさらっと検証してみた話。 時間も労力もかけたエントリではないけど、まぁいいかと。 兎と亀のアルゴリズムというのは、リスト構造を2つづつ辿るポインタ(兎)と、1つづつ辿るポインタ(亀)を用意して、兎が亀に追いつけば、そのリストは循環していると判断できるというアルゴリズム。 その話から最初に考えた擬似コードが下。兎が2つ進む間にちゃんと亀に追いついてるかどうかをチェックしている。 bool check(List *listp){ List *turtlep = listp; List *rabitp = listp; while(1){ turtlep = listp->next(); rabitp = listp->next(); if(rabitp == turtlep) return tru
動機 久しぶりのブログエントリになります。 休んでる間何もしてなかったかというと、勿論そうではなくて、比重がインプットに偏っていたのが原因でした。 偏りなくできるのが理想ですが、あまり時間がない時はひとつのことに集中するのが、経験上効率的だと思っているので、今度書く時もまた半年ぶりとかになる可能性もありますが、まぁ自分用のメモみたいなものなので、気楽にやっていきたいと思います。 前置きはこの辺にして、本題に入ります。 最近、個人的な興味があって固有値の求め方を調べていました。 固有値は、特異値分解において重要な役割を持ち、そして特異値分解は主成分分析、潜在意味インデキシングといった応用の基本となるアルゴリズムです。特異値分解自体は、それ以外にも非常に多数の応用が考えられますが、詳細については省略します。 実際に固有値を求める方法は、学部時代に固有方程式を手計算で解き、また数値解析の
背景と動機 Emacsはエディタではない。環境である。 最近のIDEは非常に優秀で、IDEを使うか使わないかで生産性に大きな差が出てしまう、そういう状況が整いつつあるのかなという気がしています。 それでもやはり、動作の軽さやきめ細かいカスタマイズ性にひかれて、今でもEmacsを僕は愛用しています。Emacsはエディタであるにも関わらず、非常に高機能かつ多彩なカスタマイズが可能なため、人によっては「エディタではない、環境である」と主張する人もいます。実際、各種パッケージを導入することで、WebブラウジングやIRCなど驚くほど多彩な機能が利用可能です。 そんなEmacsを使い続けて何年か経ち、設定ファイルもいろいろ貯まってきたので、今後気が向いた時に、Emacsでこんなこともできるよ!ということを紹介したいと思います。 ビルドと実行プロセスを簡略化するパッケージ プログラミングを行う際、基本
先行き不安ながらもなんとかDiv1で戦うことができるようになったのを記念して、TopCoderに参戦してからこれまでのことを、つらつらと振り返りたいと思います。まぁこれが読まれる頃には次のSRMに参加してDiv2に落ちているかもしれないのですが・・・。 最初の一歩 一番最初にTopCoderにユーザ登録したのは3年以上前の学生時代の頃でした。 その頃に一度SRM(シングルラウンドマッチ)の過去問を解いてみて、2,3問ほど解くのに約1日ぐらいかかったように思います。 SRMというのは、問題が出題され、アルゴリズムを考えて、コーディングして解くまでのスピードを競うゲームです。 (どういう問題が出題されるかというのは、TopCoder参戦記の方に問題の概要を張ってあるので参考にしてください。) 一回あたりEasy,Medium,Hardの三問出題され、各問題を解くごとに、解いた時間と難しさ
先行き不安ながらもなんとかDiv1で戦うことができるようになったのを記念して、TopCoderに参戦してからこれまでのことを、つらつらと振り返りたいと思います。まぁこれが読まれる頃には次のSRMに参加してDiv2に落ちているかもしれないのですが・・・。 最初の一歩 一番最初にTopCoderにユーザ登録したのは3年以上前の学生時代の頃でした。 その頃に一度SRM(シングルラウンドマッチ)の過去問を解いてみて、2,3問ほど解くのに約1日ぐらいかかったように思います。 SRMというのは、問題が出題され、アルゴリズムを考えてコーディングして解くまでのスピードを競うゲームです。 (どういう問題が出題されるかというのは、TopCoder参戦記の方に問題の概要を張ってあるので参考にしてください。) 一回あたりEasy,Medium,Hardの三問出題され、各問題を解くごとに解いた時間と難しさを考
Preface 前にプリプロセサを駆使してシリアライザを書いたことがあったのですが、Expression Template(以下 式テンプレート)を使えば#define使わなくても近いようなことできるなーと思いついたので、実際に作ってみました。 で、そっちを説明しようと思ったんですが、やっぱり気が変わって、式テンプレート自体の自分なりの理解を簡単に説明したいと思います。 ちなみに式テンプレートのちゃんとした入門は、参考URLの方で錚々たる方々が素晴らしい記事を書いているので、そちらを参考にしてください。この記事はまぁ、蛇足的な、自己満足のためのものです。 Introduction 式テンプレートは、最初、行列やベクトルを使った科学計算の効率化のために考案されました。 例えば以下のようにVectorクラスの演算を行うとします。 Vector v_result, v1, v2, v3; v
今回は負の剰余の話です。 剰余は正の数同士の場合は何も問題ないのですが、負の剰余をとってしまうとはまることがあります。 なぜなら言語処理系依存だからです。C++, pythonのそれぞれを比較すると下記のようになります。 (C) -2 % 5 = -2 (python) -2 % 5 = 3 計算結果は違っていますが、この二つプログラミング言語の剰余は、両者とも、以下の等式が成り立つような値と定義されています。 x == (x / y)*y + x%y つまり剰余の値は、 x % y = (x / y)*y - x という式で得られます。 剰余の計算結果が異なっている原因は負の値に対する除算の値が異なるからです。 (C) -2 / 5 = 0 (python) -2 / 5 = -1 下のグラフを見ていただければわかると思うのですが、pythonの場合、除算の結果は「x 以下の最も大きい
パイプライン処理といった技術の発達した最近のCPUでは、条件分岐を減らすことで最適化が可能な場面があります。 こういった場合に稀に利用されるのが、算術演算を利用したテクニックです。 算術演算を上手く利用することで、場合によっては必要だった条件分岐も削減可能なことがあります。 そんな算術演算の重要性の高まりを受け、今日から3回に分けて算術演算に関する話をしたいと思います。 まぁ、そういったこじつけ的な背景説明はともかく、@machyさんに教わったテクニックを僕の中だけにおさめておくには勿体無いなぁと思ったのが本当の動機です。 例えばプロセスのメモリ使用量をKB単位で表示したいとします。 こういった場合、実際のメモリ使用量は1500バイトでも、多めに見積った方が好まれるため、1024の倍数に切り上げて2048/1024で2KBと表示します。 ではこの倍数への切り上げ処理を素直に書いてみ
僕がC++をいいなぁと思う理由の一つに、RAIIが使えるという点がありました。 ただ最近RAIIに対して懐疑的に思えてきたので、そのことを書きたいと思います。 RAIIというのはオブジェクトのコンストラクタでファイルの初期化やロックの取得などリソースの獲得を行い、デストラクタでファイルのクローズやロックの開放など、リソースの開放を行うテクニックです。明示的にclose処理等を書く必要がないので、ファイルの閉じ忘れ、ロックの開放し忘れを防ぐことができます。 また処理の途中で例外の発生などの意図しない挙動が起きた際にもリソースが開放されることが保障されており、頑健なコードを書くことが可能となります。 Javaなどのガベージコレクションを持つ言語ではどのタイミングでオブジェクトが破棄されるかわらかないので、ファイルハンドルを開きっぱなしにしたり、ロックを持ち続けてしまう可能性もあってこのテク
NMH (Nihongo Moji-code Hanbetsu) Library 紹介 日本語の文字コードを判別するためのライブラリです。 現在、UTF-8, EUC-JP, ISO-2022-JP, Shift_JISに対応しています。 文字コードを変換するだけであれば準標準ライブラリと言えるiconvが利用できるのですが、文字コードの判別は nkf , ICU , BABEL といった追加ライブラリの導入が必要でした。 そういうライブラリを入れるまでもない、お手軽に文字コードの判別ができるように、という思いから作ってみました。 変更履歴 version 0.0.1 first release インストール 1. ソースコードをダウンロード githubもしくはこちらからダウンロードが可能です。 $ git clone https://github.com/shnya/nmh.gi
つい最近、C++の文字列splitが必要な場面がありました。 いい加減C++のsplitを毎回書くのが面倒になってきましたので、忘れないようにメモっておきたいと思います。 C++でsplitを書く方法はいくらでも方法があると思いますが、代表的な実装例をあげてみます。 boostが使える環境であれば一番最初の選択肢としてboostのstring algorithmを利用した方が車輪の再発明をしなくて済むかと思います。 ただ、競技プログラミングなどでは残念ながら利用できません。 find_first_ofを利用する方法 vector<string> split(const string &str, char delim){ vector<string> res; size_t current = 0, found; while((found = str.find_first_of
つい最近、UTF8文字列を扱う処理を書いたのでその実装方法についてのお話です。 今日の問題設定は、天下一プログラマーコンテストの例題でも有名になりましたが、UTF8の文字数カウントです。 UTF8の文字列形式について詳しくはWikipediaを見て頂ければいいかと思いますが、 http://ja.wikipedia.org/wiki/UTF-8 簡単に紹介すると、UTF8は一文字1-6バイト(最近は1-4バイトのみ)からなるエンコード形式であり、各文字が何バイトから構成されているかはその文字の1バイト目を見ればわかります。 例えば1バイト文字の場合は7bitのASCII文字から構成されていて、1バイト目の上位ビットが「0」となります。 2バイトの場合は「110」, 3バイトの場合は「1110」という風に以降、上位ビットの1の数と1文字あたりのバイト数が等しくなります。 また先頭バイト
動機 一般的なブログサービスを利用していれば、データが消えたりといった問題を気にする必要はありません。 ですが、私の場合、ブログのデータ及び、.zshrcや.emacs各種設定ファイルもレンタルサーバ上で管理しているため、データが消えた場合の復旧方法を考えておく必要がありました。 バックアップ先をどこにしようかと思っていたのですが、ちょうどAmazon Web Serviceが1年間無料のサービスを展開中だったため、Amazon S3に保存することにしました。 一応参考になる人もいるかと思いましたので手順を公開します。 Amazon Web Serviceの登録から利用まで 下記から入手可能なドキュメントを見ながら登録してもらえば問題ないでしょう。 http://jaws-ug.jp/documents/j5f69c その他にも無料Tierを利用してみましたという解説記事は多いのでこちら
C++の落とし穴 このドキュメントは下記URLのサイトを翻訳したものです。 10年以上前に作成されたドキュメントですが、いくつか新たな気づきを与えてくれた原本に感謝して、翻訳してみました。 やや見づらいところもあるかもしれませんが、誰かのお役に立てれば幸いです。 C++ Pitfalls Copyright (C) Cay S. Horstmann 1997 Translated by shnya (unofficial)
cppref.el 奥 一穂さんのCpprefをemacsから使えるようにしたelispです。 Cpprefの詳細は下記 http://developer.cybozu.co.jp/kazuho/2009/10/cppref-reading.html github 該当のcppref.elというファイルはgithubからダウンロードできます。 http://github.com/shnya/cppref-el cppref.el 上記のcppref.elをどこかのload-pathに置いて以下の設定を.emacsに書いてください。 (require 'cppref) (add-hook 'c++-mode-hook #'(lambda () (setq cppref-docroot "/usr/share/doc/cppref") ; cpprefのドキュメントパス ;; (cppre
このページを最初にブックマークしてみませんか?
『http://shnya.jp/』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く