Окончательный поиск глубокого копирования (90% людей не знают)

внешний интерфейс React.js опрос товар

Фокус, это обязательный вопрос на собеседовании, я задавал этот вопрос многим интервьюерам, ✧(≖ ◡ ≖✿) хе-хе

Во-первых, это очень хороший вопрос для собеседования. Он может исследовать многие аспекты интервьюируемого, такие как базовые навыки, умение кодировать, логические способности, а также может атаковать и защищаться. Он может исследовать разные уровни сложности для людей разного уровня. , такие как красивые девушки Вопрос 1☆, (*^__^*) Хи-хи...

Обычно после того, как интервьюер ответит на вопросы, я всегда могу по-умному подкинуть еще несколько вопросов, посмотреть на интервьюера изумленными глазами, молча повернуться и скрыть свои заслуги и славу.

В этой статье я решу для вас загадку глубокого копирования, от поверхностного к глубокому, взаимосвязанному, включающему в общей сложности 4 метода глубокого копирования, каждый из которых имеет свои особенности и индивидуальность.

Поверхностная копия, глубокая копия VS

Прежде чем мы начнем снова, нам нужно объяснить учащимся, что такое глубокая копия. Еще один термин, связанный с глубокой копией, — поверхностная копия. Что это значит? Если вы знакомы с этой частью контента, вы можете пропустить ее

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

// 基本类型
var a = 1;
var b = a;
a = 2;
console.log(a, b); // 2, 1 ，a b指向不同的数据

// 引用类型指向同一份数据
var a = {c: 1};
var b = a;
a.c = 2;
console.log(a.c, b.c); // 2, 2 全是2，a b指向同一份数据

Для ссылочных типов это приведет к тому, что ab будет указывать на одни и те же данные. Если один из них будет изменен в это время, это повлияет на другой. Иногда это может быть не тот результат, который нам нужен. Если это явление неясно, это может быть причиной ненужные ошибки

Итак, как разорвать связь между a и b? Вы можете скопировать копию данных a. В зависимости от уровня копии ее можно разделить на поверхностную копию и глубокую копию. Поверхностная копия означает только один слой копии , а глубокая копия означает копирование бесконечного уровня

var a1 = {b: {c: {}};

var a2 = shallowClone(a1); // 浅拷贝
a2.b.c === a1.b.c // true

var a3 = clone(a1); // 深拷贝
a3.b.c === a1.b.c // false

Реализация поверхностного копирования очень проста, и методов много. На самом деле это проблема обхода свойств объекта. Вот только один. Если вы не понимаете следующие методы или интересуетесь другими методами, вы может читать мойэта статья

function shallowClone(source) {
    var target = {};
    for(var i in source) {
        if (source.hasOwnProperty(i)) {
            target[i] = source[i];
        }
    }

    return target;
}

Простейшая глубокая копия

Проблема глубокого копирования на самом деле может быть разложена на две проблемы: поверхностное копирование + рекурсия, что это значит? Предположим, у нас есть следующие данные

var a1 = {b: {c: {d: 1}};

Просто немного измените код мелкой копии выше, обратите внимание на разницу

function clone(source) {
    var target = {};
    for(var i in source) {
        if (source.hasOwnProperty(i)) {
            if (typeof source[i] === 'object') {
                target[i] = clone(source[i]); // 注意这里
            } else {
                target[i] = source[i];
            }
        }
    }

    return target;
}

Большинство людей могут написать приведенный выше код, но когда я спрашиваю, что-нибудь не так с приведенным выше кодом? Очень немногие могут на него ответить, можно ли найти проблему, если вы умны?

На самом деле в приведенном выше коде слишком много проблем, давайте сначала приведем несколько примеров.

  • параметры не проверяются
  • Оценка того, является ли логика объекта недостаточно строгой
  • Нет совместимости массивов

(⊙o⊙), давайте посмотрим на решения каждой проблемы. Во-первых, нам нужно абстрагировать метод для оценки объектов. На самом деле, наиболее часто используемые методы для оценки объектов таковы. Фактически, следующие методы также есть проблемы, но если вы можете ответить на них, то это очень хорошо, если вы заинтересованы в идеальном решении, вы можете взглянутьвот

function isObject(x) {
    return Object.prototype.toString.call(x) === '[object Object]';
}

Функция должна проверять параметры, если это не объект, она возвращает напрямую

function clone(source) {
    if (!isObject(source)) return source;

    // xxx
}

По поводу третьего вопроса, гм, я оставлю его вам подумать самим.Чтобы уменьшить нагрузку на всех, в этой статье не будет рассматриваться ситуация с массивами.На самом деле после ES6 вам также нужно будет рассмотреть множество , карта, слабый набор, слабая карта, /(ㄒoㄒ)/~~

На самом деле, эти три небольшие проблемы.На самом деле, самая большая проблема с рекурсивными методами-это взрыв стека.Когда уровень данных очень глубокий, стек будет переполняться.

Следующий код может генерировать код, определяющий глубину и ширину каждого слоя, и мы снова будем использовать этот код позже.

function createData(deep, breadth) {
    var data = {};
    var temp = data;

    for (var i = 0; i < deep; i++) {
        temp = temp['data'] = {};
        for (var j = 0; j < breadth; j++) {
            temp[j] = j;
        }
    }

    return data;
}

createData(1, 3); // 1层深度，每层有3个数据 {data: {0: 0, 1: 1, 2: 2}}
createData(3, 0); // 3层深度，每层有0个数据 {data: {data: {data: {}}}}

Когда уровень клонирования очень глубокий, стек переполнится, но широта данных не вызовет переполнения.

clone(createData(1000)); // ok
clone(createData(10000)); // Maximum call stack size exceeded

clone(createData(10, 100000)); // ok 广度不会溢出

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

var a = {};
a.a = a;

clone(a) // Maximum call stack size exceeded 直接死循环了有没有，/(ㄒoㄒ)/~~

Есть два способа решить проблему циклической ссылки, один из них — постоянное циклическое обнаружение, а другой — взлом методом грубой силы.Вы можете подумать о циклическом обнаружении самостоятельно; мы подробно расскажем о взломе методом грубой силы в следующем содержании. .

Глубокая копия строки кода

Некоторые студенты могли видеть пример глубокого копирования с использованием JSON, поставляемого с системой.Давайте посмотрим на реализацию кода.

function cloneJSON(source) {
    return JSON.parse(JSON.stringify(source));
}

На самом деле, когда я впервые использовал этот метод, я искренне им восхищался, ведь это очень умный способ использовать инструменты для достижения цели.

Давайте проверим, есть ли у cloneJSON проблемы с переполнением.Похоже, cloneJSON также использует внутреннюю рекурсию.

cloneJSON(createData(10000)); // Maximum call stack size exceeded

Поскольку рекурсия используется, как насчет круговых ссылок? Там нет переполнения стека из-за бесконечной петли. Оказывается, json.Stringify делает круговое эталонное обнаружение внутренне, что является первым методом, который мы упомянули выше, чтобы взломать круговую ссылку: круглое обнаружение

var a = {};
a.a = a;

cloneJSON(a) // Uncaught TypeError: Converting circular structure to JSON

Взлом рекурсивного стека

На самом деле есть два способа взломать рекурсивный взрыв стека: первый способ — исключить хвостовую рекурсию, но в данном примере он, похоже, не работает, второй — просто не использовать рекурсию и использовать вместо нее циклы. Я предложил для ее достижения использовать циклы, в основном 90% фронтенда это неписаный код, что собственно меня шокировало

Например, предположим, что у вас есть следующая структура данных

var a = {
    a1: 1,
    a2: {
        b1: 1,
        b2: {
            c1: 1
        }
    }
}

Разве это не просто дерево? На самом деле, это очень очевидно, пока данные просматриваются через

    a
  /   \
 a1   a2        
 |    / \         
 1   b1 b2     
     |   |        
     1  c1
         |
         1

Для обхода дерева с циклом требуется помощь стека.Когда стек пуст, обход завершается, и в стеке сохраняется следующий узел для копирования.

Сначала мы помещаем начальные данные в стек,keyОбъект копирования дочернего элемента, используемый для хранения размещенного родительского элемента.

Затем пройдите по дочерним элементам под текущим узлом, если это объект, поместите его в стек, в противном случае скопируйте его напрямую.

function cloneLoop(x) {
    const root = {};

    // 栈
    const loopList = [
        {
            parent: root,
            key: undefined,
            data: x,
        }
    ];

    while(loopList.length) {
        // 深度优先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
        let res = parent;
        if (typeof key !== 'undefined') {
            res = parent[key] = {};
        }

        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // 下一次循环
                    loopList.push({
                        parent: res,
                        key: k,
                        data: data[k],
                    });
                } else {
                    res[k] = data[k];
                }
            }
        }
    }

    return root;
}

После переключения на цикл проблема взрыва стека больше не будет возникать, но по-прежнему не может справиться с циклической ссылкой.

ломать циклические ссылки

Есть ли способ взломать приложение зацикливания? Не волнуйтесь, давайте сначала рассмотрим другую проблему.Одна из проблем с тремя вышеуказанными методами заключается в том, что ссылка теряется, что может быть неприемлемо в некоторых случаях.

Например, если объект a, два значения ключа под a ссылаются на один и тот же объект b, после глубокого копирования два значения ключа a потеряют ссылочную связь и станут двумя разными объектами, o( ╯ □╰)о

var b = {};
var a = {a1: b, a2: b};

a.a1 === a.a2 // true

var c = clone(a);
c.a1 === c.a2 // false

Если мы найдем новый объект, мы сохраним объект и его копию.Перед копированием объекта проверьте, не был ли уже скопирован объект.Если он был скопирован, нет необходимости копировать его, просто используйте оригинал, поэтому мы можем сохранить эталонные отношения, ✧(≖ ◡ ≖✿) хе-хе

А вот как писать код, о(╯□╰)о, не спешите смотреть вниз, на самом деле он примерно такой же, как и код цикла, я использую разные места// ==========отмечен

импортировать массивuniqueListОн используется для хранения скопированного массива.Каждый раз при его обходе сначала оценивается, находится ли объект вuniqueListЕсли он есть, логика копирования не будет выполняться.

findЭто абстрактная функция, которая на самом деле является обходомuniqueList

// 保持引用关系
function cloneForce(x) {
    // =============
    const uniqueList = []; // 用来去重
    // =============

    let root = {};

    // 循环数组
    const loopList = [
        {
            parent: root,
            key: undefined,
            data: x,
        }
    ];

    while(loopList.length) {
        // 深度优先
        const node = loopList.pop();
        const parent = node.parent;
        const key = node.key;
        const data = node.data;

        // 初始化赋值目标，key为undefined则拷贝到父元素，否则拷贝到子元素
        let res = parent;
        if (typeof key !== 'undefined') {
            res = parent[key] = {};
        }
        
        // =============
        // 数据已经存在
        let uniqueData = find(uniqueList, data);
        if (uniqueData) {
            parent[key] = uniqueData.target;
            continue; // 中断本次循环
        }

        // 数据不存在
        // 保存源数据，在拷贝数据中对应的引用
        uniqueList.push({
            source: data,
            target: res,
        });
        // =============
    
        for(let k in data) {
            if (data.hasOwnProperty(k)) {
                if (typeof data[k] === 'object') {
                    // 下一次循环
                    loopList.push({
                        parent: res,
                        key: k,
                        data: data[k],
                    });
                } else {
                    res[k] = data[k];
                }
            }
        }
    }

    return root;
}

function find(arr, item) {
    for(let i = 0; i < arr.length; i++) {
        if (arr[i].source === item) {
            return arr[i];
        }
    }

    return null;
}

Давайте проверим эффект, потрясающе

var b = {};
var a = {a1: b, a2: b};

a.a1 === a.a2 // true

var c = cloneForce(a);
c.a1 === c.a2 // true

Теперь давайте поговорим о том, как сломать циклическую ссылку. Подождите, приведенный выше код, кажется, может сломать циклическую ссылку. Давайте проверим это сейчас.

Удивлен или нет, (*^__^*) Хи-хи...

var a = {};
a.a = a;

cloneForce(a)

выглядит идеальноcloneForceВсе в порядке?cloneForceЕсть две проблемы

Первый вопрос, так называемый успех — это тоже Сяо Хе, и неудача — это тоже Сяо Хе.Если вы не хотите продолжать цитировать, то вы не можете это использовать.cloneForce;

второй вопрос,cloneForceБудет большая проблема, когда количество объектов велико, и это не подходит для использования, если объем данных велик.cloneForce

Сравнение производительности

Вышеприведенный контент все еще немного сложен, давайте возьмем немного сложнее и сравним производительность разных методов.

Давайте сначала проведем эксперимент и посмотрим на данные. Есть две причины, влияющие на производительность. Одна — это глубина, а другая — ширина каждого слоя. Мы используем метод фиксации одной переменной и изменения только одной переменной для проверки представление.

Метод тестирования заключается в выполнении определенного количества глубоких копий в течение заданного времени.Чем больше раз, тем выше производительность.

последующийrunTimeэто основной фрагмент тестового кода, в следующем примере мы можем запустить тест за 2 секундыclone(createData(500, 1)количество раз

function runTime(fn, time) {
    var stime = Date.now();
    var count = 0;
    while(Date.now() - stime < time) {
        fn();
        count++;
    }

    return count;
}

runTime(function () { clone(createData(500, 1)) }, 2000);

Сделаем первый тест, зафиксируем ширину на 100, изменим глубину с маленькой на большую и запишем количество выполнений за 1 секунду

глубина clone cloneJSON cloneLoop cloneForce
500 351 212 338 372
1000 174 104 175 143
1500 116 67 112 82
2000 92 50 88 69

Приведя приведенные выше данные в таблицу, можно обнаружить, что некоторые правила

  • Чем меньше глубина, тем меньше разница между ними.
  • Разница между clone и cloneLoop невелика
  • cloneLoop > cloneForce > cloneJSON

Давайте сначала проанализируем временную сложность каждого метода.Каждый метод должен делать одно и то же, поэтому здесь он не будет рассчитываться, например, зацикливать объект, чтобы определить, является ли он объектом или нет.

  • время клонирования = создать рекурсивную функцию + время обработки объекта
  • время cloneJSON = обнаружение цикла + время обработки каждого объекта * 2 (рекурсивное преобразование строки + рекурсивный анализ)
  • cloneLoop time = время обработки объекта
  • cloneForce time = определить, находится ли объект в кеше + время обработки для каждого объекта

Скорость cloneJSON составляет всего 50% от clone, что легко понять, потому что он выполнит еще один раз рекурсии.

CloneForce должен определить, находится ли объект в кеше, что приводит к низкой скорости.Давайте посчитаем временную сложность логики суждения.Предполагая, что количество объектов равно n, временная сложность равна O(n2).Число объектов Чем больше, тем медленнее будет cloneForce

1 + 2 + 3 ... + n = n^2/2 - 1

Есть небольшая проблема с clone и cloneLoop. Кажется, что результаты эксперимента не согласуются с результатами вывода. Должно быть что-то не так.

Затем выполните второй тест, зафиксируйте глубину на 10000, ширину на 0 и запишите количество выполнений в течение 2 секунд.

ширина clone cloneJSON cloneLoop cloneForce
0 13400 3272 14292 989

Давайте посмотрим на влияние глубины на каждый метод без вмешательства ширины.

  • По мере увеличения количества объектов подчеркивается низкая производительность cloneForce.
  • Производительность cloneJSON также сильно снижается, это связано с тем, что обнаружение циклов занимает много времени.
  • Производительность cloneLoop выше, чем у clone.Видно, что время рекурсивной новой функции ничтожно мало по сравнению с объектом цикла.

Давайте проверим ограничение производительности cloneForce, на этот раз мы проверим время, необходимое для запуска заданного количества раз.

var data1 = createData(2000, 0);
var data2 = createData(4000, 0);
var data3 = createData(6000, 0);
var data4 = createData(8000, 0);
var data5 = createData(10000, 0);

cloneForce(data1)
cloneForce(data2)
cloneForce(data3)
cloneForce(data4)
cloneForce(data5)

Тестирование показало, что время увеличивается экспоненциально, когда количество объектов превышает 10 000, задержка составляет более 300 мс.

Суммировать

Линейка короткая, а дюйм длинный, независимо от того, хорошо это или плохо. На самом деле у каждого метода есть свои преимущества и недостатки, и применимые сценарии. Это правда, что люди наилучшим образом используют свои таланты и материалы. .

Ниже приводится сравнение различных методов, я надеюсь оказать вам некоторую помощь.

clone cloneJSON cloneLoop cloneForce
трудность ☆☆ ☆ ☆☆☆ ☆☆☆☆
совместимость ie6 ie8 ie6 ie6
циклическая ссылка слой не поддерживается слой служба поддержки
переполнение стека Могу Могу Не будет Не будет
продолжай цитировать нет нет нет да
подходит для сцены Копия общих данных Копия общих данных много уровней поддерживать ссылку

Эта статья вдохновлена@jsmini/cloneЕсли вы хотите использовать четыре метода глубоких копий в тексте, вы можете использовать @ jsmini / clone в этой библиотеке.

// npm install --save @jsmini/clone
import { clone, cloneJSON, cloneLoop, cloneForce } from '@jsmini/clone';

Для простоты и удобочитаемости в примере кода игнорируются некоторые пограничные случаи.Если вы хотите изучить код в действии, прочтите@jsmini/cloneисходный код

@jsmini/clone вылупился вjsmini, jsmini стремится предоставить вам набор небольших и красивых высококачественных библиотек без зависимостей.

Рождение jsmini неотделимоjslib-base, спасибо jslib-base за предоставление базовой технологии для jsmini

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

Наконец, я рекомендую мою новую книгу «React State Management and Isomorphic Practice», глубокую интерпретацию передовой изоморфной технологии, спасибо за вашу поддержку.

Цзиндон:item.JD.com/12403508.Контракт…

Данданг:product.dangdang.com/25308679.Контракт…

Наконец-то мы наконец-то набираем фронтенд, бэкенд и клиентскую часть! Расположение: Пекин + Шанхай + Чэнду, заинтересованные студенты могут отправить свои резюме на мой почтовый ящик:yanhaijing@yeah.net

Исходный URL:Yanhaijing.com/JavaScript/…

Категории