Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

第 6 题:请分别用深度优先思想和广度优先思想实现一个拷贝函数? #10

Open
atheist1 opened this issue Feb 12, 2019 · 33 comments
Labels

Comments

@atheist1
Copy link

@atheist1 atheist1 commented Feb 12, 2019

话不多说直接放代码
发现了比较多的错误,但由于最近工作有点忙,一直没来得及纠正

更改(0226)

// 工具函数
let _toString = Object.prototype.toString
let map = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number'
}
let getType = (item) => {
  return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
  return map[type] && map[type] === getType(item)
}

深复制 深度优先遍历

let DFSdeepClone = (obj, visitedArr = []) => {
  let _obj = {}
  if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')) {
    let index = visitedArr.indexOf(obj)
    _obj = isTypeOf(obj, 'array') ? [] : {}
    if (~index) { // 判断环状数据
      _obj = visitedArr[index]
    } else {
      visitedArr.push(obj)
      for (let item in obj) {
        _obj[item] = DFSdeepClone(obj[item], visitedArr)
      }
    }
  } else if (isTypeOf(obj, 'function')) {
    _obj = eval('(' + obj.toString() + ')');
  } else {
    _obj = obj
  }
  return _obj
}

广度优先遍历

let BFSdeepClone = (obj) => {
    let origin = [obj],
      copyObj = {},
      copy = [copyObj]
      // 去除环状数据
    let visitedQueue = [],
      visitedCopyQueue = []
    while (origin.length > 0) {
      let items = origin.shift(),
        _obj = copy.shift()
      visitedQueue.push(items)
      if (isTypeOf(items, 'object') || isTypeOf(items, 'array')) {
        for (let item in items) {
          let val = items[item]
          if (isTypeOf(val, 'object')) {
            let index = visitedQueue.indexOf(val)
            if (!~index) {
              _obj[item] = {}
                //下次while循环使用给空对象提供数据
              origin.push(val)
                // 推入引用对象
              copy.push(_obj[item])
            } else {
              _obj[item] = visitedCopyQueue[index]
              visitedQueue.push(_obj)
            }
          } else if (isTypeOf(val, 'array')) {
            // 数组类型在这里创建了一个空数组
            _obj[item] = []
            origin.push(val)
            copy.push(_obj[item])
          } else if (isTypeOf(val, 'function')) {
            _obj[item] = eval('(' + val.toString() + ')');
          } else {
            _obj[item] = val
          }
        }
        // 将已经处理过的对象数据推入数组 给环状数据使用
        visitedCopyQueue.push(_obj)
      } else if (isTypeOf(items, 'function')) {
        copyObj = eval('(' + items.toString() + ')');
      } else {
        copyObj = obj
      }
    }
  return copyObj
}

测试

/**测试数据 */
// 输入 字符串String
// 预期输出String
let str = 'String'
var strCopy = DFSdeepClone(str)
var strCopy1 = BFSdeepClone(str)
console.log(strCopy, strCopy1) // String String 测试通过
// 输入 数字 -1980
// 预期输出数字 -1980
let num = -1980
var numCopy = DFSdeepClone(num)
var numCopy1 = BFSdeepClone(num)
console.log(numCopy, numCopy1) // -1980 -1980 测试通过
// 输入bool类型
// 预期输出bool类型
let bool = false
var boolCopy = DFSdeepClone(bool)
var boolCopy1 = BFSdeepClone(bool)
console.log(boolCopy, boolCopy1) //false false 测试通过
// 输入 null
// 预期输出 null
let nul = null
var nulCopy = DFSdeepClone(nul)
var nulCopy1 = BFSdeepClone(nul)
console.log(nulCopy, nulCopy1) //null null 测试通过

// 输入undefined
// 预期输出undefined
let und = undefined
var undCopy = DFSdeepClone(und)
var undCopy1 = BFSdeepClone(und)
console.log(undCopy, undCopy1) //undefined undefined 测试通过
  //输入引用类型obj
let obj = {
  a: 1,
  b: () => console.log(1),
  c: {
    d: 3,
    e: 4
  },
  f: [1, 2],
  und: undefined,
  nul: null
}
var objCopy = DFSdeepClone(obj)
var objCopy1 = BFSdeepClone(obj)
console.log(objCopy === objCopy1) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy.c) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy1.c) // 对象类型判断 false 测试通过
console.log(obj.b === objCopy1.b) // 函数类型判断 false 测试通过
console.log(obj.b === objCopy.b) // 函数类型判断 false 测试通过
console.log(obj.f === objCopy.f) // 数组类型判断 false 测试通过
console.log(obj.f === objCopy1.f) // 数组类型判断 false 测试通过
console.log(obj.nul, obj.und) // 输出null,undefined 测试通过

// 输入环状数据
// 预期不爆栈且深度复制
let circleObj = {
  foo: {
    name: function() {
      console.log(1)
    },
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null //待会让它指向obj.foo
      }
    }
  }
}
circleObj.foo.bar.baz.aChild = circleObj.foo
var circleObjCopy = DFSdeepClone(circleObj)
var circleObjCopy1 = BFSdeepClone(circleObj)
console.log(circleObjCopy, circleObjCopy1) // 测试通过?

ps


关于深浅拷贝的问题博主已经在他的git上有文章说过了,我就不做多的叙述
这两个方法我认为主要区别在于对于深层次以及环状数据,用深度优先遍历递归去做容易爆栈,广度优先遍历我对环状数据进行了处理,已经存在过的对象会存在数组中,下次直接赋值即可,无需继续遍历
如果出现问题欢迎讨论指出

@H246802

This comment has been minimized.

Copy link

@H246802 H246802 commented Feb 18, 2019

@atheist1 老哥你代码最好添加代码高亮一下,这样阅读感很差。

@xiaobaichiliangpi

This comment has been minimized.

Copy link

@xiaobaichiliangpi xiaobaichiliangpi commented Feb 19, 2019

笔误:
map = {
number: 'Number'
}

@zhengjianghao

This comment has been minimized.

Copy link

@zhengjianghao zhengjianghao commented Feb 21, 2019

DFSdeepClone 方法有问题吧 字符串 clone 出来不久变数组了
浏览器console 实验一下就错了

@Tairraos

This comment has been minimized.

Copy link

@Tairraos Tairraos commented Feb 22, 2019

数值赋值本身就是复制,clone的时候需要复制的是array, object和function,这个代码里并没有针对function成员的复制。

@oychao

This comment has been minimized.

Copy link

@oychao oychao commented Feb 25, 2019

DFS没有对环状结构进行处理~

@atheist1

This comment has been minimized.

Copy link
Author

@atheist1 atheist1 commented Feb 26, 2019

顺便说明下,这里我对es6的symbol数据以及构造函数的拷贝都没做处理,想要了解的可以看大佬的
这篇文章【进阶4-4期】Lodash是如何实现深拷贝的

@LeeLejia

This comment has been minimized.

Copy link

@LeeLejia LeeLejia commented Feb 26, 2019

DFSdeepClone = (obj, visitedArr = []) ,这里visitedArr如果传参的话,子层的属性不能和同层的属性做比较。只有同层的环能检测出来。
let b = {haha: 'haha'} let a = { a: {b: b}, c: {b: b} } const rs = DFSdeepClone(a) console.log(rs.a.b === rs.c.b) // false console.log(a.a.b === a.c.b) // true

@WozHuang

This comment has been minimized.

Copy link

@WozHuang WozHuang commented Mar 2, 2019

我只深拷贝了 Object, Array,其他的非基本类型都是浅拷贝(如果处理Set什么的就太复杂了,题目用意应该是考察遍历树和重复引用吧)

DFS用常规的递归问题不大,需要注意下重复引用的问题,不用递归的话就用栈

BFS就用队列,整体代码倒是差不多

// 如果是对象/数组,返回一个空的对象/数组,
// 都不是的话直接返回原对象
// 判断返回的对象和原有对象是否相同就可以知道是否需要继续深拷贝
// 处理其他的数据类型的话就在这里加判断
function getEmpty(o){
	if(Object.prototype.toString.call(o) === '[object Object]'){
		return {};
	}
	if(Object.prototype.toString.call(o) === '[object Array]'){
		return [];
	}
	return o;
}

function deepCopyBFS(origin){
	let queue = [];
	let map = new Map(); // 记录出现过的对象,用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		queue.push([origin, target]);
		map.set(origin, target);
	}

	while(queue.length){
		let [ori, tar] = queue.shift();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				queue.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

function deepCopyDFS(origin){
	let stack = [];
	let map = new Map(); // 记录出现过的对象,用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		stack.push([origin, target]);
		map.set(origin, target);
	}

	while(stack.length){
		let [ori, tar] = stack.pop();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				stack.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

// test
[deepCopyBFS, deepCopyDFS].forEach(deepCopy=>{
	console.log(deepCopy({a:1}));
	console.log(deepCopy([1,2,{a:[3,4]}]))
	console.log(deepCopy(function(){return 1;}))
	console.log(deepCopy({
		x:function(){
			return "x";
		},
		val:3,
		arr: [
			1,
			{test:1}
		]
	}))

	let circle = {};
	circle.child = circle;
	console.log(deepCopy(circle));
})
@binsinger

This comment has been minimized.

Copy link

@binsinger binsinger commented Mar 6, 2019

var o = {m: 2}
var obj = {
a: {b:o},
e: o
}
广度优先测试失败

@atheist1

This comment has been minimized.

Copy link
Author

@atheist1 atheist1 commented Mar 6, 2019

var o = {m: 2}
var obj = {
a: {b:o},
e: o
}
广度优先测试失败

公司gayhub怎么老是炸,感谢提醒,已更新,在处理环状数据时我将visitedCopyQueue错用成visitedQueue了,导致上一次使用的数据是存在visitedQueue里的引用导致深复制失败

@zhw2590582

This comment has been minimized.

Copy link

@zhw2590582 zhw2590582 commented Mar 29, 2019

笔试时会不会纸上手写深度拷贝

@Emensionyu

This comment has been minimized.

Copy link

@Emensionyu Emensionyu commented Apr 7, 2019

代码有点难读

@yanzhang146

This comment has been minimized.

Copy link

@yanzhang146 yanzhang146 commented Apr 11, 2019

    function deepClone(obj){
        var temp = {};
        for(var key in obj){
            if(obj.hasOwnProperty(key)){
                temp[key] = typeof obj[key] === "object" ? deepClone(obj[key]) : obj[key];
            }
        }
        return temp;
    }
@yygmind yygmind changed the title 第六题 实现深度拷贝 第 6 题:请分别用深度优先思想和广度优先思想实现一个拷贝函数? Apr 26, 2019
@ibwei

This comment has been minimized.

Copy link

@ibwei ibwei commented Jul 9, 2019

这应该是深度优先拷贝吧

let cloneObject = function(source) {
    let target = {};
    for (key in source) {
        if (source.hasOwnProperty(key)) {
            let itemType = Object.prototype.toString.call(source[key]).slice(8, -1);
            switch (itemType) {
                case "Object":
                    target[key] = cloneObject(source[key]);
                    break;
                case "Array":
                    let temp = [];
                    for (let i = 0; i < source[key].length; i++) {
                        temp.push(source[key][i]);
                    }
                    target[key] = temp;
                    break;
                default:
                    target[key] = source[key];

            }
        }
    }
    return target;
}
@smlPig

This comment has been minimized.

Copy link

@smlPig smlPig commented Jul 11, 2019

/**
 * @Author nzq
 * @Date 2019/5/28
 * @Description:
 * @Param:
 * @Return:
 */

const type = Object.prototype.toString;

function getType(obj) {
  const map = {
    '[object Boolean]'         : 'boolean',
    '[object Number]'          : 'number',
    '[object String]'          : 'string',
    '[object Null]'            : 'null',
    '[object Undefined]'       : 'undefined',
    '[object Symbol]'          : 'symbol',
    '[object Object]'          : 'object',
    '[object Array]'           : 'array',
    '[object Function]'        : 'function',
    '[object Date]'            : 'date',
    '[object RegExp]'          : 'regExp',
    '[object HTMLDivElement]'  : 'dom',
  };

  return map[type.call(obj)];
}

/**
 * @Author nzq
 * @Date 2019/5/28
 * @Description: 递归
 *        注意 visitedQueue.push(target); createQueue.push(res); 的时机
 * @Param:
 * @Return:
 */
function deepClone(obj) {
  // visitedQueue 和 createQueue 的值一定要相互对应
  let visitedQueue = [],
    createQueue = [],
    visitedIdx = 0;

  return (function _clone (target) {
    let res = null,
    type = getType(target);

    visitedIdx = visitedQueue.indexOf(target);

    // 访问过
    if ( visitedIdx !== -1) {
      res = createQueue[visitedIdx]; // 获取对应的 createQueue 中的值
    }
    // 没访问过
    else {
      switch(type) {
        case 'object': {
          res = {};
          visitedQueue.push(target);
          createQueue.push(res);

          // 遍历
          for (let key in target) {
           res[key] = _clone(target[key]);
          }
          break;
        }
        case 'array': {
          res = [];
          visitedQueue.push(target);
          createQueue.push(res);

          // 遍历
          for (let idx in target) {
            res[idx] = _clone(target[key]);
          }
          break;
        }
        case 'dom': {
          res = target.cloneNode(true);
          break;
        }
        default : {
          res = target;
        }
      }
    }
    return res;
  })(obj)
}
@SLSJL

This comment has been minimized.

Copy link

@SLSJL SLSJL commented Jul 14, 2019

请问能不能解释一下环状结构数据呢?

@NuoHui

This comment has been minimized.

Copy link

@NuoHui NuoHui commented Jul 16, 2019

请问能不能解释一下环状结构数据呢?

解决深拷贝中的环问题

@qinchenguang

This comment has been minimized.

Copy link

@qinchenguang qinchenguang commented Jul 22, 2019

@atheist1
您好。我刚刚查看您的广度优先遍历 BFSdeepClone 函数。while递归中没有判断array的环状数据。

您可以将下面这段代码 添加到函数执行之前,来复现该问题

let a = [1,2,3,4]
let b = a
a.push(b)
obj.a = a;

@zjinh

This comment has been minimized.

Copy link

@zjinh zjinh commented Jul 22, 2019

@qinchenguang

This comment has been minimized.

Copy link

@qinchenguang qinchenguang commented Jul 22, 2019

@atheist1
因为刚刚发现的问题。我又一次尝试了下。深度优先遍历 DFSdeepClone 函数中 visitedArr 数组存放的都是原数组的引用类型。这会导致环状数据出现问题。

如下代码
let a = [1,2,3,4]
let b = a
a.push(b)
obj.a = a;
var objCopy = DFSdeepClone(obj)
obj.a[2] = 2;
objCopy 克隆对象中的a数组 第二次引用会和源数据保持一致

@CatWithWings

This comment has been minimized.

Copy link

@CatWithWings CatWithWings commented Jul 23, 2019

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝,实现了下,暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }
@zzNire

This comment has been minimized.

Copy link

@zzNire zzNire commented Aug 1, 2019

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝,实现了下,暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }

这好像还是深度遍历

@CatWithWings

This comment has been minimized.

Copy link

@CatWithWings CatWithWings commented Aug 2, 2019

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝,实现了下,暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }

这好像还是深度遍历

const test = {a: {b: {v: 1}}, c: {f: 2}, h: new Date()};
你可以再for循环内部打印key,看看路径

@jiang2016tao

This comment has been minimized.

Copy link

@jiang2016tao jiang2016tao commented Aug 12, 2019

if (~index) 中的~是啥意思

@WB9292

This comment has been minimized.

Copy link

@WB9292 WB9292 commented Aug 14, 2019

深度优先搜索的拷贝函数,没有考虑一些复杂的对象。

function deepTraversal(target) {
    // 使用WeakSet防止循环引用
    let weakSet = new WeakSet();

    function realDeepTraversal(target) {
      if (target !== null && target !== undefined) {
        if (typeof target === 'object' && !weakSet.has(target)) {
          weakSet.add(target);

          if (Array.isArray(target)) {
            return target.map(realDeepTraversal);
          } else {
            return Object.keys(target).reduce((result, key) => ({
              ...result,
              [key]: realDeepTraversal(target[key])
            }), {});
          }
        } else {
          return target;
        }
      }
    }

    return realDeepTraversal(target);
  }
@yft

This comment has been minimized.

Copy link

@yft yft commented Aug 14, 2019

@atheist1 广度优先拷贝存在一个问题:

最外层是数组时,会变成对象

@Eliccc

This comment has been minimized.

Copy link

@Eliccc Eliccc commented Aug 29, 2019

容我抖个机灵,深度优先json.parse(json.stringify(obj))

@zjinh

This comment has been minimized.

Copy link

@zjinh zjinh commented Aug 29, 2019

容我抖个机灵,深度优先json.parse(json.stringify(obj))

我自己用的这个

@chenlei15

This comment has been minimized.

Copy link

@chenlei15 chenlei15 commented Sep 9, 2019

      visitedArr.push(obj)

@atheist1

这边不应该是放入的原始值吧,应该是放入深拷贝之后的值_obj

circleObjCopy.foo.bar.baz.aChild === circleObjCopy.foo //false

测试用例最后一个,拷贝后的结果的循环引用不正确。

@Bellhey

This comment has been minimized.

Copy link

@Bellhey Bellhey commented Oct 8, 2019

@atheist1
DFSdeepClone中通过if(~index)判断引用类型是否clone过不妥,直接判断index > -1不更好吗

@panzhengtao

This comment has been minimized.

Copy link

@panzhengtao panzhengtao commented Oct 9, 2019

谁能解释一下“环状数据”是什么意思? 我理解为 循环引用

@panzhengtao

This comment has been minimized.

Copy link

@panzhengtao panzhengtao commented Oct 9, 2019

容我抖个机灵,深度优先json.parse(json.stringify(obj))

这种不能满足所有场景,碰到函数,正则表达式,Symbol...就歇菜了

@yygmind yygmind added the 编程题 label Dec 16, 2019
@iceycc

This comment has been minimized.

Copy link

@iceycc iceycc commented Dec 30, 2019

// 判断正则、日期函数等
if(value instanceof RegExp){return new RegExp(value)}
if(value instanceof Date){return new Date(value)}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.