'二次元のキーに対する値を保持するデータ構造'の実装方法(Java)

個人的に作成しているデータ集計用のプログラムで、二次元の表形式のデータ構造を利用したかったため、その実装方法を考えてみました。

実装方針を決める

軽くWebを探した限りでは、いずれのケースでも、JDKのCollection型を組み合わせて実現しています。組み合わせ方に関しては、以下2通りの方法を採るケースがほとんどのようです。

1．Mapの値として、さらにMapを持たせる：Map<R, Map<C, V>>
2．Mapのキーに、要素数 2のListを用いる：Map<List, V>

今回は、上記のいずれかを用いることにしました。これらををラップして、put() や get() でデータの出し入れができるようにします。 また、ラップするCollectionの実装型には、1. ではHashMapを、2.ではArrayListとHashMapを使います。

パフォーマンスを検討する

1．と2．のどちらかを選択するために、パフォーマンスを測って比較してみました。 キー、値はすべてString型にしています。 1,000 × 1,000 = 1,000,000 通りのキーの組み合わせに対して値を put/get する操作を1試行とし、100 試行の平均所要時間を出しました。 以下、計測結果です。

- put() [ms] get()[ms]
1．Map<R, Map<C, V>> 85 42
2．Map<List, V> 1753 1229


結論

1．Map<R, Map<C, V>>は、2．Map<List, V>に比べて、圧倒的に速いです（put で20分の1、get で30分の1の処理時間）。 というわけで、今回は1. を採用することにしました。


コード（付録）

インターフェース Table

/**
 * テーブルのインターフェース
 * テーブルは、二次元のキーに対する値を保持するデータ形式
 */
public interface Table<R, C, V> {


    /**
     * テーブルに値を追加する
     *
     * @param rowKey テーブルの行
     * @param columnKey テーブルの列
     * @param value 値
     */
    public void put(R rowKey, C columnKey, V value);


    /**
     * テーブルから値を取得する
     *
     * @param rowKey
     * @param columnKey
     * @return
     */
    public V get(R rowKey, C columnKey);
}

HashMapsTable（Tableを入れ子のHashMapを使って実装したもの）

import java.util.HashMap;
import java.util.Map;


/**
 * HashMapを入れ子にすることによりテーブルを実現する、Tableインターフェースの実装
 *
 * @param <R> 行
 * @param <C> 列
 * @param <V> 値
 */
public class HashMapsTable<R, C, V> implements Table<R, C, V> {


    private Map<R, Map<C, V>> table = new HashMap<R, Map<C, V>>();


    @Override
    public void put(R rowKey, C columnKey, V value) {
        Map<C, V> row = table.get(rowKey);
        if (row == null) {
            row = new HashMap<C, V>();
            table.put(rowKey, row);
        }
        row.put(columnKey, value);
    }


    @Override
    public V get(R rowKey, C columnKey) {
        Map<C, V> row = table.get(rowKey);
        if (row == null) {
            return null;
        }
        return row.get(columnKey);
    }


}

ArrayListAndHashMapTable（TableをArrayListをキーとしたHashMapを使って実装したもの）

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


/**
 * ArrayListをキーとしたHashMapによりテーブルを実現する、Tableインターフェースの実装
 *
 * @param <R> 行
 * @param <C> 列
 * @param <V> 値
 */
public class ArrayListAndHashMapTable<R, C, V> implements Table<R, C, V> {


    private Map<List<Object>, V> table = new HashMap<List<Object>, V>();


    @Override
    public void put(R rowKey, C columnKey, V value) {
        List<Object> key = new ArrayList<Object>(2);
        key.add(0, rowKey);
        key.add(1, columnKey);
        table.put(key, value);
    }


    @Override
    public V get(R rowKey, C columnKey) {
        List<Object> key = new ArrayList<Object>(2);
        key.add(0, rowKey);
        key.add(1, columnKey);
        return table.get(key);
    }
}

パフォーマンス測定（メイン）

public class Test {


    /*
     *  keyとvalue
     *  行、列のサイズをそれぞれ1000とし、全てのキーの組み合わせに対する値を用意する
     *  キー、値の型はすべてString
     */
    private static final int COLUMN_SIZE = 1000;
    private static final String[] COLUMN_KEYS = new String[COLUMN_SIZE];
    static {
        for (int i = 0; i < COLUMN_KEYS.length; i++) {
            COLUMN_KEYS[i] = "C" + i;
        }
    }
    private static final int ROW_SIZE = 1000;
    private static final String[] ROW_KEYS = new String[ROW_SIZE];
    static {
        for (int i = 0; i < ROW_KEYS.length; i++) {
            ROW_KEYS[i] = "R" + i;
        }
    }
    private static final String[][] VALUES =
            new String[COLUMN_KEYS.length][ROW_KEYS.length];
    static {
        for (int i = 0; i < COLUMN_KEYS.length; i++) {
            for (int j = 0; j < ROW_KEYS.length; j++) {
                VALUES[i][j] = COLUMN_KEYS[i] + ROW_KEYS[j];
            }
        }
    }


    private static final int TRIAL_NUMBER = 100;


    /**
     * main関数
     *
     * @param args
     */
    public static void main(String[] args) {
        long elapsed_put = 0, elapsed_get = 0;
        long mean_put = 0, mean_get = 0;


        System.out.println("----- Map-Map table. -----");
        for (int i = 0; i < TRIAL_NUMBER; i++) {
            Table<String, String, String> mm =
                    new HashMapsTable<String, String, String>();
            elapsed_put += testPut(mm, COLUMN_KEYS, ROW_KEYS, VALUES);
            elapsed_get += testGet(mm, COLUMN_KEYS, ROW_KEYS);
        }
        mean_put = elapsed_put / TRIAL_NUMBER;
        mean_get = elapsed_get / TRIAL_NUMBER;
        System.out.println("elapsed mean time of...");
        System.out.println("    put(): " + mean_put + " [ms]");
        System.out.println("    get(): " + mean_get + " [ms]");


        elapsed_put = 0;
        elapsed_get = 0;


        System.out.println("----- List-Map table. -----");
        for (int i = 0; i < TRIAL_NUMBER; i++) {
            Table<String, String, String> lm =
                    new ArrayListAndHashMapTable<String, String, String>();
            elapsed_put += testPut(lm, COLUMN_KEYS, ROW_KEYS, VALUES);
            elapsed_get += testGet(lm, COLUMN_KEYS, ROW_KEYS);
        }
        mean_put = elapsed_put / TRIAL_NUMBER;
        mean_get = elapsed_get / TRIAL_NUMBER;
        System.out.println("elapsed mean time of...");
        System.out.println("    put(): " + mean_put + " [ms]");
        System.out.println("    get(): " + mean_get + " [ms]");
    }




    /**
     * テーブルの全ての要素に値を設定する
     * 1,000 * 1,000 で、1,000,000回の処理
     */
    private static long testPut(Table<String, String, String> table,
            String[] c_keys, String[] r_keys, String[][] values) {
        if (c_keys == null || r_keys == null || values == null) {
            throw new NullPointerException();
        }
        if (c_keys.length != values.length
                || r_keys.length != values[0].length) {
            throw new IllegalArgumentException();
        }


        long begin = System.currentTimeMillis();
        for (int i = 0; i < c_keys.length; i++) {
            for (int j = 0; j < r_keys.length; j++) {
                table.put(c_keys[i], r_keys[j], values[i][j]);
            }
        }
        long end = System.currentTimeMillis();
        return end - begin;
    }


    /**
     * テーブルの全ての要素の値を取得する
     * 1,000 * 1,000 で、1,000,000回の処理
     */
    private static long testGet(Table<String, String, String> table,
            String[] c_keys, String[] r_keys) {
        if (c_keys == null || r_keys == null) {
            throw new NullPointerException();
        }


        long begin = System.currentTimeMillis();
        for (int i = 0; i < c_keys.length; i++) {
            for (int j = 0; j < r_keys.length; j++) {
                String value = table.get(c_keys[i], r_keys[j]);
//                System.out.print(value + " ");
            }
//            System.out.println();
        }
        long end = System.currentTimeMillis();
        return end - begin;
    }


}