TadaoYamaokaの日記

山岡忠夫 Home で公開しているプログラムの開発ネタを中心に書いていきます。

Javaでリングバッファ

自分が作成しているアプリは音声の波形データを一定サイズバッファしてから、処理するといことをよく行っている。
その際に、メモリを効率よく扱うために、リングバッファを用いている。

リングバッファというのは、固定サイズのバッファに順番に値を書き込んでいき、末尾に達したときに、先頭に戻って書き込むという仕組みのバッファのことを言う。
読み込みの場合も、書き込みと同様に読み込み位置が末尾に達したら先頭に戻って読み込みを行う。

もともと音声解析のプログラムをWindowsで開発していたので、C言語でリングバッファを自分で実装していて、Androidアプリでも同じように実装していたが、
AndroidアプリはJava言語なので、Javaのライブラリに同様の処理を行うクラスがないか気になって調べてみた。

Java リングバッファ」でググったら、検索結果にQueueがでてきたので、
始めリングバッファとQueueが結びつかなかったが、
たしかに、キューでリングバッファと同じことができる。

リングバッファもサイズが固定なだけで、行っていることは、FIFO(先入れ先出し)のキューと同じである。

Javaで、キューを扱うクラスはいくつかあるが、できるだけオーバーヘッドが少ないクラスを探したら、スレッドセーフが不要で固定サイズとなると、ArrayDequeが該当した。

Dequeは、Queueを拡張して、どちら方向からも値の追加と取り出しを行えるようにした仕組みであり、
Queueとしても使うことができる。


さっそくテストコードを書いて試してみたが、ジェネリックスの型の部分にプリミティブ型が使えない。
ラッパークラスを使えばよいが、クラスのインスタンス生成はコストの高い処理なので、要素の追加、削除を頻繁に行う場合、性能面が気になる。

そこで、自分でプリミティブ型で実装したクラスと処理速度を比較してみた。

自分で実装したプリミティブ型(int)のArrayQueueクラス
public class ArrayQueue {
	private int[] elements;
	private int head = 0;
	private int tail = 0;
	
	ArrayQueue(int numElements) {
		elements = new int[numElements];
	}

	public void offer(int e) {
		elements[tail] = e;
		tail = (tail + 1) % elements.length;
	}
	
	public int poll() {
		int result = elements[head];
		head = (head + 1)  % elements.length;
		return result;
	}
}
ArrayDequeとの比較用コード
import java.util.ArrayDeque;
import java.util.Queue;

public class Test {

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		testArrayDeque_manytimes(100000);
		long stop = System.currentTimeMillis();
		System.out.println(stop - start);
		
		start = System.currentTimeMillis();
		testArrayQueue_manytimes(100000);
		stop = System.currentTimeMillis();
		System.out.println(stop - start);
	}

	private static void testArrayDeque_manytimes(int n) {
		Queue<Integer> queue = new ArrayDeque<Integer>(256);

		for (int i = 0; i < n; i++) {
			queue.offer(1);
			queue.offer(2);
	
			queue.poll();
	
			queue.offer(3);
			
			queue.poll();
	
			queue.offer(4);
	
			queue.poll();
			queue.poll();
		}
	}

	private static void testArrayQueue_manytimes(int n) {
		ArrayQueue queue = new ArrayQueue(256);

		for (int i = 0; i < n; i++) {
			queue.offer(1);
			queue.offer(2);
	
			queue.poll();
	
			queue.offer(3);
			
			queue.poll();
	
			queue.offer(4);
	
			queue.poll();
			queue.poll();
		}
	}


測定結果は、

ArrayDeque 15ms
ArrayQueue 9ms

という結果であった。

自分でプリミティブ型で実装したクラス(ArrayQueue)の方が、JavaのArrayDequeよりも1.7倍ほど速かった。
自分の実装よりもJavaのライブラリの方が速いかもと期待していたが、そうでもなかった。

ということで、Androidアプリで使うリングバッファは自分の実装を使うことにする。