Использование итеративного стиля для клонирования объекта в JavaScript

Можно ли переписать следующую рекурсивную функцию JavaScript, чтобы сделать ее быстрее?

function clone_recursive(object) {
    var result = {};
    for (var key in object) {
        var value = object[key];
        if (typeof value === 'object') {
            result[key] = clone_recursive(value);
        } else {
            result[key] = value;
        }
    }
    return result;
}

Я переписал его в итеративном стиле, но он не получил никакой производительности, фактически скорость снизилась на ≈20%.

function clone_iterative(object) {
    var result = {};
    var queue = [{base: result, value: object}];
    var item;
    while (item = queue.shift()) {
        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queue.push({base: resultValue, value: value});
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

http://jsperf.com/clone-an-object/13

Ответы

Ответ 1

Несомненно, что итеративная версия будет действительно быстрее, поскольку вы заменяете рекурсивный вызов несколькими вызовами функций очередей. Там, где преобразование в итерацию помогает предотвратить переполнение стека (поскольку стеки вызовов имеют тенденцию быть меньше, чем кучи в интерпретируемых языках) и с хвостовой рекурсией на языках без оптимизации хвостового вызова.

Ответ 2

То, как вы сохраняете (используя свою очередь) в итеративной версии, вызывает замедление. Используйте массив-стек и введите запись для каждого элемента вместо объекта, который содержит оба элемента (основание и значение).

function clone_iterative(object) {
    var result = {};
    var stack = [result, object];
    var curr, base;
    while (curr = stack.pop()) {
        var base = stack.pop();
        for (var key in curr) {
            var value = curr[key];
            if (typeof value === 'object') {
                stack.push(base[key] = {});
                stack.push(value)
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Ознакомьтесь с набором функций функции clone на JS Fiddle. На некоторых запусках итеративная версия быстрее, чем рекурсивная, в других случаях выигрывает рекурсия.

Ответ 3

Я попытался использовать реализацию связанного списка очереди, чтобы узнать, что произойдет. Я думаю, что ваши проблемы могут быть служебными и функциональными вызовами функции() не обязательно являются O (1)

Jsperf сказал, что это был самый быстрый способ (я тестировал на FF7): http://jsperf.com/clone-an-object/4 но тогда я не уверен, что я не испортил бенчмарк, поскольку я не очень привык к веб-сайту jsperf.

Изменить: У меня была ошибка в моем коде. Это было фактически мелкое копирование

Ниже приведена фиксированная версия кода, который я использовал. Его быстрее, чем другая императивная версия, но все же проигрывает рекурсивному коду:

function clone_iterative_linked_list(object) {
    var result = {};
    var queueHead = {base: result, value: object, next: null};
    var queueTail = queueHead;

   for(;queueHead; queueHead = queueHead.next){
        var item = queueHead;

        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queueTail.next = {base: resultValue, value: value, next:null};
                queueTail = queueTail.next;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Ответ 4

Ну, это попыталось использовать JSON-заменитель, чтобы иметь только один обход JSON, но также не быстрее (см. http://jsperf.com/clone-an-object/6):

function clone(x) {
var r = {}, lastSrc, lastDst = r, stack = [], v;
function replacer(key, value) {
    while (this !== lastSrc && stack.length) {
        lastDst = stack.pop();
        lastSrc = stack.pop();
    }
    if (typeof value === "object") {
        stack.push(lastSrc, lastDst);
        lastDst[key] = v = new value.constructor;
        lastDst = v;
        lastSrc = value;
        return value;
    } else {
        lastDst[key] = value;
        return undefined;
    }
}
JSON.stringify(x, replacer);
return r[""];
}

Ответ 5

Итерационный. 2 массива, не используйте pop()

function clone_iterative2(object) {
    var result = {};
    var bases = [result];
    var objects = [object];
    for (var i = 0, length = 1; i < length; ++i) {
        var current = objects[i];
        var base = bases[i];
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                bases.push(base[key] = {});
                objects.push(value);
                ++length;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Это самый быстрый итерационный вариант. В Chrome Canary (17.0.959.0) это самый быстрый результат. Еще медленнее, чем рекурсивный во всех других браузерах.

http://jsperf.com/clone-an-object/13