2008年8月9日に東京ミッドタウンにて行われた サーバ/インフラ Tech Meetingでの発表を録画した動画をニコニコ動画にアップロードしました。
サーバ/インフラ Tech Meetingの動画 - techtalk.jp
2008年8月9日に東京ミッドタウンにて行われた サーバ/インフラ Tech Meetingでの発表を録画した動画をニコニコ動画にアップロードしました。
社内コードコンペ - お題：最速なCIDRブロックマッチ判定 〜 稲田の場合: hamanoが倒せない 〜 : DSAS開発者の部屋
おさらい #1 ひろせの場合 - IP::CountryとAPRを使ってみた #2 安井の場合: バイナリサーチのあれとこれ #3 hamanoの場合: あ ありのまま 今 起こった事を話すぜ!『コードコンペだと思ったらゴルフコンペだった』な(ry #4 稲田の場合: hamanoが倒せない ← 今回 このコードのウリ 安井さんが２分探索で実装しているという話を聞いて、「それ、TRIE(トライ)で書いた方が速いしシンプルに 書けるんじゃね？」と思って、コードコンペに参加しました。 TRIEそのもの解説は、先日の濱野さんの物と同じなので省略します。 ２分探索等だとO(log n) (nは登録されているcidrの数)の計算量になりますが、TRIEを使うと計算量はO(m) (mはアドレスの長さ) となり、登録するcidrの数が増えてもほとんど遅くなりません。 また、２分探索に比べると、探索部分の
社内コードコンペ - お題：最速なCIDRブロックマッチ判定 〜 安井の場合: バイナリサーチのあれとこれ〜 : DSAS開発者の部屋
そして、残った7個のCIDRブロックに対してネットワークアドレスのマッチングをすればよいので、最大でも14回の数値比較で結果を得ることができます。これならば、32ビットの二分木検索（IP::Country）よりも計算量は少なくて済むはずです。 アセンブラでも書いてみた もう、だいぶ昔の話になりますが、アセンブラ（6502,Z80,68000)で遊んでいた時期がありました。ちょうどそのころ、バイナリサーチ、バブルソート、クイックソートなどの「アルゴリズム」と呼ばれるものにはじめて遭遇し、「これはすごい！」と純粋に感動していたことを覚えています。 その記憶が甦ったのか、なにを血迷ったのかわかりませんが、なぜかふと、「cidr_lookupをアセンブラで書き直せばもっと速くなるんでね？」と思い、インラインアセンブラで書き直してみたのがこちらのコードです。処理の内容は上記のものとまったく同じです。
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
