Развертывание циклов javascript

У меня есть кубический 3D-массив "класс", например:

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; };
}

Я хотел бы обобщить несколько измерений, но без ущерба для производительности доступа. Вот мой простой подход:

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; };
}

Есть ли способ «развернуть» мою функцию makeIndex, чтобы цикл оценивался один раз во время объявления, но не при вызове? Не сведут ли накладные расходы использование сгенерированного во время выполнения кода из eval или new Function() преимущество отсутствия циклов?

И size, и N по сути являются константами, поэтому повторяющееся умножение и итерация кажутся чем-то, что можно сделать только один раз.


person Eric    schedule 02.12.2012    source источник
comment
Разве это не должно быть ind += p[i] * Math.pow( size, i );, в результате чего получается p[0] + p[i] * size + p[1] * size * size + ...?   -  person Šime Vidas    schedule 02.12.2012
comment
Единственный расчет, который вы можете сделать при объявлении, — это создать массив [0, size, size*size, size*size*size, ...]. Умножение этого массива на массив p и добавление его в сумму должно выполняться при каждой операции получения/установки.   -  person Šime Vidas    schedule 02.12.2012
comment
@ŠimeVidas: Конечно, но поскольку size является константой, длина p является константой, поэтому в принципе цикл можно развернуть.   -  person Eric    schedule 02.12.2012
comment
Поправьте меня, если я ошибаюсь, но ваш цикл работает лучше, чем развернутое выражение для N значений, превышающих 3. Цикл выполняет N умножения и N сложения, тогда как развернутое выражение выполняет N-1 сложения, но N*(N-1)/2 умножения. Например, для N=10 цикл выполняет 10 умножений, тогда как развернутое выражение выполняет 45 умножений. Так что, я бы сказал, придерживайтесь цикла.   -  person Šime Vidas    schedule 03.12.2012
comment
@ŠimeVidas: Да, я думаю, вам придется предварительно вычислить константы в дополнение к развертыванию цикла.   -  person Eric    schedule 03.12.2012


Ответы (3)


Вот один из способов сделать это, который строит содержимое функции в виде строки, используя 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('+'));
})();
person Eric    schedule 02.12.2012
comment
Я думаю, что пока это не окончательный код, который вы в конечном итоге используете, его лучше опубликовать как редактирование вопроса, показывающего, что вы пробовали до сих пор. - person Shadow Wizard Wearing Mask V2; 02.12.2012
comment
@ShadowWizard: Не уверен, что согласен. Это определенно ответ, а не часть вопроса. Я все еще надеюсь на лучший ответ, но это не делает это не ответом. - person Eric; 02.12.2012

Учти это:

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 );
    };
}());

Таким образом, вы заранее создаете массив [0, size, size*size, size*size*size, ...], а затем при каждом вызове выполняете скалярное произведение этого массива и массива p.

В своем коде я использую функцию подчеркивания range.

person Šime Vidas    schedule 02.12.2012
comment
Это интересный подход, но я не уверен, что он что-то покупает. Для заданного значения N ваш makeIndex выполняет N умножений, N сложений и итерацию. Моя первоначальная версия делает то же самое, но без накладных расходов на список. - person Eric; 02.12.2012
comment
Кроме того, +1 за new Array(N).map(...) - я никогда раньше не сталкивался с этой идиомой. - person Eric; 02.12.2012
comment
Вероятно, это связано с тем, что new Array(N).map всегда возвращает массив, полный undefined в Chrome. - person Eric; 02.12.2012
comment
@ Эрик Да, new Array(N).map(...) не работает, я только что заметил. new Array(N) устанавливает только длину массива, но не создает никаких элементов, поэтому карта не запускается. Мне нужно идти сейчас, но я вернусь к этому позже. - person Šime Vidas; 02.12.2012
comment
@Eric Эрик Да, действительно, мой массив arr просто ненужный. Ваш первоначальный цикл, вероятно, является наиболее эффективным способом сделать это с помощью цикла. - person Šime Vidas; 03.12.2012

Что не так с традиционным подходом к многомерным массивам?

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;
}

Это возвращает многомерный массив (необязательно заполненный значением по умолчанию), доступ к которому гораздо более интуитивно понятен:

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

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

Обновление: поскольку ваша цель — получить доступ к многомерному массиву, указав аргумент произвольной длины, я бы использовал этот подход:

!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
}();

Это дает вам лучшее из обоих миров: new ArrayND(s, d) по-прежнему выглядит и ведет себя как обычный массив, но также дает вам методы доступа get и set, которые могут принимать произвольное количество аргументов индекса во время выполнения без изменения встроенного 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');
person josh3736    schedule 02.12.2012
comment
Я реализую его таким, какой я есть, потому что это означает, что моя программа может обобщаться на большее количество измерений. Я могу вызвать arr.get(l) со списком любого размера во время выполнения, но не могу arr[l[0]][l[1]]... - person Eric; 02.12.2012