Hadoopだけど可変長整数さえあれば関係ないよねっ (2) ~データを加工して可変長整数の効果を高める~

[前回][link-1] のサンプルでは、日時の配列をWritableでシリアライズした結果を固定長整数と可変長整数で比較してみたが、可変長整数を使用してもそれほど大きな効果はなかった。
今回はデータを加工することで可変長整数の効果を高める方法を解説する。

# 前回のサンプルデータと結果

データは時系列に並んだ10個のlong型タイムスタンプ値。

```java
        long[] timestamps = {
                timestamp("2014-08-01 00:00:00"),
                timestamp("2014-08-01 00:05:30"),
                timestamp("2014-08-01 00:10:42"),
                timestamp("2014-08-01 00:15:15"),
                timestamp("2014-08-01 00:20:31"),
                timestamp("2014-08-01 13:15:10"),
                timestamp("2014-08-01 13:20:16"),
                timestamp("2014-08-01 13:24:47"),
                timestamp("2014-08-01 13:31:31"),
                timestamp("2014-08-01 13:40:05"),
        };
```

実行結果

|シリアライズ方法|サイズ|
|----|----:|
|固定長整数|84|
|可変長整数|71|

# 前回の結果があまり効果がなかったのはなぜか？

ひとことで言うと、値が大きいから。

Javaでは日時を1970年1月1日00:00:00 GMTからの経過ミリ秒数で表し、long型で保持する。
今日現在あたりだと10進数で13桁程度の数値になり、これを可変長整数にすると7バイトになる。

```java:
long t = System.currentTimeMillis();
System.out.println(t);
System.out.println("size=" + WritableUtils.getVIntSize(t));
```
```
1408878513200
size=7
```

可変長整数は小さい値のサイズは小さくなるが、大きい値だとあまり小さくならないか、逆に固定長より大きくなってしまう。
では日時のような大きい値を扱う場合には可変長整数は使用しない方がいいのか？

そんなことはない。小さくすればいいのである。

# 整数値を小さい値に加工する

## 大きいなら　切り捨ててしまえ　整数値

Javaの日時はミリ秒単位まで保持するが、実際に扱うデータでは秒単位だったり、日付だけという事もある。
あるいは、データがミリ秒まで持っていてもそのデータを使う処理が秒単位までしか必要ないという事もある。
そんな時には不要な部分を切り捨ててしまえばいいのである。

秒単位にした日時を可変長整数にすると5バイト、日付だと3バイトにまで縮小できる。

```java
long ms = System.currentTimeMillis();
System.out.println("ms=" + ms);
System.out.println("size=" + WritableUtils.getVIntSize(ms));
long sec = ms / 1000;
System.out.println("sec=" + sec);
System.out.println("size=" + WritableUtils.getVIntSize(sec));
long date = ms / 24 / 60 / 60 / 1000;
System.out.println("date=" + date);
System.out.println("size=" + WritableUtils.getVIntSize(date));
```
```
ms=1408878478903
size=7
sec=1408878478
size=5
date=16306
size=3
```

## 大きいなら　相対値にしてみせよう　整数値

ソートされた時刻の配列をシリアライズする場合には、前の時刻からの相対値(つまり前の時刻からの経過時間)に変換すると値は小さくなる。
こうすると秒単位であれば経過時間が1分以内(60秒)で1バイト、1日以内(86400秒)なら4バイトでシリアライズできる。

```java
System.out.println("1分以内=" + WritableUtils.getVIntSize(60));
System.out.println("1日以内=" + WritableUtils.getVIntSize(24*60*60));
```
```
1分以内=1
1日以内=4
```

## 大きいなら　鳴くまで待とう　整数値

いくら待っても整数は鳴いてくれないが、その間にサンプルデータをよく観察してみると約5分間隔でデータが並んでいる部分が多いのがわかる。
であれば「前の時刻から5分後」を基準にした相対値にすれば値をもっと小さくできる。

# サンプルコード

## 可変長整数をそのまま使う

先ずは前回の可変長整数をそのまま使うコードに、各要素の値とサイズを表示するコードを追加しておく。

```java:TimestampArray.java
    @Override
    public void readFields(DataInput in) throws IOException {
        int len = WritableUtils.readVInt(in);
        timestamps = new long[len];
        for (int i = 0; i < len; i++) {
            timestamps[i] = WritableUtils.readVLong(in);
        }
    }
    @Override
    public void write(DataOutput out) throws IOException {
        WritableUtils.writeVInt(out, timestamps.length);
        for (long timestamp : timestamps) {
            int size = WritableUtils.getVIntSize(timestamp);
            System.out.println("" + timestamp + ":" + size);
            WritableUtils.writeVLong(out, timestamp);
        }
    }
```
```
1406818800000:7
1406819130000:7
1406819442000:7
1406819715000:7
1406820031000:7
1406866510000:7
1406866816000:7
1406867087000:7
1406867491000:7
1406868005000:7
size=71
```

## ミリ秒を切り捨てる

```java:TimestampArray.java
    @Override
    public void readFields(DataInput in) throws IOException {
        int len = WritableUtils.readVInt(in);
        timestamps = new long[len];
        for (int i = 0; i < len; i++) {
            timestamps[i] = WritableUtils.readVLong(in) * 1000;
        }
    }
    @Override
    public void write(DataOutput out) throws IOException {
        WritableUtils.writeVInt(out, timestamps.length);
        for (long timestamp : timestamps) {
            long value = timestamp / 1000;
            int size = WritableUtils.getVIntSize(value);
            System.out.println("" + timestamp + "->" + value + ":" + size);
            WritableUtils.writeVLong(out, value);
        }
    }
```
```
1406818800000->1406818800:5
1406819130000->1406819130:5
1406819442000->1406819442:5
1406819715000->1406819715:5
1406820031000->1406820031:5
1406866510000->1406866510:5
1406866816000->1406866816:5
1406867087000->1406867087:5
1406867491000->1406867491:5
1406868005000->1406868005:5
size=51
```

## 前の時刻からの経過時間にする

```java:TimestampArray.java
    @Override
    public void readFields(DataInput in) throws IOException {
        int len = WritableUtils.readVInt(in);
        timestamps = new long[len];
        long prev = 0;
        for (int i = 0; i < len; i++) {
            timestamps[i] = WritableUtils.readVLong(in) * 1000 + prev;
            prev = timestamps[i];
        }
    }
    @Override
    public void write(DataOutput out) throws IOException {
        WritableUtils.writeVInt(out, timestamps.length);
        long prev = 0;
        for (long timestamp : timestamps) {
            long value = (timestamp - prev) / 1000;
            int size = WritableUtils.getVIntSize(value);
            System.out.println("" + timestamp + "->" + value + ":" + size);
            WritableUtils.writeVLong(out, value);
            prev = timestamp;
        }
    }
```
```
1406818800000->1406818800:5
1406819130000->330:3
1406819442000->312:3
1406819715000->273:3
1406820031000->316:3
1406866510000->46479:3
1406866816000->306:3
1406867087000->271:3
1406867491000->404:3
1406868005000->514:3
size=33
```

## 前の時刻から5分後を基準にする

```java:TimestampArray.java
    @Override
    public void readFields(DataInput in) throws IOException {
        int len = WritableUtils.readVInt(in);
        timestamps = new long[len];
        long prev = 0;
        for (int i = 0; i < len; i++) {
            timestamps[i] = (WritableUtils.readVLong(in) + 300) * 1000 + prev;
            prev = timestamps[i];
        }
    }
    @Override
    public void write(DataOutput out) throws IOException {
        WritableUtils.writeVInt(out, timestamps.length);
        long prev = 0;
        for (long timestamp : timestamps) {
            long value = (timestamp - prev) / 1000 - 300;
            int size = WritableUtils.getVIntSize(value);
            System.out.println("" + timestamp + "->" + value + ":" + size);
            WritableUtils.writeVLong(out, value);
            prev = timestamp;
        }
    }
```
```
1406818800000->1406818500:5
1406819130000->30:1
1406819442000->12:1
1406819715000->-27:1
1406820031000->16:1
1406866510000->46179:3
1406866816000->6:1
1406867087000->-29:1
1406867491000->104:1
1406868005000->214:2
size=18
```

# 結果まとめ

|シリアライズ方法|サイズ|
|----|----:|
|固定長整数|84|
|そのまま可変長整数を使う|71|
|ミリ秒を切り捨てる|51|
|前の時刻からの経過時間にする|33|
|5分後を基準にする|18|

単純に可変長整数を使うだけでは効果が小さかったが、データを加工することで元の約1/4のサイズにできた。

# 次回は...

次回は、Hadoopの可変長整数ではなく、独自ロジックで整数をシリアライズする例を紹介する。

------------

記事一覧

[(1) Writableで可変長整数を使う][link-1]
(2) データを加工して可変長整数の効果を高める
[(3) 独自ロジックで整数をシリアライズする][link-3]

[link-1]:http://qiita.com/tag1216/items/4c5349bfe612484d3ce5 "(1) Writableで可変長整数を使う"
[link-3]:http://qiita.com/tag1216/items/68c14bab2e583866a00d "(3) 独自ロジックで整数をシリアライズする"