Kotlin 1.4.20-M2でDeprecatedとなったKotlin Android Extensionsを弔う
表題の通りKotlin 1.4.20-M2でKotlin Android ExtensionsがDeprecatedとなりました、個人的には好きな技術だったので弔いがてら記事にしたいと思います。
概要
Kotlin Android Extensions[1]はKotlin用のView参照機構で、findViewByIdによるViewの参照の問題を解決するために導入された。手軽に導入できシンタックスもシンプルなので採用しているプロジェクトも多いように思うが、後述するいくつかの問題によりAndroid公式からはBest Practiceとはされていなかった。
このような背景からView参照機構として長らくfindViewById,ButterKnife,Kotlin Android Extensionsといった技術が存在する状況が続いてたが（DataBindingは除く）、2019年のGoogle I/OにてViewBinding[2]が発表されView参照機構のBest Practice問題は一様の収束に至った。
これを受けて昨日リリースされたKotlin 1.4.20-M2[3]では遂にKT-42121 Deprecate Kotlin Android Extensions compiler plugin となり、今後多くのAndroidプロジェクトのView参照機構はViewBindingへmigrateされていくことになると思う。
Why kotlinx synthetic is no longer a recommended practice
redditにてなぜkotlinx syntheticはrecommended practiceではないのか、というスレッドで議論がされておりその中に以下の回答がされている。[4]
We’ve been shifting away from them (e.g. we don’t teach them in the Udacity course) because they expose a global namespace of ids that’s unrelated to the layout that’s actually inflated with no checks against invalid lookups, are Kotlin only, and don't expose nullability when views are only present in some configuration. All together, these issues cause the API to increase number of crashes for Android apps.
これによるとKotlin Android Extensionsの問題としてglobal namespace of ids, Kotlin only, don't expose nullabilityがあげられている。
global namespace of ids
これはKotlin Android Extensionsを使ったことがある人なら一度は経験したことはあると思う。Kotlin Android Extensionsのlayout id定義はグローバルに存在しlayout idのViewをimportして参照したとしてもコンパイルエラーで気がつくことができない。
Kotlin only
当然Kotlinでしか利用できないためJavaで記述されたActivityなどでは引き続きButterKnifeやfindViewByIdを使う必要があった。
don't expose nullability
when views are only present in some configuration、例えば以下のようにportrait,landscapeで異なるlayoutを定義していた場合を考えると
activity_kotlin_android_extensions.xml
<?xml version="1.0" encoding="utf-8"?> <FrameLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" android:layout_width="match_parent" android:layout_height="match_parent" tools:context=".KotlinAndroidExtensionsActivity"> </FrameLayout>
land/activity_kotlin_android_extensions.xml
<?xml version="1.0" encoding="utf-8"?> <FrameLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:tools="http://schemas.android.com/tools" android:layout_width="match_parent" android:layout_height="match_parent" tools:context=".KotlinAndroidExtensionsActivity"> <TextView android:id="@+id/label_kotlin_android_extensions_land" android:layout_width="wrap_content" android:layout_height="wrap_content" /> </FrameLayout>
この状態で例えばActivityでTextViewを参照しようとするとwarningが発生するもののクラッシュするまで問題に気づくことはできない。
... label_kotlin_android_extensions.text = "bar" // warning: The resource is missing in some of layout versions ...
一方ViewBindingを利用して参照する場合Viewはnullableとなるためコンパイルエラーとなる。
...
binding.labelKotlinAndroidExtensions.text // only safe (?.) or non-null asserted (!!.) calls are allowed on a nullable receiver of type TextView?
...
終わりに
以上Kotlin Android ExtensionsがDeprecatedになった経緯を眺めた。ViewBindingはAndroid Studio 3.6 Canary 11以降から使用可能でActivity/Fragment単位で段階的な導入も可能にみえる。自分が携わっているプロダクトでは主にDataBindingを使用しているため移行する必要はあまりなさそうだが、一部ButterKnifeによる記述が残っているのでそのあたりから移行を進めていこうと思う。
※ proandroiddevのほうでもKotlin Android ExtensionsのDeprecatedの件に触れていた[5]
参考
[1] Android KTX | Android Developers
[2] ビュー バインディング | Android デベロッパー | Android Developers
[3] Release Kotlin 1.4.20-M2 · JetBrains/kotlin · GitHub
[4] Why kotlinx synthetic is no longer a recommended practice : androiddev
AndroidにおけるJSR-310実装
ちょっとツイッターに流れてきた情報を見て気になったので改めて調べてみました。
これが凄く気になってて、本当に java.time API移行していいのかなぁ・・・ともにょってる https://t.co/XLwTNu9EuB
— 🦉 (@red_fat_daruma) June 3, 2020
TL;DL
- ThreeTenABPでJSR-310を利用する場合は環境によらず同じtz databaseを参照する（はず
- desugaringでJSR-310を利用する場合は実行環境により異なるtz databaseを参照する（はず
java.util.Date と JSR-310
java.util.Dateが使い勝手が悪いことは良く知られており、Java SE 8ではjava.util.Dateを置き換えるDate and Time APIが追加された。このAPIはJSR-310として標準化されており、インターフェースがデベロッパーフレンドリーであるだけでなくインスタンスがイミュータブル、スレッドセーフといった機能的な優位性を持つ。[1]
AndroidでのJSR-310実装方法の変遷
前述の通りJSR-310はJava SE 8からの機能である。Android Gradle plugin4.0.0以降でJSR-310のdesugaring対応がされたが[2]、それまではThreeTenBPやThreeTenABP[3]のようなJava6,7向けにJSR-310をバックポートしたライブラリを利用する必要があった。またThreeTenBPはJSR-310と完全に同じ振る舞いをするわけではないという点にも注意が必要でタイムゾーン(tz database)は独自に実装されておりJREではなくThreeTenBP自体にパッケージされたtz databaseを参照するため、tz databaseの更新にはThreeTenBPの更新が必要であった。[4][5]
tz databaseについて
世界各地域の標準時（time zone、タイムゾーン）情報をまとめたデータ群のことである、以下のように標準時からの差をタイムゾーンとオフセットにより定義する。厄介なのが世界各国でこの定義の更新は割と頻繁に行われているようで、年に数回はtz databaseの更新が行われていることだ。[6]
# Zone NAME GMTOFF RULES FORMAT [UNTIL]
Zone Asia/Tokyo 9:18:59 - LMT 1887 Dec 31 15:00u
9:00 - JST 1896
9:00 - CJT 1938
9:00 Japan J%sT
ZonedDateTime: 2020-08-01 00:00:00 (Asia/Tokyo) OffsetDateTime: 2020-08-01T00:00:00+09:00
Androidにおけるtz database
Android Gradle plugin4.0.0以降でJSR-310のdesugaring対応がされたと述べたが、これまでThreeTenABPで利用していたJSR-310に見えるものとdesugaringで利用可能となるJSR-310はtz databaseの取り扱いなど細かい部分で実は挙動が異なる。ThreeTenABPが参照するtz databaseはパッケージングされたものであるのに対してdesugaringしたJSR-310が参照するのはJava実行環境のtz databaseとなる。Android10以降の端末でいうと/system/apex/com.google.android.tzdata.apex に含まれているtz databaseを参照する。
またAndroid10以降でAPEXベースのモジュール更新メカニズム[7]が採用されたようでtz databaseの更新方法が変わっているようだが、Android9以前のOEMがAPKベースのメカニズムでtz databaseを端末にプッシュしていた方法と比べて今回の件について本質的な差異はないように思う。
まとめ
JSR-310で実装するといってもThreeTenABPを使うかdesugaringを使うかで参照するtz databaseは異なる。今後はdesguaringでJSR-310を利用するほうに流れていくと思うが、その場合実行環境によって異なるバージョンのtz databaseを参照することは避けられないのではないだろうか。
参考
[1] 必修！ Date and Time API──Java SE 8の新日時APIの基本を学ぶ - builder by ZDNet Japan
[2] Use Java 8 language features and APIs | Android Developers
[3] GitHub - JakeWharton/ThreeTenABP: An adaptation of the JSR-310 backport for Android.
[4] ThreeTen Extra と ThreeTen Backport (ja) - notepad
[5] TzdbZoneRulesProvider (ThreeTen backport 1.4.5 API)
[6] Timezone Data Versions in the JRE Software
[7] Time Zone Data | Android オープンソース プロジェクト | Android Open Source Project
9月の振り返りと10月の目標
Android
一応月1は維持している。
Coroutine Suspending Functionsを理解したい2 - sky’s 雑記
Android関係なくなりつつあるが、Coroutineについてもう少し調べて記事にする。
大学院
授業のほうは比較的順調？らしく現在10単位取得。
弊学は4学期制で10月から3学期が始まるわけだが10単位ぶん履修予定である、これが全部取れると計20単位で修士論文除く卒業要件を満たすことになるので気合入れて頑張りたい。
研究のほうはネットワーク、トランザクション系のFPGA実装に絞りつつあって10月は以下の論文読む＋プロトタイプ実装用に環境構築をする、ということでついに動き出した感じである。
サーバーサイド、インフラ
今月からサーバーサイド、インフラという項目を新規追加しました。
やはり将来的にはバックエンドにシフトしつつレイヤーを下げていきたいということで少しずつAndroid以外の仕事を振ってもらっています。当面はAndroidエンジニアとしてやっていく覚悟ですがある程度のリスクヘッジは必要なのでスキマ時間に趣味感覚で進めていければと思っています。
競プロ
pend
関数プログラミングと形式手法の振り返り
本日で春先から受講していたJAISTの授業I217関数プログラミングを終えました。
経緯としてはSET(Software Engineer in Test)界隈で形式手法が取り上げられることがあり、自分の業務守備範囲からそう遠くない領域だったため興味を持ち受講しました。今回学ぶことが多かったので内容と所感をまとめたいと思います。
※ この記事はあくまでも自分の解釈と所感であり、私は形式手法の専門家ではないので詳しい話は参考に記載したリンクを参照ください。
関数プログラミング
今回受講したJAISTの緒方教授の講義。緒方研究室[1]は形式手法に取り組んでいる関係上、講義では最終的に形式手法の触りまで学んだ。形式手法には代数仕様言語CafeOBJを用いますが、授業で触った限りだと副作用を持つような記述はできず、純粋関数型言語のパラダイムに属する印象を持った。
CafeOBJ
Common Lispで書かれた代数仕様言語。Java等のオブジェクト指向言語がソフトウェアを創るためのものであるとすると、CafeOBJは仕様を検証するためのものと捉えられると思う。講義では以下のような代数の基礎的概念を利用した。
- ソート
一般的なプログラミング言語における型に似た概念。 以下のようにソートに包括関係を持たせて宣言することが可能であり数理論理学でいう集合論的な概念を表現できる点が特徴かなと思う。
[ NzNat < Nat ]
この場合はNzNatはNatに含まれるとなり、非ゼロの自然数が自然数に含まれるという包括関係を表す。
- オペレータ
代数学でいうところの演算子を表す。例えば加算であれば以下のように定義する。
op _+_ : Nat Nat -> Nat
ただし演算子といっても算数で扱う加減乗除のようなものに限らず、プログラミング的には入力に対して出力が一意に定まる関数と捉えたほうが適切かもしれない。
- 変数・等式
変数は一般的なプログラミング言語ではデータの読み書きを行う記憶領域のことだが、代数仕様言語の文脈ではあるソートの集合そのものと捉えられる。等式 eq を用いて自然数の仕様を以下のように表すとわかりやすい。
var M : Nat . eq 0 + M = M .
数学における方程式と同義であり0 + x = xと考えるとわかりやすい。
形式手法
形式仕様記述言語を用いてソフトウェアの仕様を記述し数理や代数によりそれを検証する手法のこと。形式手法のアプローチには2つあるようで[2]、講義では証明譜(proof score)という定理証明に近い手法を学んだ。
一例として講義で取り扱った階乗を求めるfactorialの検証を示す。
再帰による階乗計算fact1と末尾再帰による階乗計算fact2を定義し、一方を仕様もう一方を実装としたときにfact1=fact2となれば仕様通りに実装されているとみなせるとのこと。PNatはペアノの公理[3]を満たす0を含む自然数。
mod! PNAT1 {
[PNat]
op 0 : -> PNat {constr} .
op s : PNat -> PNat {constr} .
vars X Y Z : PNat .
eq (0 = s(Y)) = false .
eq (s(X) = s(Y)) = (X = Y) .
--
op _+_ : PNat PNat -> PNat .
eq 0 + Y = Y .
eq s(X) + Y = s(X + Y) .
op _*_ : PNat PNat -> PNat .
eq 0 * Y = 0 .
eq s(X) * Y = (X * Y) + Y .
op fact1 : PNat -> PNat .
eq fact1(0) = s(0) . -- f1-1
eq fact1(s(X)) = s(X) * fact1(X) . -- f1-2
op fact2 : PNat -> PNat .
op sfact2 : PNat PNat -> PNat .
eq fact2(X) = sfact2(X,s(0)) . -- f2
eq sfact2(0,Y) = Y . -- sf2-1
eq sfact2(s(X),Y) = sfact2(X,s(X) * Y) . -- sf2
}
検証自体は数学的帰納法により行い、本来は定理証明に必要な補題(Lemma)も都度証明する。手順の概要は以下の通り。
- 自然数0で実装が仕様を満たす red fact1(0) = fact2(0) .
- 任意の自然数xの場合に実装が仕様を満たすことを仮定する eq fact1(x) = fact2(x) .
- x+1=>s(x)の場合に実装が仕様を満たすことを示す red fact1(s(x)) = fact2(s(x)) .
open PNat1 . op x : -> PNat . -- lemma eq Y * sfact2(X,Z) = sfact2(X,Y * Z) -- induction hypothesis eq fact1(x) = fact2(x) . -- check red fact1(0) = fact2(0) . red fact1(s(x)) = fact2(s(x)) . close
所感
- 業務への適用可能性
形式手法の導入事例[4]から見てわかるように形式手法そのものは大規模で安全性が求められるシステムに適用される事例が多いようだった。実際にプラント、発電所、機械、鉄道、医療機器、家電などを対象とした安全規格であるIEC 61508ではformal methodがhighly recommendedとなっている。[5]
元々はプロダクションコードのテストを行う要領で形式手法を導入することができると考えていたが、むしろ開発者がコーディングを行う前段階で仕様の漏れや不備を発見したりアルゴリズムの妥当性を検証するための技術と見たほうが正しいと感じた。仕様の漏れによる手戻りがクリティカルな問題になりやすいウォーターフォールの上流で効果を発揮すると思う。
自分が身を置いているようなアジャイル開発を基本とするIT業界において形式手法そのものを導入することはしばらくなさそうだなという印象だった。
- 抽象度を上げて業務へ活かせそうなこと
普段の業務では仕様策定->デザイン->開発->QA->リリースという工程があればなるべく上流で手戻り（仕様の漏れの発見）をさせることを意識しているが、学術的にも同様の試みがされていることを知り業務の取り組み方に確信を持つことはできた。
副次的には実装を式として記述することは関数型言語の基本的概念であり副作用を減らす意識も高まったので形式手法を取り巻く諸概念を学ぶ意味はあったと思う。またテストについてテストケースが足りず検知しきれないという問題やParameterized Testのような機能の有り難みも改めて実感でき良かった。
以上！
参考
[1] 緒方研究室｜研究室ガイド 北陸先端科学技術大学院大学
[2] 形式手法とは？｜ディペンダブル・システムのための形式手法の実践ポータル
[4] 形式手法の分類 - 応用事例DB
Coroutine Suspending Functionsを理解したい2
続きの記事です。 Coroutine Suspending Functionsを理解したい1 - sky’s 雑記
振り返り
fun main(args: Array<String>) { CoroutineScope(Dispatchers.Main).launch { println("start") greet() println("end") } } suspend fun greet() { println("suspended!!") }
上記コードをByteコードへCompileするとgreetの引数に Continuation という引数が渡ったコードが生成されることを見ました。
またCompileしたコードをDecompileすると以下のようなコードが生成されました、今回はDecompileしたコードからsuspendの実体を調べていきたいと思います。
... public static final void main(@NotNull String[] args) { Intrinsics.checkParameterIsNotNull(args, "args"); BuildersKt.launch$default(CoroutineScopeKt.CoroutineScope((CoroutineContext)Dispatchers.getMain()), (CoroutineContext)null, (CoroutineStart)null, (Function2)(new Function2((Continuation)null) { private CoroutineScope p$; Object L$0; int label; @Nullable public final Object invokeSuspend(@NotNull Object $result) { Object var5 = IntrinsicsKt.getCOROUTINE_SUSPENDED(); CoroutineScope $this$launch; String var3; boolean var4; switch(this.label) { case 0: ResultKt.throwOnFailure($result); $this$launch = this.p$; var3 = "start"; var4 = false; System.out.println(var3); this.L$0 = $this$launch; this.label = 1; if (TestKt.greet(this) == var5) { return var5; } break; case 1: $this$launch = (CoroutineScope)this.L$0; ResultKt.throwOnFailure($result); break; default: throw new IllegalStateException("call to 'resume' before 'invoke' with coroutine"); } var3 = "end"; var4 = false; System.out.println(var3); return Unit.INSTANCE; } @NotNull public final Continuation create(@Nullable Object value, @NotNull Continuation completion) { Intrinsics.checkParameterIsNotNull(completion, "completion"); Function2 var3 = new Function2(completion) { private CoroutineScope p$; Object L$0; int label; @Nullable public final Object invokeSuspend(@NotNull Object $result) {
CoroutineScope.launch(Java)
はじめにCoroutineの起動から見ていきます。 Decompileされた以下のコードは
BuildersKt.launch$default(CoroutineScopeKt.CoroutineScope((CoroutineContext)Dispatchers.getMain()), (CoroutineContext)null, (CoroutineStart)null, (Function2)(new Function2((Continuation)null) {
Kotlinで以下のように実装されています。
public fun CoroutineScope.launch( context: CoroutineContext = EmptyCoroutineContext, start: CoroutineStart = CoroutineStart.DEFAULT, block: suspend CoroutineScope.() -> Unit ): Job { val newContext = newCoroutineContext(context) val coroutine = if (start.isLazy) LazyStandaloneCoroutine(newContext, block) else StandaloneCoroutine(newContext, active = true) coroutine.start(start, coroutine, block) return coroutine }
greet()を含むCoroutineScopeに渡されるラムダ式は block: suspend CoroutineScope.() -> Unit にあたり new Function2((Continuation)null) に変換されます。Kotlinにおけるラムダ式はFunction2(2とは限らない)というインターフェースを実装したクラスのようで(1)、Coroutineで何が行われるかを理解するには続くFunction2の実装を追いかければ良さそうです。
CoroutineScope.launch(Kotlin)
Javaのコードを追いかけたいところですが、ここで一旦Kotlinのほうのソースコードを眺めてCoroutineの理解を深めたいと思います。 CoroutineScope.launchで渡されたblock(ラムダ式)は以下のように実行されます。CoroutineScopeで実行されるblock全体もsuspendableです。
- Builders.common.kt
public fun CoroutineScope.launch( context: CoroutineContext = EmptyCoroutineContext, start: CoroutineStart = CoroutineStart.DEFAULT, block: suspend CoroutineScope.() -> Unit ): Job { val newContext = newCoroutineContext(context) val coroutine = if (start.isLazy) LazyStandaloneCoroutine(newContext, block) else StandaloneCoroutine(newContext, active = true) coroutine.start(start, coroutine, block) return coroutine }
- AbstractCoroutine.kt
public fun <R> start(start: CoroutineStart, receiver: R, block: suspend R.() -> T) { initParentJob() start(block, receiver, this) }
- CoroutineStart.kt
@InternalCoroutinesApi public operator fun <T> invoke(block: suspend () -> T, completion: Continuation<T>) = when (this) { CoroutineStart.DEFAULT -> block.startCoroutineCancellable(completion) CoroutineStart.ATOMIC -> block.startCoroutine(completion) CoroutineStart.UNDISPATCHED -> block.startCoroutineUndispatched(completion) CoroutineStart.LAZY -> Unit // will start lazily }
CoroutineScope.launchにおいて LazyStandaloneCoroutine or StandaloneCoroutine を生成します。いずれもAbstractCoroutineを実装しておりAbstractCoroutineは以下のようにContinuationを継承します。
- AbstractCoroutine.kt
@InternalCoroutinesApi public abstract class AbstractCoroutine<in T>( /** * The context of the parent coroutine. */ @JvmField protected val parentContext: CoroutineContext, active: Boolean = true ) : JobSupport(active), Job, Continuation<T>, CoroutineScope {
CoroutineStartのstartによりblockが実行されるようですが、第2引数としてContinuationを受け取りこれはCoroutineScope.launchにおいて生成したCoroutineそのものです。CoroutineScopeにおいて生成したCoroutine(Continuation)が実行時に伝搬していく様子が徐々に見て取れるようになってきました。
前回の記事で触れた suspend関数は継続渡し方式 (Continuation Passing Style)で実装されている という話が少し実感できるようになったところでここまでにします。
少し脱線しましたが次回はJavaコードに戻りinvokeSuspend/createあたりを深堀りしてsuspend関数がどのように処理を中断するか調べていきます。
参考
7月の振り返りと8月の目標
Android
DIについて詰める予定だったけど書かなかった、とりあえず月1ペースは維持できている。Androidは仕事で触れていて書きたいものは無限に出てくるので、興味の赴くままに記事を書く形でいいかなと思っている。8月は既にCoroutineについて記事を書いていて余裕があればもう1つくらい書きたい。
大学院
1期の授業がだいたい終わったところ。
関数プログラミングという授業が面白くてCafeOBJという言語でminilaという簡単なスクリプト言語的なものを作ったりした。
研究の方はだいぶ始まってきた感があり、特にネットワークやトランザクションをFPGAで並列高速化する論文を読んでいる。将来的に仕事でサーバーサイドやインフラを取り扱うことになった際にも役に立ちそうだし。昨日ブルームフィルタについて記事を書いたけど、今後は研究に関連するアルゴリズムとデータ構造、ハードウェアの記事が増えていくと思う。
確率的データ構造ブルームフィルタについて - sky’s 雑記
競プロ
全然時間が取れておらずしばらくは休止するしかなさそう、目標設定したけどやっぱり両立できなかった。
確率的データ構造ブルームフィルタについて
Scalable Packet Classification on FPGA - IEEE Journals & Magazine
論文を読んでいて初見のデータ構造があったので記事にしておく、wikiのほうが確かだし詳しいので自分用のまとめです。
内容はルーターのようなネットワーク機器に実装されるパケットクラシファイア[1]のFPGA実装に関するもので、パケットの分類方法としてブルームフィルタというデータ構造が利用されていた。
ブルームフィルタ[2]
ブルームフィルタは確率的データ構造と呼ばれるもので偽陽性(false positive)による誤検出の可能性があるが偽陰性(false negative)はそうでなはいという特徴を持つ。空間的/時間的に他のデータ構造と比較して優位性があり、省メモリで高速に集合に要素が含まれるかを判定できる。
例えばm=18のビット列とk=3個のハッシュ関数(hash_k1,k2,k3)を仮定し、 集合{x,y,z}と要素{w}について以下が成り立つとすると
hash_k1(x)->1 hash_k2(x)->5 hash_k3(x)->13 hash_k1(y)->4 hash_k2(y)->11 hash_k3(y)->16 hash_k1(z)->3 hash_k2(z)->5 hash_k3(z)->11 hash_k1(w)->4 hash_k2(w)->13 hash_k3(w)->15
初期状態のブルームフィルタは18ビット全てが0であり
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
集合{x,y,z}それぞれにハッシュ関数を適用して該当のインデックスのビットを立てることを考えると対応は以下のようになる。
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| x | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| y | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| z | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
上記操作を行った最終的なビット列は以下のようになる。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
要素{w}が集合に含まれるかは生成したビット列の対応するビットが立っているかを見れば良く13ビット目が0となっていることから要素{w}は集合に含まれていないことがわかる。
| - | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| - | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| w | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
偽陽性・偽陰性
上記のようにブルームフィルタはk個のハッシュ関数によりビット列のインデックスを得て対応するビットを立てるという処理を繰り返す。省メモリで高速に集合の判定を行えるというメリットはあるものの、ハッシュ関数の衝突により集合からビット列を生成する際に同じインデックスのビットを立てることや、判定時に衝突により誤判定をする可能性がある。
実際には集合に存在しないが存在すると判定する偽陽性(false positive)による誤判定の可能性がある一方で、集合に存在するときに存在しないと判定する偽陰性(false negative)の可能性はないという特徴を持つ。
実装
TBD postdの記事[3]が詳しかったので時間あるときに実装したい。
