LoginSignup
0
1

More than 1 year has passed since last update.

javascriptで1次元配列を2次元配列として扱う手法は速いのか?

Posted at

javascriptで1次元配列を2次元配列として扱う手法は速いのか?

2次元配列を素直に実装するのとn x m の1次元配列を確保して2次元配列として取り扱う方法で速度差はあるのかと疑問に思ったので実験してみました

方法A(素直な実装)

        // このように確保して
        var x = new Array(rows);
        for(var i = 0; i < rows; i += 1) {
            x[i] = new Array(cols);
        }
        // このように参照する
        x[i][j]

方法B(1次元配列を2次元配列として扱う)

        // このように確保して
        var x = new Array(rows * cols);
        // このように参照する
        for(var r = 0; r < rows; r += 1) {
            for(var c = 0; c < cols; c += 1) {
                x[r * cols + c];
            }
        }

実験方法

各列の合計値を求める速度で速度計測します

結果

”差”は「方法Aの計測時間 - 方法Bの計測時間」

(100行、10000列) x 100回

方法A 方法B
1回目 3667ms 3218ms 449ms
2回目 3349ms 2850ms 499ms
3回目 3328ms 2833ms 495ms
4回目 3220ms 2883ms 337ms
5回目 3403ms 2964ms 439ms

(10000行、100列) x 100回

方法A 方法B
1回目 3257ms 2856ms 401ms
2回目 3245ms 2913ms 332ms
3回目 3256ms 2850ms 406ms
4回目 3300ms 2835ms 465ms
5回目 3330ms 2832ms 498ms

1次元配列で確保するほうが若干速い

1次元配列で確保して2次元配列としてしまう方法の方が速いという結果になりました
JavaScriptの実装まで追う気は無いので何故速いのかまではわかりません

実験に使用したソース


function exit(n) {
    process.exit(n);
}

function Number2D_A() {
    var self = this;
    self.create = function(rows, cols) {
        var me = this;
        var x = new Array(rows);
        for(var i = 0; i < rows; i += 1) {
            x[i] = new Array(cols);
        }
        return x;
    }
    self.rand = function(rows, cols) {
        var me = this;
        var x = me.create(rows, cols);
        for(var i = 0; i < rows; i += 1) {
            for(var j = 0; j < cols; j += 1) {
                x[i][j] = Math.random();
            }
        }
        return x;
    }
    self.col_sum = function(x, rows, cols) {
        var y = new Array(cols).fill(0);
        for(var r = 0; r < rows; r += 1) {
            for(var c = 0; c < cols; c += 1) {
                y[c] += x[r][c];
            }
        }
        return y;
    }
}

function Number2D_B() {
    var self = this;
    self.create = function(rows, cols) {
        var me = this;
        var x = new Array(rows * cols);
        return x;
    }
    self.rand = function(rows, cols) {
        var me = this;
        var x = me.create(rows, cols);
        for(var i = 0; i < x.length; i += 1) {
            x[i] = Math.random();
        }
        return x;
    }
    self.col_sum = function(x, rows, cols) {
        var y = new Array(cols).fill(0);
        for(var r = 0; r < rows; r += 1) {
            for(var c = 0; c < cols; c += 1) {
                y[c] += x[r * cols + c];
            }
        }
        return y;
    }
}

function Test(n2d) {
    var rows = 100;
    var cols = 10000;
    var x = n2d.rand(rows, cols);
    var y = n2d.col_sum(x, rows, cols);
    //console.log(y);
}

function BulkTest(n2d, n) {
    for(var i = 0; i < n; i += 1) {
        Test(n2d);
    }
}

function measStart() {
    return Date.now();
}

function measEnd(t) {
    var et = Date.now();
    return et - t;
}

function main() {
    var testN = 100;
    
    var t1 = measStart();
    BulkTest(new Number2D_A(), testN);
    console.log(measEnd(t1));
    
    var t2 = measStart();
    BulkTest(new Number2D_B(), testN);
    console.log(measEnd(t2));
}

if(!module.parent){
    main();
}

以上です

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1