codeiq427Java「メモリを配慮したプログラムを書こう」

Java「メモリを配慮したプログラムを書こう」問題解説記事～レベル2で正解は56% #java #memory - CodeIQ Blog

ランダムを使っています。これは、出題者からの「データは圧縮することで小さくはなりません」という暗黙のメッセージです。

データの圧縮以外の方法でデータ量を削減してほしい。そういった意図を読み取り、プログラムを書かなければなりません。

えっ．そうだったのか．いやしかしなるほど，せやろな．

Javaの基本データ型のビット数

まずこの仕様を確かめた．とほほのJava入門からbyteが1バイトと知って，とりあえずデータ型変更した．およそ4分の1になった．

boolean2個を持ったクラスを作った．どうせ1バイト丸々使っちゃって，半分だろうなと思ったら5倍になった．newするときのサイズ指定を誤ったのだろう．

「genData」関数で生成される数値は、「0～3」の4つです。これは2ビットで表現可能です。「int」は32ビットありますので、16個のデータを格納可能なことが分かります。

はい，これで回答した．15分の1になった．

レベル2正解には、もう1つの方法があります。Javaには、ビット値を効率的に格納する「java.util.BitSet」というクラスがあります。このクラスを使いプログラムを書いても、出力結果は「2500016」になります。

そうだよ何か便利な機能が備わっていたようなと思っていたけれどあるじゃないか使えば良かった．あああああ．

CodeIQはNetBeansでテストしている．プロジェクト名は問題番号だけでなく，問題内容を窺えるようにしようと思った．

メモリ削減の様子

/*
 * 初期状態
 *  39948160 true
 * データ型変更
 *  mDataの要素は0, 1, 2, 3の4とおりしかない．byteで足りる．
 *  10000016 true
 * データ型変更
 *  データクラスBitsDataを作成．2ビットで保持
 *  200676816 true
 * データ型変更
 *  int配列に2ビットずつ突っ込む
 *  19948872 true
 * 見直し
 *  DataContainer.data の確保領域計算を修正した
 *  2590600 true
 */

内部にprivate static class DataContainerを作った

マジックナンバー「3」……．一度きりだし，コメント付けたし良いよね．ね．「AMD」は投稿後に気付いた．

    /**
     * 2ビットデータコンテナクラス
     */
    private static class DataContainer {

        // データ
        private int data[];
        // データは 0, 1, 2, 3 以上4パターン限りゆえ，2ビットで表現できる
        private static final int DATA_BITS = 2;

        /**
         * サイズを設定する
         * @param dataNum データ個数
         */
        DataContainer(int dataNum) {
            if (dataNum % DATA_BITS > 0) {
                // 余剰がある場合は1個大きくする
                // 32bit/2bit 16個
                // 確保する領域は dataNum/16個 + alpha
                data = new int[dataNum / (Integer.SIZE / DATA_BITS) + 1];
            } else {
                data = new int[dataNum / (Integer.SIZE / DATA_BITS)];
            }
        }

        /**
         * データ書き込み
         * 書き換えはできない
         * @param pos 位置
         * @param data データ
         */
        public void setData(int pos, int data) {
            // 入力データを挿入位置に合わせるためシフト
            int shifted = data << (pos % (Integer.SIZE / 2) * DATA_BITS);
            // 入力先は 00(2) なので OR で入力できる．書き換えは出来ない
            this.data[pos / (Integer.SIZE / 2)] |= shifted;
        }

        /**
         * データ読み出し
         * @param pos
         * @return データ
         */
        public int getData(int pos) {
            // 3は11(2)．読み出し位置に合わせるためシフトする
            int mask = 3 << (pos % (Integer.SIZE / 2) * DATA_BITS);
            // AMD でデータ抽出
            int data = this.data[pos / (Integer.SIZE / 2)] & mask;
            // シフトして値取り出し
            return data >>> (pos % (Integer.SIZE / 2) * DATA_BITS);
        }
    }