Unrolling javascript loops

Question

I have a cubic 3D array "class" like this:

function Array3D(size) {
    this.data = new Array(size*size*size);
    var makeIndex = function(p) {
        return p[0] + p[1]*size + p[2]*size*size;
    }
    this.get = function(p) { return this.data[makeIndex(p)]; };
    this.set = function(p, value) { this.data[makeIndex(p)] = value; };
}

I'd like to generalize to multiple dimensions, but without affecting access performance. Here's my simple approach:

function ArrayND(size, N) {
    var s = 1;
    for(var i = 0; i < N; i++) s *= size;
    this.data = new Array(s);

    var makeIndex = function(p) {
        var ind = 0;
        for(var i = N-1; i >= 0; i--)
            ind = ind*size + p[i];
        return ind;
    }
    this.get = function(p) { return this.data[makeIndex(p)]; };
    this.set = function(p, value) { this.data[makeIndex(p)] = value; };
}

Is there any way I can "unroll" my makeIndex function, so that the loop is evaluated once at declaration time, but not upon invokation? Would the overhead of using runtime-generated code from eval or new Function() cancel out the benefit of not looping?

Both size and N are essentially constants, so the repeated multiplication and iteration feels like something that could be done only once.

Answer 1

What's wrong with the traditional approach to multidimensional arrays?

function ArrayND(size, N, fill) {
    if (N < 1) throw new Error('Arrays must have at least one dimension.');
    if (size < 1) throw new Error('Arrays must have at least one element.');
    var arr = new Array(size);
    populate(arr, 1);

    function populate(a, depth) {
        for (var i = 0; i < size; i++) {
            if (depth < N) {
                a[i] = new Array(size);
                populate(a[i], depth+1);
            } else a[i]=fill;
        }
    }

    return arr;
}

This returns a multidimensional array (optionally filled with a default value) that's much more intuitive to access:

var arr = ArrayND(5, 3, 'hi');

console.log(arr[0][1][2]); // => 'hi'
arr[0][1][3] = 'mom';

---

Update: Since your goal is to access the multidimensional array by giving an argument of arbitrary length, I'd use this approach:

!function() {
    function ArrayND(size, N, fill) {
        if (N < 1) throw new Error('Arrays must have at least one dimension.');
        if (size < 1) throw new Error('Arrays must have at least one element.');
        if (!(this instanceof ArrayND)) return new ArrayND(size, N, fill); // allow this ctor to be called without `new` operator

        var arr = this;
        arr.length = size;
        populate(arr, 1);

        function populate(a, depth) {
            for (var i = 0; i < size; i++) {
                if (depth < N) {
                    a[i] = new Array(size);
                    populate(a[i], depth+1);
                } else a[i]=fill;
            }
        }

        return arr;
    }

    var proto = Object.create(Array.prototype); // polyfill necessary for older browsers, see https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/Object/create#Polyfill

    proto.get = function(indicies) {
        var pos = this;
        for (var i = 0; i < indicies.length; i++) {
            pos = pos[indicies[i]];
        }
        return pos;
    };
    proto.set = function(indicies, value) {
        var pos = this;
        for (var i = 0; i < indicies.length - 1; i++) {
            pos = pos[indicies[i]];
        }
        pos[indicies[indicies.length-1]] = value;
    }
    ArrayND.prototype = proto;

    this.ArrayND = ArrayND; // export to global scope
}();

This gives you the best of both worlds: a new ArrayND(s, d) still looks and behaves like a normal array, but also gives you get and set accessors that can take an arbitrary number of index arguments at runtime – all without modifying the builtin Array.

var arr = new ArrayND(5, 3, 'hi');

console.log(arr[0][1][2]); // => hi
console.log(arr.get([0,1,2]); // => hi

arr.push([]); // => 6 (the new length)
arr.set([6,0], 'I was added');

Answer 2

Consider this:

var makeIndex = (function () {
    var arr = _.range( N ).map(function ( i ) {
        return Math.pow( size, i );
    });

    function dotProduct ( a, b ) {
        var sum = 0;
        for ( var i = 0, l = a.length; i < l; i++ ) {
            sum += a[i] * b[i];
        }
        return sum;
    }

    return function ( p ) {
        return dotProduct( p, arr );
    };
}());

So you create the [0, size, size*size, size*size*size, ...] array beforehand, and then on each invocation, you perform a dot product on that array and the p array.

I use underscore's range function in my code.

Answer 3

Here's one method of doing this, that builds the function contents as a string using new Function:

var makeIndex = (function() {
    var code = []
    var scale = 1;
    for(var i = 0; i < N; i++) {
        code.push("p["+i+"]*"+scale);
        scale *= size;
    }
    return new Function('p', 'return '+code.join('+'));
})();