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

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

TL;DR

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

確率的データ構造と Java

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

その一方で、(標準クラスライブラリではないにせよ) 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 アダプタを買っておこう、高いけど

発表資料