mog project

6.22.2015

Counting True in the Python List

Python: リスト内の True の個数を数える

sum を使えば、True: 1, False: 0 としてカウントされるので便利。

>>> [False, True, True, False, True].count(True)
3
>>> sum([False, True, True, False, True])
3
>>> sum(x % 2 == 1 for x in range(5))
2

References

Counting the number of True Booleans in a Python List - Stack Overflow

How to Internationalize Messages in Python

Python アプリケーション内のメッセージの国際化 (i18n) について

思ったよりも面倒だったのでメモ。

tl;dr

GNU gettext API よりもクラスベース API が推奨されている
ロケール辞書の置き場所が必要
翻訳対象のメッセージにマーク _('text') を付けてアプリケーション・コードを書く
ソースコードからカタログ(.po)を作成する。
これを実現するツールは lingua, babel, po-utils, xpot, xgettext など多数ある模様。
カタログを編集して翻訳後の文字列を記述し、コンパイルしてバイナリファイル(.mo)を作成。
そして所定の位置に配備する。

具体例

ソースコード

import gettext

_ = gettext.translation('hello_i18n', 'locale', fallback=True).ugettext

print(_('hello i18n'))
print(_('hello %(world)s') % {'world': 'i18n'})

カタログの作成

今回は、xgettext + msgfmt で実現する。

### Macの場合
$ brew install gettext

### バージョンは環境に合わせて適宜変更
$ /usr/local/Cellar/gettext/0.19.4/bin/xgettext --language=python --from-code=UTF-8 \
--keyword=_ --add-comments=NOTE -o hello_i18n.po hello_i18n.py

$ vi hello_i18n.po

# SOME DESCRIPTIVE TITLE.
# Copyright (C) YEAR THE PACKAGE'S COPYRIGHT HOLDER
# This file is distributed under the same license as the PACKAGE package.
# FIRST AUTHOR , YEAR.
#
#, fuzzy
msgid ""
msgstr ""
"Project-Id-Version: PACKAGE VERSION\n"
"Report-Msgid-Bugs-To: \n"
"POT-Creation-Date: 2015-06-21 23:48+0900\n"
"PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
"Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
"Language-Team: LANGUAGE <LL@li.org>\n"
"Language: \n"
"MIME-Version: 1.0\n"
"Content-Type: text/plain; charset=UTF-8\n"
"Content-Transfer-Encoding: 8bit\n"

#: hello_i18n.py:5
msgid "hello i18n"
msgstr "こんにちは i18n"

#: hello_i18n.py:6
#, python-format
msgid "hello %(world)s"
msgstr "%(world)s、こんにちは"

カタログのコンパイル

$ mkdir -p locale/ja_JP/LC_MESSAGES
$ /usr/local/Cellar/gettext/0.19.4/bin/msgfmt -o locale/ja_JP/LC_MESSAGES/hello_i18n.mo \
./hello_i18n.po

実行結果

$ python2 ./hello_i18n.py
こんにちは i18n
i18n、こんにちは
$ LC_ALL=C python2 ./hello_i18n.py
hello i18n
hello i18n

GNU gettext との結び付きが強すぎるし、コンパイルが必須なのもあって、あまり使う気がしない設計という印象。

References

6.09.2015

HyperLogLog Implementation in Redis, pt.4

Redis: HyperLogLog の実装についてその4

その他のトピック。

要素の追加

追加する要素のハッシュを求め、インデックスと base-2 rank を求める。
各インデックスごとにより大きい値をレジスタに保存するだけ。

データのマージ

$2^{14}$ 個の全てのレジスタを走査し、各位置に対して値の大きいほうを保持する。
非常に高速なマージ処理も HyperLogLog の特長である。

dense 表現について

dense 表現では、sparse 表現と異なり、全部のインデックスの値が配列的に保持されている。

Redis では以下のような構造のバイト配列を定義することで、メモリ使用量を圧縮している。
(各レジスタの値は 0〜50 の範囲内であるため、それぞれ 6 ビットで表現可能)

 * +--------+--------+--------+------//
 * |11000000|22221111|33333322|55444444
 * +--------+--------+--------+------//

sparse から dense へ変換が行われるタイミングは以下。

PFADD
- 追加する要素の base-2 rank が 33 以上だった場合 (sparse では表現不可)
- sparse 表現の使用サイズがサーバ変数 server.hll_sparse_max_bytes を超えた場合
  (デフォルトは 3000)
PFMERGE: マージ実行後は必ず dense 表現になる
PFDEBUG TODENSE key: デバッグ用のコマンド

6.07.2015

HyperLogLog Implementation in Redis, pt.3

Redis: HyperLogLog の実装についてその3

前回は sparse 表現のバイナリについて中身をざっと見た。

今回は HyperLogLog の目的である、カーディナリティを求める処理 pfcount についてその実装を確かめてみる。

カウントのコア部分の処理は hllCount 関数に記述されている。

カウントの求め方

論文によれば、カーディナリティの期待値 $E$ は以下のように求められる。

レジスタの個数を $m$ とする。Redis の場合 $$m = 2^{14} = 16384$$
このとき $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}}$$
ここで $$\alpha_{m} = \left(m \int_{0}^{\infty} \left(\text{log}_2 \left(\frac{2+u}{1+u}\right)\right)^m du\right)^{-1}$$
Redis の場合、これは $\alpha_{m} \approx 0.7213 \cdot \left({1 + \frac{1.079}{m}}\right)^{-1} \approx 0.7213$ で近似される。
また、$M^{(j)}$ は $j$番目のレジスタの値である。

具体的な例

これまで見てきたように、Redis の HyperLogLog 型に "A", "B", "C" という 3つの値を追加すると、レジスタの状態は以下のようになる。

index:4477 -> 3 (C)
index:12352 -> 1 (A)
index:12964 -> 3 (B)
上記以外の index -> 0

この例で実際に $E$ を求めてみる。

$2^0 = 1, \qquad 2^{-1} = 0.5, \qquad 2^{-3} = 0.125$ であるから $$\sum_{j=1}^{m} 2^{-M^{(j)}} = 1 \cdot (m-3) + 0.5 \cdot 1 + 0.125 \cdot 2 = 16381.75$$
したがって $$E = \frac{\alpha_{m}m^2}{\sum_{j=1}^{m} 2^{-M^{(j)}}} \approx \frac{0.7213 \cdot 16384^2}{16381.75} \approx 11819.40$$

実際のカーディナリティは 3 なので、大きなズレがあるように見える。

期待値の補正

このように、HyperLogLog は小さいカーディナリティに対して大きな誤差が出るという性質がある。
この問題を解決するため、Redis では一旦期待値を算出した後で、以下のルールに従ってその値を補正している。

i) $E \lt 2.5 \cdot m = 40960$ かつ値が 0 であるレジスタが存在する場合
以下の式 (Redis のコメントには「LINEARCOUNTING アルゴリズム」と書かれている) によって期待値を計算し直す。値が 0 であるレジスタの個数を $z$ として $$E := m \cdot \text{log} \left( \frac{m}{z} \right)$$

上記の具体例では、$z = 16384 - 3 = 16381$ なので $$E := m \cdot \text{log} \left( \frac{m}{z} \right) = 16384 \cdot \text{log} \left( \frac{16384}{16381} \right) \approx 3.0003$$
正しいカーディナリティ 3 を得ることができた。
ii) i)に該当せず $E \lt 72000$ の場合
以下の多項式バイアスを適用して期待値を調整している。これは $m = 2^{14}$ の場合に限り適用可能。 $$ \begin{align} bias &= 5.9119 \cdot 10^{-18}E^4 - 1.4253 \cdot 10^{-12}E^3 + 1.2940 \cdot 10^{-7}E^2-5.2921 \cdot 10^{-3}E + 83.3216 \\ E :&= E - E \cdot \frac{bias}{100} \end{align}$$
iii) その他の場合は補正なし

こうして得られた値 $E$ を 64ビット非負整数に変換したものが、HyperLogLog型のカウントとして得られる値である。

6.06.2015

easy-scala-bench - Run sbt-jmh in Easy Way

easy-scala-bench - 手軽に sbt-jmh を実行する

ワン・ライナーないしは数行の Scala スクリプトに対して簡単に JMH でマイクロ・ベンチマークを実行できるようにシェルを書いた。

mogproject/easy-scala-bench

前提条件

0.13 系の sbt がインストールされていること
Bash (/bin/bash) が使えること

使い方

リポジトリのクローン

$ cd your/work/dir
$ git clone https://github.com/mogproject/easy-scala-bench.git
$ cd easy-scala-bench

測定したい Scala コードを easy-scala-bench スクリプトの入力に与える
```
$ echo 'for (i <- 1 to 1000) for (j <- 1 to 1000) i + j' | ./easy-scala-bench
```
これだけ。

入力をもとに自動的に Scala コード (src/main/scala/Bench.scala) が生成され、
コマンド sbt 'run -i 3 -wi 3 -f 1 -t 1 easy_scala_bench.Bench' が実行される。
測定対象外の準備コードを書くこともできる
```
$ echo '
val xs = (1 to 1000000).toList
====
xs.length
' | ./easy-scala-bench
```
準備用コードと計測用コードを「====」(イコール 4個完全一致) という行で区切れば、区切り以降のコードだけが計測対象になる。
シェルスクプトに対してシンボリック・リンクを張っても正しく動作する

たとえば
```
ln -s path/to/easy-scala-bench /usr/local/bin/
```
のようにパスの通る場所にリンクを作ってコマンド化してしまえば、実行ファイルのパスを意識する必要がなくなる。

実行例

$ echo 'for (i <- 1 to 1000) for (j <- 1 to 1000) i + j' | ./easy-scala-bench
(snip)
[info] Compiling 1 Scala source to /private/tmp/easy-scala-bench/target/scala-2.11/classes...
[info] Generating JMH benchmark Java source files...
Processing 3 classes from /private/tmp/easy-scala-bench/target/scala-2.11/classes with "reflection" generator
Writing out Java source to /private/tmp/easy-scala-bench/target/scala-2.11/generated-sources/jmh and resources to /private/tmp/easy-scala-bench/target/scala-2.11/classes
[info] Compiling generated JMH benchmarks...
[info] Compiling 1 Scala source and 9 Java sources to /private/tmp/easy-scala-bench/target/scala-2.11/classes...
[info] Running org.openjdk.jmh.Main -i 3 -wi 3 -f 1 -t 1 easy_scala_bench.Bench
[info] # JMH 1.9.1 (released 43 days ago)
[info] # VM invoker: /Library/Java/JavaVirtualMachines/jdk1.7.0_75.jdk/Contents/Home/jre/bin/java
[info] # VM options: 
[info] # Warmup: 3 iterations, 1 s each
[info] # Measurement: 3 iterations, 1 s each
[info] # Timeout: 10 min per iteration
[info] # Threads: 1 thread, will synchronize iterations
[info] # Benchmark mode: Throughput, ops/time
[info] # Benchmark: easy_scala_bench.Bench.bench
[info]
[info] # Run progress: 0.00% complete, ETA 00:00:06
[info] # Fork: 1 of 1
[info] # Warmup Iteration   1: 120.743 ops/s
[info] # Warmup Iteration   2: 214.615 ops/s
[info] # Warmup Iteration   3: 222.462 ops/s
[info] Iteration   1: 226.371 ops/s
[info] Iteration   2: 230.060 ops/s
[info] Iteration   3: 226.733 ops/s
[info]
[info]
[info] Result "bench":
[info]   227.722 ±(99.9%) 37.095 ops/s [Average]
[info]   (min, avg, max) = (226.371, 227.722, 230.060), stdev = 2.033
[info]   CI (99.9%): [190.626, 264.817] (assumes normal distribution)
[info]
[info]
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt    Score    Error  Units
[info] Bench.bench  thrpt    3  227.722 ± 37.095  ops/s
[success] Total time: 17 s, completed Jun 6, 2015 11:08:17 PM

$ echo '
val xs = (1 to 1000000).toList
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt   Score    Error  Units
[info] Bench.bench  thrpt    3  24.990 ± 71.849  ops/s
(snip)
$ echo '
val xs = (1 to 1000000).toList
====
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:07
[info]
[info] Benchmark     Mode  Cnt    Score    Error  Units
[info] Bench.bench  thrpt    3  212.187 ± 35.787  ops/s
(snip)
$ echo '
val xs = (1 to 1000000).toVector
====
xs.length
' | ./easy-scala-bench
(snip)
[info] # Run complete. Total time: 00:00:06
[info]
[info] Benchmark     Mode  Cnt           Score           Error  Units
[info] Bench.bench  thrpt    3  1291414027.800 ± 568908317.371  ops/s
(snip)

How to capture input lines to array in Bash

Bash: 入力された内容を行単位で配列に格納する

readarray は互換性が不十分なので使いたくない。
IFS を正しく扱うのがポイント。

ワンライナー

IFS=$'\n' lines=($(cat))

for ループ

declare -a lines
while IFS= read line; do
    lines+=("$line")
done

実行例

bash-3.2$ IFS=$'\n' lines=($(cat))
  a b  c
d
e
        f

g
bash-3.2$ printf '[%s]\n' "${lines[@]}"
[  a b  c]
[d]
[e   ]
[       f       ]
[g      ]
bash-3.2$ lines=()
bash-3.2$ while IFS= read line; do lines+=("$line"); done
  a b  c
d
e
        f

g
bash-3.2$ printf '[%s]\n' "${lines[@]}"
[  a b  c]
[d]
[e   ]
[       f       ]
[]
[g      ]

References

Shell Script Cheat Sheet

6.02.2015

Implement MurmurHash in Scala

Scala: MurmurHash を実装する

Redis の MurmurHash2 実装をそのまま Scala で書いてみる。

redis/hyperloglog.c at 3.0 · antirez/redis

コード

効率よりも分かりやすさを優先。

object MurmurHash {

  private val defaultSeed = 0xadc83b19L

  def murmurHash64A(data: Seq[Byte], seed: Long = defaultSeed): Long = {
    val m = 0xc6a4a7935bd1e995L
    val r = 47

    val f: Long => Long = m.*
    val g: Long => Long = x => x ^ (x >>> r)

    val h = data.grouped(8).foldLeft(seed ^ f(data.length)) { case (y, xs) =>
      val k = xs.foldRight(0L)((b, x) => (x << 8) + (b & 0xff))
      val j: Long => Long = if (xs.length == 8) f compose g compose f else identity
      f(y ^ j(k))
    }
    (g compose f compose g)(h)
  }

}

13行目は、Redis のコードの big endian の場合の分岐に相当。
Byte 型を 0xff と論理積を取れば、非負の Int 値が手に入る。

実行例

scala> MurmurHash.murmurHash64A("A".getBytes).toHexString
res1: String = fc089b66b14af040

scala> MurmurHash.murmurHash64A("AB".getBytes).toHexString
res2: String = 24fb508dc42efb7f

scala> MurmurHash.murmurHash64A("ABCDEFGHabcdefgh".getBytes).toHexString
res3: String = 40055074d92b389f

scala> MurmurHash.murmurHash64A(Seq.fill[Byte](100)(-1)).toHexString
res4: String = 78be0c4f11cdc6d5

Redis の HyperLogLog で行われるカウント処理の結果も前回の調査内容と一致した。

scala> def count(x: Long): (Int, Int) = (
     |   (x & ((1L << 14) - 1)).toInt,
     |   (14 until 64).find(i => ((x >>> i) & 1L) != 0L).getOrElse(63) - 13
     | )
count: (x: Long)(Int, Int)

scala> count(MurmurHash.murmurHash64A("A".getBytes))
res7: (Int, Int) = (12352,1)

scala> count(MurmurHash.murmurHash64A("B".getBytes))
res8: (Int, Int) = (12964,3)

scala> count(MurmurHash.murmurHash64A("C".getBytes))
res9: (Int, Int) = (4477,3)

mog project: HyperLogLog Implementation in Redis, pt.2

登録: 投稿 (Atom)

mog project

6.22.2015

Counting True in the Python List

References

How to Internationalize Messages in Python

tl;dr

具体例

ソースコード

カタログの作成

カタログのコンパイル

実行結果

References

6.09.2015

HyperLogLog Implementation in Redis, pt.4

要素の追加

データのマージ

dense 表現について

Related Posts

6.07.2015

HyperLogLog Implementation in Redis, pt.3

カウントの求め方

具体的な例

期待値の補正

Related Posts

6.06.2015

easy-scala-bench - Run sbt-jmh in Easy Way

前提条件

使い方

実行例

How to capture input lines to array in Bash

ワンライナー

for ループ

実行例

References

6.02.2015

Implement MurmurHash in Scala

コード

実行例