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

7014 단어 알고리즘
수조 가 무 거 워 지 는 것 은 늘 하 는 문제 다.일반적인 처 리 는 간단 한 데이터 형식 만 포함 하 는 배열 을 조작 하 는 것 일 수 있 습 니 다. 오늘 우 리 는 복합 데이터 형식 에 대해 토론 을 합 니 다.
_.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) 이다.
비교적 효율 적 인 알고리즘 이 실현 되 었 는 지 모르겠다.

좋은 웹페이지 즐겨찾기