BitFlag


bitflag弊社では、他の会社が作られたソースコードを元に、機能追加をすることもままあります。
大きな改変は避けたいのですが、そうも行かないこともあります。
ここで紹介するのは、BitFlagの検証をしたよ、という話です。

以前、BitFlagという検索手法をAS3で実装しているコードにぶつかりました。
BitFlagは32Bitの整数で構成されているので、原理的に32以下のキーしか持てません。
しかし、求められている機能追加では、検索キー自体を40以上に増やす必要がありました。
そこで、BitFlagを二つ用意するように改変するのか、そもそもBitFlagを使わない方法に改変するのかの選択に迫られました。いずれにしても、大幅な改変です。

結論から言うと、BitFlagの実装は丸ごと捨てて、単純に文字列の全数比較をする方法で実装しなおしました。
コードもわかりやすくなり、速度の犠牲もありませんでした。めでたしめでたし、でした。

検証したことを紹介します。

BitFlagについて

その前に、BitFlagについて簡単に説明します。

例として、ソフトウェアのスキル保持者調査をイメージしてみます。
スキルと言ってもいろいろあるわけですが、ここでは深くは述べず単純化します。
「Excel、PowerPoint、Photoshop、Flash」
という4つの項目で抽象化します。

Aさんは、
「Excel=Yes、PowerPoint=No、Photoshop=Yes、Flash=No」
となりました。
順番固定として、Yesを1、Noを0と書き表すと
「1010」
となります。

AさんがPhotoshopを使えるかどうかを見るには、
「1010 & 0010」として、0010が返ってくれば該当者となるわけです。

ビット演算に関しては、Wikipediaでどうぞ

数千、数万人のデータを保持しておいて、
PowerPointとPhotoshopを使える人を抜き出すには、
「対象のデータ & 0110」 として、0110が返ってくれば該当者となるわけです。
ExcelとPowerPointを使える人であれば、
「対象のデータ & 1100」として、1100が返ってくれば該当者となるわけです。

なかなか面白い考え方ですね。

速度確認

BitFlagは非常にリソースの限られた環境の場合でも効率よく検索できる方法として、使われているようですが、Flashで扱うような範囲の検索の場合、複雑な処理をするだけの意義があるのでしょうか?

件の案件では、せいぜい数千件のデータでした。
そこで、3万件のデータ、検索キー(上の例で言うと、PowerPointなどの項目)を10個として、元のソースに近い実装で速度確認をしました。

bitflag – wonderfl build flash online

結果はBitFlagが数ミリ秒早い時もありますが、遅い時もあります。実質的に速度差が無い、と判断しました。