読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

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

CodeIQ中の人、millionsmileです。

CodeIQでは、「いかに短いコードを書くか」、というコードゴルフ問題が賑わっていますが、
そんな中、「いかに省メモリのコードを書くか」、という問題を出してみました。

当初予定していたよりも多くの方に挑戦いただいたこともあって、出題者の柳井さんに解説記事を書いていただきました!!

採点では、正解を2つのレベルに分けています。レベル1は、メモリの使用量を減らせてはいるけれど、まだまだ改善の余地のあるプログラムで、レベル2は、レベル1よりもメモリ使用量を減らせている解答です。

今回80名の方に挑戦いただきましたが、レベル2で正解だったのは、56%だそうですよ。

あなたの解答はレベル1でしたか、それともレベル2でしたか?
解説記事を参考にしてみてください。

https://codeiq.jp/ace/yanai_masakazu/q427
f:id:codeiq:20130823164635p:plain

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

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

● 出題について

 2013年8月1日 ~ 2013年8月22日の期間にわたって、メモリの使用量を削減する問題を出題しました。

問題文


 あなたの開発しているアプリケーションでは、メモリの使用量が大きく、その使用量を減らせないかと検討しています。

 データサイズは「10 * 1000 * 1000」であり、各値は「0~3」の整数が入っています。ベンチマークしてみたところ、現在「40000016 byte」の容量を消費しているようです。

 そこで、上手くプログラムを改良して、より少ないメモリーで、情報を保持して、取り出せるようにしてください。



書き換えるコード
package com.crocro.ques;

import java.util.Random;

public class Ques {
	private static final int DATA_SIZE = 10 * 1000 * 1000;
	private static final int DATA_RNG = 4;
	private static final int DATA_SEED = 1234;
	private static Random mRnd = new Random();

	public static void main(String[] args) {
		// 開始時使用メモリ
		long memStrt = Runtime.getRuntime().totalMemory()
			- Runtime.getRuntime().freeMemory();

		// データの初期化
		mRnd.setSeed(DATA_SEED);
		initData();

		// データの確認
		mRnd.setSeed(DATA_SEED);
		boolean res = checkData();

		// 終了時使用メモリ
		long memEnd = Runtime.getRuntime().totalMemory()
			- Runtime.getRuntime().freeMemory();

		// メモリの差分
		long memDif = memEnd - memStrt;

		// 結果出力
		System.out.println(memDif + " " + res);
	}

	// データの生成
	private static int genData(int pos) {
		return mRnd.nextInt(DATA_RNG);
	}

	// データの確認
	private static boolean checkData() {
		boolean res = true;
		for (int i = 0; i < DATA_SIZE; i ++) {
			if (getData(i) != genData(i)) {
				res = false;
				break;
			}
		}
		return res;
	}
	//--------------------------------------------------
	// 以降、ユーザーが書き換えて改良する部分

	// データを保持する変数
	private static int[] mData = null;

	// データの初期化
	private static void initData() {
		mData = new int[DATA_SIZE];
		for (int i = 0; i < DATA_SIZE; i ++) {
			mData[i] = genData(i);
		}
	}

	// データの取得
	private static int getData(int pos) {
		return mData[pos];
	}
	//--------------------------------------------------
}

 解答者は、この問題の出題意図を読み取り、適切な解答を返さなければなりません。

 それでは問題に隠されている意図はなんでしょうか? タイトルや問題文、問題中のソースコードから、それらの情報は読み取ることができます。

 以下、問題から読み取れる出題意図を書いていきます。


○ メモリの使用量を削減する問題である

 この問題は、タイトルに「メモリを配慮したしたプログラムを書こう」と書いてあります。

 また問題文にも「メモリの使用量が大きく、その使用量を減らせないかと検討しています」「より少ないメモリーで、情報を保持して、取り出せるようにしてください」と書いてあります。

 そのため、出力結果の値が見かけ上減るようなプログラムを書いても、問題の答えとしては相応しくないということになります。


○ DATA_RNG = 4

 問題を解く鍵は、コード中の「DATA_RNG = 4」の部分になります。この値については、問題文中にも「各値は『0~3』の整数が入っています」と、記されています。

 この部分を見てピンと来た人は、この問題を簡単に解くことができます。


○ データの生成

 次にデータの生成部分のコードを見ます。

データの生成
	private static final int DATA_RNG = 4;
	private static Random mRnd = new Random();

	// データの生成
	private static int genData(int pos) {
		return mRnd.nextInt(DATA_RNG);
	}

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

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


● 問題を解く上での予備知識

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

 Javaの基本データ型は、内部に格納するデータのビット数が決まっています。

型名 ビット数
boolean 1
char 16
byte 8
short 16
int 32
long 64
float 32
double 64

 そして配列として初期化した際は、以下の表のようにメモリーを消費します。

型名 出力バイト数 ビット数変換 型ビット数 (メモリ-128)/ビット数
boolean 10000016 80000128 1 80000000
char 20000016 160000128 16 10000000
byte 10000016 80000128 8 10000000
short 20000016 160000128 16 10000000
int 40000016 320000128 32 10000000
long 80000016 640000128 64 10000000

 この値を求めたプログラムも掲載しておきます。問題文と同じように、要素数は「10,000,000(1千万)」の場合です。

実験用のコード
package com.crocro.ques;

public class Ques {
	private static final int DATA_SIZE = 10 * 1000 * 1000;

	public static void main(String[] args) {
		// 開始時使用メモリ
		long memStrt = Runtime.getRuntime().totalMemory()
			- Runtime.getRuntime().freeMemory();

		// データの初期化
		initData();

		// 終了時使用メモリ
		long memEnd = Runtime.getRuntime().totalMemory()
			- Runtime.getRuntime().freeMemory();

		// メモリの差分
		long memDif = memEnd - memStrt;

		// 結果出力
		System.out.println(memDif);
	}

	// データを保持する変数
	private static boolean[] mBoolean = null;
	private static char[] mChar = null;
	private static byte[] mByte = null;
	private static short[] mShort = null;
	private static int[] mInt = null;
	private static long[] mLong = null;

	// データの初期化
	private static void initData() {
		//mBoolean = new boolean[DATA_SIZE];
		//mChar = new char[DATA_SIZE];
		//mByte = new byte[DATA_SIZE];
		//mShort = new short[DATA_SIZE];
		//mInt = new int[DATA_SIZE];
		mLong = new long[DATA_SIZE];
	}
}

 上記の表から、「(データサイズ×型のビット数+128)÷8」が出力バイト数になっていることが分かります。この時「128ビット」は、配列変数自体を表す情報だと想像が付きます。

 さて、ここで注意しなければならないことがあります。それは「boolean」です。「true」「false」の2値を表す「boolean」ですが、内部的には「byte」と同じメモリ量を消費しています。もし、「boolean」で配列を作る際は、このことに注意しなければなりません。


● 解答について

 この問題は、「レベル1正解」「レベル2正解」という、2つの正解の段階を用意していました。以下、それぞれの特徴について説明します。


○ レベル1正解

 メモリの使用量を減らせてはいるけれど、まだまだ改善の余地のあるプログラムです。具体的に言うと、「int」の配列を「byte」の配列にする改良を行った場合です。この時の出力結果は「10000016」になります。

レベル1正解のコード
	// データを保持する変数
	private static byte[] mData = null;

	// データの初期化
	private static void initData() {
		mData = new byte[DATA_SIZE];
		for (int i = 0; i < DATA_SIZE; i ++) {
			mData[i] = (byte)genData(i);
		}
	}

	// データの取得
	private static int getData(int pos) {
		return mData[pos];
	}

 この種類の解答には、データを格納する配列を「short」や「char」にしている人もいました。いずれもメモリ量を削減できてはいますが、まだまだ減らすことが可能な状態になっています。


○ レベル2正解1

 レベル1正解よりも、メモリ使用量を減らせている解答です。ビットシフトを使い、1つの値の中に複数のデータを格納します。

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

 以下、解答例を示します。この時の出力結果は「2500016」になります。

レベル2正解1のコード
	// データを保持する変数
	private static int[] mData = null;

	private static final int BIT_SIZE = 2;
	private static final int MSK = 3;

	private static final int BIT_NO = Integer.SIZE / BIT_SIZE;
	private static final int DATA_SIZE2 =
		DATA_SIZE / BIT_NO + (DATA_SIZE % BIT_NO == 0 ? 0 : 1);

	// データの初期化
	private static void initData() {
		mData = new int[DATA_SIZE2];
		for (int i = 0; i < DATA_SIZE; i ++) {
			int d = genData(i);
			mData[i / BIT_NO] |= d << i % BIT_NO * BIT_SIZE;
		}
	}

	// データの取得
	private static int getData(int pos) {
		return (mData[pos / BIT_NO] >> pos % BIT_NO * BIT_SIZE) & MSK;
	}

 それほど複雑ではないコードで、メモリ使用量を削減できているのが分かると思います。

 以下、少しだけ解説です。

 Javaでは、基本データ型を初期化した場合は、0で初期化されることが仕様上保障されています。そのため、初期化後の値に、そのまま「|=」で値を連結しています。

 こういった手法で解答した人の中には、「DATA_RNG」の値が4以外になった場合にも対応できるようにプログラムを書いている人も多かったです。本記事では、ロジックのみを示すために、簡単に書きました。

 また、ロジックは合っていても惜しいミスを犯している人もいました。Javaの「int」は32ビットですが、16ビットと勘違いしてプログラムを書いている人がいました。

 他には、「int」配列ではなく、「boolean」配列にデータを格納してしまっている人もいました。前述の通り、「boolean」は1ビットではなく、8ビット消費してしまいます。


○ レベル2正解2

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

レベル2正解2のコード
	// データを保持する変数
	private static java.util.BitSet mData = null;

	private static final int BIT_SIZE = 2;
	private static final int DATA_SIZE2 = DATA_SIZE * BIT_SIZE;

	// データの初期化
	private static void initData() {
		mData = new java.util.BitSet(DATA_SIZE2);
		for (int i = 0; i < DATA_SIZE; i ++) {
			int d = genData(i);
			for (int j = 0; j < BIT_SIZE; j ++) {
				mData.set(i * BIT_SIZE + j, (d >> j & 1) == 1);
			}
		}
	}

	// データの取得
	private static int getData(int pos) {
		int res = 0;
		for (int j = 0; j < BIT_SIZE; j ++) {
			res += (mData.get(pos * BIT_SIZE + j) ? 1 : 0) << j;
		}
		return res;
	}

 「int」配列などを使った場合は、データ型のビットサイズを、データのビットサイズで割り切れない場合のロスが生じます。


 しかし、こちらの方式では、そういった問題は起きないので、より効率的にプログラムを書けるでしょう。

 ただし、Javaの機能に依存したコードなので、移植性は低くなります。今後の用途によって、どういった方法を使うか選択すればよいでしょう。


○ その他の解

 データをメモリーに保持せず、テンポラリー ファイルを作り、HDDに値を直接書き込むことで、メモリの使用量を減らしている方もいました。

 その解答では、ビット単位でデータを保存することで、データ量自体を最少にしており、問題の意図を理解して、解決した上で、さらにその先を考えていました。

 環境によっては、この方法もありだと思いました。「環境によっては」と書いたのは、HDDにアクセスする分、実行速度が非常に遅かったからです。

 いろいろな解答方法があるのだなあと思いました。

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

CodeIQ中の人後記:

昨日、自宅のmacが予告なしでお亡くなりになりました。起動すらしないという・・・
気のせいにしたいと思って、一晩寝て、アレは夢だったと言いたかったのですが現実はそうではありませんでした。

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る