복잡 한 데이터 형식 을 포함 한 배열 의 무 거 운 문 제 를 이야기 하 다.

수조 가 무 거 워 지 는 것 은 늘 하 는 문제 다.일반적인 처 리 는 간단 한 데이터 형식 만 포함 하 는 배열 을 조작 하 는 것 일 수 있 습 니 다. 오늘 우 리 는 복합 데이터 형식 에 대해 토론 을 합 니 다.
_.isEqual
배열 의 무 게 를 실현 하려 면, 우 리 는 먼저 두 데이터 가 같은 지 비교 하 는 함수 가 있어 야 한다.Underscore. js 는 우리 에 게 좋 은 기능 함 수 를 제공 합 니 다. 이름 은:...isEqual()。복합 데이터 형식 에 대한 비교 에 있어 서 스 택 (후진 후 출) 과 유사 한 두 개의 배열 (push () 과 pop () 방법 만 호출 하여 스 택 을 실현 합 니 다) 을 도입 하고 재 귀적 인 방식 으로 끼 워 넣 어 판단 합 니 다.그 소스 코드 는 다음 과 같다.

// eq    isEqual     ,               
  //   ===     , eq       
  //                 ,               ,         (               )
  var eq = function(a, b, aStack, bStack) {
    //                 
    //         ,            ,       
    //            0,           -0,    0 === -0     
    //   1 / 0 == 1 / -0      (1 / 0  Infinity, 1 / -0  -Infinity,  Infinity   -Infinity)
    if (a === b) return a !== 0 || 1 / a == 1 / b;
    //                false,                (  null undefined            )
    if (a == null || b == null) return a === b;
    //             Underscore     (           _     )
    //               (  _wrapped  ),              
    //           jQuery   DOM  ,          DOM  
	
    //                         ，              Object.prototype.toString()              ，        false，        
    if (a instanceof _) a = a._wrapped;
    if (b instanceof _) b = b._wrapped;
	
    var className = toString.call(a);
	//             ，    false
    if (className != toString.call(b)) return false;
    switch (className) {
	  //    ，  ，            
      case '[object String]':
        //                toString()          ，  ：
		// Object.prototype.toString.call(new String('5'))-->"[object String]"
		// Object.prototype.toString.call('5')-->"[object String]"
        return a == String(b);
      case '[object Number]':
		//   +a a    Number,   a             ,    a   NaN  
        //   NaN NaN     ,    a  NaN ,        a == b    ,           b   NaN(  b != +b)
        //  a     NaN    ,    a   0,    b -0 , 0 === -0    (                  )
        return a != +a ? b != +b : (a == 0 ? 1 / a == 1 / b : a == +b);
		//          return break,            (         Boolean  ,        Boolean      )
      case '[object Date]':
      case '[object Boolean]':
        // Coerce dates and booleans to numeric primitive values. Dates are compared by their
        // millisecond representations. Note that invalid dates with millisecond representations
        // of `NaN` are not equivalent.
		//              
        //                 (            NaN,                 )
		//      , true    1, false    0
        //                       
        return +a == +b;
      // RegExps are compared by their source patterns and flags.
	  //        ,   source           
      //                  
      //                 (  g, i, m)
		//       ,          
      case '[object RegExp]':
        return a.source == b.source &&
               a.global == b.global &&
               a.multiline == b.multiline &&
               a.ignoreCase == b.ignoreCase;
		break;
		//             ，   Underscore          true:
		// _.isEqual({a:1},{a:1});// true
		//           false:
		// _.isEqual({a:function(){}},{a:function(){}}); // false
		//        （       ），         ，       true
		case '[object Function]':
			var repReg = /\r|
|\t|\v|\s*/g;
			return a.toString().replace(repReg,'') === b.toString().replace(repReg,'');
    }
	//       , ab                   
    if (typeof a != 'object' || typeof b != 'object') return false;
	//           。            ES  15.12.3     （          ），      'JO'
    var length = aStack.length;
    while (length--) {
	  //     。                   。
	  //                              。                         
      if (aStack[length] == a) return bStack[length] == b;
    }
	//                    ，  Object instanceof Object true，Function instanceof Function true，        
    var aCtor = a.constructor, bCtor = b.constructor;
    if (aCtor !== bCtor && !(_.isFunction(aCtor) && (aCtor instanceof aCtor) &&
                             _.isFunction(bCtor) && (bCtor instanceof bCtor))) {
      return false;
    }
    // Add the first object to the stack of traversed objects.
	//                  
    aStack.push(a);
    bStack.push(b);
    var size = 0, result = true;
    // Recursively compare objects and arrays.
	//                  
    if (className == '[object Array]') {
      // Compare array lengths to determine if a deep comparison is necessary.
	  // size       ，         false
      size = a.length;
      result = size == b.length;
      if (result) {
        // Deep compare the contents, ignoring non-numeric properties.
		//       ，        （           ）
        while (size--) {
          if (!(result = eq(a[size], b[size], aStack, bStack))) break;
        }
      }
    } else {
      // Deep compare objects.
	  //       
      for (var key in a) {
        if (_.has(a, key)) {
          // Count the expected number of properties.
		  //        
          size++;
          // Deep compare each member.
		  //            
          if (!(result = _.has(b, key) && eq(a[key], b[key], aStack, bStack))) break;
        }
      }
      // Ensure that both objects contain the same number of properties.
	  //                   true，    b    a          b  a      ，      true。             （         ）
      if (result) {
        for (key in b) {
          if (_.has(b, key) && !(size--)) break;
        }
        result = !size;
      }
    }
    // Remove the first object from the stack of traversed objects.
	//      “  ” push     ，             。
    aStack.pop();
    bStack.pop();
    return result;
  };

  // Perform a deep comparison to check if two objects are equal.
  _.isEqual = function(a, b) {
    return eq(a, b, [], []);
  };

특히 주의해 야 할 것 은 Underscore 대.isEqual({a:1},{a:1});의 결 과 는 true 이 고, 대.isEqual({a:function(){}},{a:function(){}});의 결과 가 false 라 는 점 은 나 로 하여 금 특히 이해 하지 못 하 게 한다.나 는 그 소스 코드 를 작은 변경 하여 후자 의 비교 도 true 로 만 들 었 다.
배열 제거
위 에서 두 개의 임 의 값 이 기다 리 고 싶 은 지 비교 하 는 함수 가 있 으 면 우 리 는 배열 의 무 거 운 조작 을 할 수 있다.
우 리 는 가장 간단 한 이중 순환 방식 으로 실현 합 니 다. 코드 는 다음 과 같 습 니 다.

function removeRepeat(ary){
		var len = ary.length;
		for(var i=0;i

최 악의 경우 알고리즘 의 시간 복잡 도 계산 공식 은 n * (n - 1) + (n - 1) * (n - 2) +... 2 * 1 이 고 결 과 는 O (n ^ 2) 이다.
또 하나의 실현 은 빈 배열 을 정의 한 다음 왼쪽 에서 오른쪽으로 무 거 운 배열 을 옮 겨 다 니 며 값 push 를 빈 배열 로 옮 겨 다 니 며 다음 값 으로 옮 겨 다 닐 때 이 값 이 배열 의 값 과 중복 되 는 지 여 부 를 판단 하고 중복 이 있 으 면 조작 하지 않 으 며 중복 이 없 으 면 push 를 배열 에 넣 는 것 입 니 다.이러한 시간 복잡 도 는 1 + 2 + 3 +... + (n - 1) 이 고 결 과 는 O (n * (n - 1) / 2) 이 며 O (n ^ 2) 이다.
비교적 효율 적 인 알고리즘 이 실현 되 었 는 지 모르겠다.