社内コードコンペ - お題：最速な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の数が増えてもほとんど遅くなりません。 また、２分探索に比べると、探索部分の

[kazuhooku]

ルータの実装とか既知の良いアルゴリズムがあるんじゃないのかなぁ