B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
2次キャッシュを意識してコーディングしてる?
先日、北陸twitterオフで、2次元配列をx,yの順でアクセスするのと、y,xの順でアクセスするのでは、実行速度が違うんだよ、という話をしていたのだが、正直このネタは4、5年前にMIPSを使っていたときの事なので、今でも有効なのか?と思いベンチマークプログラムを作成して検証してみた。 内容 Integer型二次元配列の内容を処理する時に、アドレス順に行う(キャッシュにヒットしやすい)場合と、そうでない(キャッシュにヒットしにくい)場合を比較してみた。 環境 MacBookPro (Core2Duo 2.4G / Memory 4GB) MacOS X 10.5.6 gcc 4.0.1(-O2で最適化) 結果 X Y キャッシュヒット キャッシュミス diff 1024 1024 0.002351 sec 0.062166 sec x 26.44 1024 2048 0.004840 se
「ソフトウェアは工業製品ではない」、Rubyのまつもと氏が講演 － ＠IT
2009/04/10 ソフトウェアは工業製品ではない――。Rubyの生みの親としてしられるまつもとゆきひろ氏は2009年4月9日、InfoQ主催のイベント「QCon Tokyo 2009」の基調講演で、ソフトウェアと何であり、何でないのか、それはどういう性質のものであるのかを雄弁に語った。 コードとは設計である 「ビューティフルコード」と題した基調講演を行ったまつもと氏は、2007年に共著者の1人として出版した同名の書籍に書いたエッセイに込めた思いを、次のように語る。 「世界に冠たる日本の製造業のノウハウを適用することで生産性を上げることができるに違いないという発想がありますが、ソフトウェアは工業製品ではない。そうした誤解を正していきたい」。 ソフトウェア産業界では、よくエンジニアが何十万人足りないということが言われる。しかし、まつもと氏は、これは工業生産と同じ方法論を当てはめることから来
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
