Java で確率的データ構造をお手軽に扱う / #JJUG ナイト・セミナー 「ビール片手にLT＆納涼会 2017」発表メモ

JJUG ナイト・セミナー 「ビール片手にLT＆納涼会 2017」 で、無理矢理 Java に絡めて確率的データ構造の話をしてきたメモです。

TL;DR

• stream-lib がそこそこ幅広く確率的データ構造の実装を提供しているので、まずはこれを使ってみるのがよい
• (時間効率ではなくて) 空間効率のよさを求める類の確率的データ構造は、厳密解ではなく近似解が得られる
  • 近似解の精度と空間効率は、トレードオフの関係にある
• 「精度と空間効率のトレードオフ」は、パラメータで調整できる
  • JOL (Java Object Layout) や JMH (Java Microbenchmark Harness) を用いて、実際の空間効率や速度効率を確認しながらパラメータを調整するのがよい

確率的データ構造と Java

「Java で確率的データ構造」というと、java.util.concurrent の ConcurrentSkipListMap や ConcurrentSkipListSet の実装などで使われている スキップリスト がその具体例として真っ先に上がるかと思います。

その一方で、(標準クラスライブラリではないにせよ) Maven central リポジトリにはそれ以外の確率的データ構造の実装が存在するので、それを使わない手はないよね、ということで、確率的データ構造のライブラリの紹介と、それぞれが提供する機能について非常に軽く説明しました。

• stream-lib
  • Membership query: Bloom filter
  • Cardinality estimation: LogLog, HyperLogLog, HyperLogLog++
  • Frequency counting: Count-min sketch, Conservative update
  • Quantile estimation: Q-Digest, T-Digest
• java-hll
  • Cardinality estimation: HyperLogLog++
• t-digest
  • Quantile estimation: T-Digest

特に、リアルタイムかつ大量に発生するデータをオンラインで処理する場合に、これらの確率的データ構造が活躍することでしょう。

発表の振り返り

振り返りというか、反省点です。

• 5 分の LT では 40 ページ超の発表はギリギリ収まらないので、もうちょっと削ろう
• USB type-c to HDMI アダプタ & HDMI to VGA のアダプタ二段重ねは無理だった
  • 素直に Apple 純正品の type-c to VGA アダプタを買っておこう、高いけど

発表資料