Algorithmus zum

Question

Gleichheit von Kreisdatenstrukturen in JavaScript Bestimmung

var ones = [1]; 
ones[1] = ones; 
ones; 
// => [1, [1, [1, [1, [1, ...]]]]] 

var ones_ = [1]; 
ones_[1] = ones_; 
ones_; 
// => [1, [1, [1, [1, [1, ...]]]]] 

Wie bestimmt man, dass ones und ones_ gleich sind? Gibt es einen Algorithmus, der zirkuläre Strukturen wie die obigen behandelt?

Answer 1

Eine grundlegende Möglichkeit, dieses Problem zu lösen, ist zu beachten, dass während eines rekursiven Vergleich, wenn wir immer wieder am Ende wir vergleichen dasselbe Objektpaar, das wir bereits vergleichen, dann , wir können einfach annehmen, dass sie gleich sind. Das funktioniert, weil, wenn sie nicht gleich sind, dann der Vergleich, der bereits im Gange ist, schließlich einen Unterschied zwischen ihnen finden wird.

So können wir einfach mit einer grundlegenden rekursiven Vergleichsfunktion, starten und einen Stapel von Objekten hinzufügen zur Zeit verglichen werden:

function isEqual (a, b) { 
 
    var stack = []; 
 
    function _isEqual (a, b) { 
 
     // console.log("->", stack.length); 
 
     // handle some simple cases first 
 
     if (a === b) return true; 
 
     if (typeof(a) !== "object" || typeof(b) !== "object") return false; 
 
     // XXX: typeof(null) === "object", but Object.getPrototypeOf(null) throws! 
 
     if (a === null || b === null) return false; 
 
     var proto = Object.getPrototypeOf(a); 
 
     if (proto !== Object.getPrototypeOf(b)) return false; 
 
     // assume that non-identical objects of unrecognized type are not equal 
 
     // XXX: could add code here to properly compare e.g. Date objects 
 
     if (proto !== Object.prototype && proto !== Array.prototype) return false; 
 

 
     // check the stack before doing a recursive comparison 
 
     for (var i = 0; i < stack.length; i++) { 
 
      if (a === stack[i][0] && b === stack[i][1]) return true; 
 
      // if (b === stack[i][0] && a === stack[i][1]) return true; 
 
     } 
 

 
     // do the objects even have the same keys? 
 
     for (var prop in a) if (!(prop in b)) return false; 
 
     for (var prop in b) if (!(prop in a)) return false; 
 

 
     // nothing to do but recurse! 
 
     stack.push([a, b]); 
 
     for (var prop in a) { 
 
      if (!(_isEqual(a[prop], b[prop]))) { 
 
       stack.pop(); 
 
       return false; 
 
      } 
 
     } 
 
     stack.pop(); 
 
     return true; 
 
    } 
 
    return _isEqual(a, b); 
 
} 
 

 
// TEST CASES: 
 

 
var ones = [1]; ones[1] = ones; 
 
var foo = [1]; foo[1] = [1, foo]; 
 
var bar = [1]; bar[1] = [1, ones]; 
 
console.log("ones == foo:", isEqual(ones, foo)); 
 
console.log("ones == bar:", isEqual(ones, bar)); 
 
console.log("foo == bar:", isEqual(foo, bar)); 
 

 
var obj = {}; obj["x"] = obj; obj["y"] = {obj}; 
 
console.log("obj == obj[x]:", isEqual(obj, obj["x"])); 
 
console.log("obj != obj[y]:", !isEqual(obj, obj["y"])); 
 

 
var seven = []; seven[0] = [[[[[[seven]]]]]]; 
 
var eleven = []; eleven[0] = [[[[[[[[[[eleven]]]]]]]]]]; 
 
console.log("seven == eleven:", isEqual(seven, eleven)); 
 
console.log("[seven] == [eleven]:", isEqual([seven], [eleven])); 
 
console.log("[seven] == seven:", isEqual([seven], seven)); 
 
console.log("[seven] == [[[eleven]]]:", isEqual([seven], [[[eleven]]]));

Beachten Sie, dass ein großer Teil der Komplexität im Code Dies liegt daran, dass es versucht, eine Mischung aus verschiedenen Arten von JavaScript-Werten zu akzeptieren und (mehr oder weniger) elegant zu handhaben, einschließlich Primitiven, Nullwerten, Arrays, einfachen Objekten und all den anderen Dingen, die eine JS-Variable enthalten kann. Wenn Sie wissen, dass Ihre Eingaben nur eine begrenzte Anzahl von Datentypen enthalten können, ist es möglich, diesen Code erheblich zu vereinfachen.

Ps. Aufgrund des Stapelvergleichs kann die Laufzeit dieses Codes bis zu O (nd) sein, wobei n die Anzahl der Knoten in den Bäumen ist, die verglichen werden müssen (was mehr als erwartet sein kann; z. B. der Vergleich der Objekte seven und eleven im obigen Ausschnitt dauert 77 rekursive Aufrufe) und d ist die Tiefe des Stapels (die in diesem Fall auch bis zu 77). In ES2015 könnte eine potentiell nützliche Optimierung darin bestehen, ein Map von zuvor gesehenen Objekten zu verwenden, um den Stack-Lookup von O (d) auf effektiv O (1) zu reduzieren. Wenn wir erwarten, dass die zu vergleichenden Datenstrukturen im Allgemeinen viele sich wiederholende Verzweigungen aufweisen, die Verweise auf dieselben Objekte enthalten, könnte es sogar nützlich sein, diese in einen allgemeinen Cache von zuvor gesehenen Objekten zu expandieren, die wir bereits als gleichwertig erkannt haben.

Answer 2

Sie können ein Objekt durch Iterieren und Ersetzen bereits gesehener Objekte mit "Zeigern" (= Indizes in einem Array) "dezysten". Sobald Sie decycled structs bekommen, serialisiert sie einfach und vergleichen Sie als Strings:

let encode = function (x) { 
 

 
    function _enc(x, lst) { 
 
     if (typeof x !== 'object') 
 
      return x; 
 

 
     let i = lst.indexOf(x); 
 
     if (i >= 0) 
 
      return {'->': i}; 
 
     lst.push(x); 
 

 
     let y = {}; 
 
     for (let k of Object.keys(x)) 
 
      y[k] = _enc(x[k], lst) 
 

 
     return y; 
 
    } 
 

 
    return JSON.stringify(_enc(x, [])); 
 
}; 
 

 
////// 
 

 
let ones = [1]; 
 
ones[1] = ones; 
 

 
let ones_ = [1]; 
 
ones_[1] = ones_; 
 

 
console.log(encode(ones) === encode(ones_)) 
 

 
// more interesting example 
 

 
a = { 
 
    b: { 
 
     c: 123 
 
    } 
 
}; 
 

 
a.b.d = a; 
 
a.x = [9, a.b]; 
 

 

 
a2 = { 
 
    b: { 
 
     c: 123 
 
    } 
 
}; 
 

 
a2.b.d = a2; 
 
a2.x = [9, a2.b]; 
 

 
console.log(encode(a) === encode(a2))