Vectorは良いのか?

気になるので,Vectorを使う場合とプリミティブな配列で処理したときのパフォーマンス影響を確認してみる.たぶん,Vectorで利用される実装はDenseVectorとRandomAccessSparseVectorあたりな気がするので,これらと比較する.DenseVectorは内部的にはプリミティブ配列と同様に全次元数分の容量を確保する(内部的にはdouble配列だし).RandomAccessSparseVectorは必要な要素だけを確保する(簡単に言うと内部的にはMapみみたいなイメージだと思う).単純に以下のコードで比較してみた.

public void test_performance() {
int count = 100;
int dim = .../*次元数*/;
int testNum = .../*利用した要素数*/;
testDenseVector(count, dim, testNum);
sleep(5000);
testSparseVector(count, dim, testNum);
sleep(5000);
testArrayVector(count, dim, testNum);
sleep(5000);
testDenseVector(count, dim, testNum);
sleep(5000);
testSparseVector(count, dim, testNum);
sleep(5000);
testArrayVector(count, dim, testNum);
}
private void testArrayVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
double[][] data = new double[count][];
for (int i = 0; i < count; i++) {
data[i] = new double[dim];
for (int j = 0; j < testNum; j++) {
data[i][j] = j;
}
}
long heapSize = getHeapSize();
System.out.println("array vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
data[i][j] = j;
}
}
}
private void testDenseVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
DenseVector[] vectors = new DenseVector[count];
for (int i = 0; i < count; i++) {
vectors[i] = new DenseVector(dim);
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
long heapSize = getHeapSize();
System.out.println("dense vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
}
private void testSparseVector(int count, int dim, int testNum) {
long time = System.currentTimeMillis();
long oldHeapSize = getHeapSize();
RandomAccessSparseVector[] vectors = new RandomAccessSparseVector[count];
for (int i = 0; i < count; i++) {
vectors[i] = new RandomAccessSparseVector(dim);
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
long heapSize = getHeapSize();
System.out.println("sparse vector: "
+ (System.currentTimeMillis() - time) + "ms, " + heapSize
+ "MB(" + (heapSize - oldHeapSize) + "MB)");
for (int i = 0; i < count; i++) {
for (int j = 0; j < testNum; j++) {
vectors[i].setQuick(j, j);
}
}
}
private long getHeapSize() {
final Runtime runtime = Runtime.getRuntime();
return (runtime.totalMemory() - runtime.freeMemory()) / 1000000;
}
private void sleep(long time) {
System.gc();
try {
Thread.sleep(time);
} catch (InterruptedException e) {
}
}

GCとかの都合とかもあってスリープとかもろもろ入れておく.

まず,100,000次元で10,000要素を使った場合は

dense vector: 103ms, 80MB(80MB)
sparse vector: 133ms, 37MB(37MB)
array vector: 92ms, 80MB(80MB)

次に,100,000次元で20,000要素を使った場合は

dense vector: 113ms, 80MB(80MB)
sparse vector: 237ms, 67MB(67MB)
array vector: 99ms, 80MB(80MB)

さらに,要素数を25,000にすると

dense vector: 114ms, 80MB(80MB)
sparse vector: 388ms, 110MB(110MB)
array vector: 108ms, 80MB(80MB)

で最後に100,000要素を利用すると

dense vector: 130ms, 80MB(80MB)
sparse vector: 1469ms, 376MB(376MB)
array vector: 110ms, 80MB(80MB)

という感じだった.

というわけで,メモリ的には,次元数の20%以下の利用で済むのであれば,RandomAccessSparseVectorで,それ以上ならDenseVectorが良いかな(時間的なことを考えると,10%くらいでもよいのかも).プリミティブ配列とDenseVectorに大きな差はないけど,若干早いような感じかね.プリミティブ配列で処理するかは,10%の速度向上をとるか,利便性をとるかのどちらが必要かを考えて判断するべきかね.

カテゴリー: Mahout パーマリンク

コメントを残す

メールアドレスが公開されることはありません。

Time limit is exhausted. Please reload the CAPTCHA.