VBCode を Java で実装する

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)

はてなほどの規模ではないが、自分も Webサービスを提供する会社に勤めているので、とても興味深く読ませてもらいった。

でも、読むだけだと身にならないので、第6回の演習課題を Java で実装してみることにする。

byte だとキャストをいっぱい書かなきゃいけないので、さぼって計算は int でやってます。

import java.util.LinkedList;
import java.util.List;

public class VBCode {
	
	private static final int MASK = 128;
	
	private VBCode() {
	}

	/**
	 * 整数を VBCode にエンコードする。
	 *  
	 * @param n　エンコード対象整数
	 * @return エンコード結果
	 */
	public static List<Integer> encode(int n) {
		LinkedList<Integer> bytes = new LinkedList<Integer>();
		while(true) {
			bytes.push(n % MASK);
			if (n < MASK) {
				break;
			}
			n = n / MASK;
		};
		bytes.set(bytes.size() - 1, bytes.peekLast() + MASK);
		return bytes;
	}
	
	/**
	 * VBCode を整数にデコードする
	 *  
	 * @param  vb デコード対象
	 * @return デコード結果
	 */
	public static int decode(Integer[] vb) {
		int n = 0;
		for (int i=0; i<vb.length; ++i) {
			if (vb[i].intValue() < MASK) {
				n = MASK*n + vb[i];
			} else {
				n = MASK*n + (vb[i] - MASK);
			}
		}
		return n;
	}
		
}

で、これを利用してエンコードするコード例が以下。

public class Encode {
	
	public static void main(String[] args) throws IOException {
		System.out.println("start");
		long start = System.currentTimeMillis();
			
		BufferedOutputStream out = new BufferedOutputStream(new FileOutputStream("vbcode.bin"));
		BufferedReader reader = new BufferedReader(new FileReader("eid_tags.txt"));
		String line = null;
		while (reader.ready()) {
			line = reader.readLine();
			String[] vars = line.split("\t");
			if (vars.length != 2) {
				continue;
			}
			byte[] tag = vars[0].getBytes();
			String nums = vars[1];
		
			List<Integer> vb = new ArrayList<Integer>();
			int pre = 0;
			for (String s : nums.split(",")) {
				int v = Integer.valueOf(s);
				vb.addAll(VBCode.encode(v - pre));
				pre = v;
			}
			out.write(tag.length);
			out.write(vb.size());
			out.write(tag);
			for (Integer v : vb) {
				out.write(v);
			}
		}
		
		out.close();
		
		System.out.printf("end (process time = %dms)", System.currentTimeMillis() - start);
	}

で、これでできたんだけど、実際に サポートページ書籍サポート：［Web開発者のための］大規模サービス技術入門 ―データ構造，メモリ，OS，DB，サーバ/インフラ：｜gihyo.jp … 技術評論社 からサンプルデータをダウンロードしてきて実行してみたら、Core2 Duo E7200(2.53GHz)でエンコードに 25〜30秒くらいかかる。
本では Core2 Duo T7200(2GHz)で3秒って書いてあるんですが・・・

ただ、2700万回くらいメソッド呼び出しがあるので、1回あたりの処理時間が 0.001ms だとしても、27秒かかる計算なので、こんなもんだという気もするが・・・うーん、大規模データの扱いは奥が深いな。

時間のあるときプロファイリングでもしてみよっと