-
-
Save saitonakamura/d51aa672c929e35cc81fa5a0e31f12a9 to your computer and use it in GitHub Desktop.
| // DISCLAIMER | |
| // Original function was updated to a faster and es5-supporting version by @Quacky2200 | |
| var replaceCircular = function(val, cache) { | |
| cache = cache || new WeakSet(); | |
| if (val && typeof(val) == 'object') { | |
| if (cache.has(val)) return '[Circular]'; | |
| cache.add(val); | |
| var obj = (Array.isArray(val) ? [] : {}); | |
| for(var idx in val) { | |
| obj[idx] = replaceCircular(val[idx], cache); | |
| } | |
| cache.delete(val); | |
| return obj; | |
| } | |
| return val; | |
| }; | |
| // var a = { f: "asd", b: undefined } | |
| // var b = { h: 123, a: a } | |
| // a.b = b | |
| // console.log(JSON.stringify(replaceCircular(a))) | |
| // { "f": "asd", "b": { "h": 123, "a": "[Circular]" } } |
Thanks @logidelic, I fixed that!
@saitonakamura : Good stuff, thanks for this. However, don't you also want to do an already.delete(obj) before returning, after the array condition?
I decided to make this a little bit simpler since in an old NodeJS version, lambdas aren't supported, and in general, a small switch statement and map/forEach can be considered slow (more function invocations). I removed the level variable since there was no implementation of it other than passing it on the recurring loop and simplified the if statements. For example, your use of (!val) return (which is null if it's an object) can be simplified to if (val && typeof(val) === 'object') { /* do something*/ }. You also had some duplicated code with the forEach which I removed.
var stringify = function(obj) {
var replaceCircular = function(val, cache) {
cache = cache || new WeakSet();
if (val && typeof(val) === 'object') {
if (cache.has(val)) return '[Circular]';
cache.add(val);
var obj = (Array.isArray(val) ? [] : {});
for(var idx in val) {
obj[idx] = replaceCircular(val[idx], cache);
}
cache.delete(val);
return obj;
}
return val;
};
return JSON.stringify(replaceCircular(obj));
};Feel free to replace tabs to spaces, var to const, ofc.
I just used console.time to benchmark running your version @Quacky2200 as replaceCIrcularFast and his as replaceCircular 100k times each, and yours runs approximately twice as slow.
decyled
{
abc:"Hello",
circular:"CIRCULAR"
}
replaceCircular: 33ms
decyled fast
{
abc:"Hello",
circular: {
abc:"Hello",
circular:"CIRCULAR"
}
}
replaceCircularFast: 64ms
my test code:
const replaceCircular = (obj, level = 0, already = new WeakSet()) => {
switch (typeof obj) {
case 'object':
if (!obj)
return obj
if (already.has(obj)) {
return "CIRCULAR"
}
already.add(obj)
if (Array.isArray(obj)) {
return obj.map(item => replaceCircular(item, level + 1, already))
}
const newObj = {}
Object.keys(obj).forEach(key => {
const val = replaceCircular(obj[key], level + 1, already)
newObj[key] = val
})
already.delete(obj)
return newObj
default:
return obj;
}
}
var replaceCircularFast = function(val, cache) {
cache = cache || new WeakSet();
if (val && typeof(val) === 'object') {
if (cache.has(val)) return '[Circular]';
cache.add(val);
var obj = (Array.isArray(val) ? [] : {});
for(var idx in val) {
obj[idx] = replaceCircular(val[idx], cache);
}
cache.delete(val);
return obj;
}
return val;
};
function Foo() {
this.abc = "Hello";
this.circular = this;
}
var foo = new Foo();
console.log("decyled", replaceCircular(foo))
console.time("replaceCircular")
for (let i = 0; i < 100000; i++) {
replaceCircular(foo)
}
console.timeEnd("replaceCircular")
console.log("decyled fast", replaceCircularFast(foo))
console.time("replaceCircular")
console.time("replaceCircularFast")
for (let i = 0; i < 100000; i++) {
replaceCircularFast(foo)
}
console.timeEnd("replaceCircularFast")
My original stringify method is very slow with a JSON.stringify. I chose to go from a recursive to a iterative stack method which trades function overhead for storage to gain slight performance improvements. The new function doesn't bother creating any new objects, stack holds the parent value and child key to modify itself. As you can see in the replaceCircularFaster function I added (albeit the JSON.stringify).
var stringify = function(obj) {
var cache = new WeakSet();
var stack = [{obj: arguments, key: 0}];
while (stack.length > 0) {
var item = stack.pop();
var item_val = item.obj[item.key];
if (typeof(item_val) == 'object') {
if (cache.has(item_val)) {
item.obj[item.key] = '[Circular]';
continue;
}
cache.add(item_val);
for(var idx in item_val) {
stack.push({obj: item_val, key: idx});
}
}
}
return JSON.stringify(obj);
};Edit: See below comment
Sorry to spam the comment section...
@jt0dd I noticed you're calling the original function replaceCircular in the replaceCircularFast function. When I change this to replaceCircularFast, this changes the result to ~50ms.
I also decided to run more tests with slight differences before actually realising the mistake above... I thought it was quite interesting. The array lamdba functions used in the original can still take over 100ms worst case. The iteration function from my last comment is still somewhat quite low in my results, yet it's actually higher than my original recursive refactor comment!
The iteration function forgets to create a new instance which causes the original argument object to change (whoops, my bad 😞 ). My original comment seems to give the lowest result, type equality (===) differences give a teeny-tiny neglible speed boost.
Test Code
// Original post
// Can be harder to read, relies on Array function with lambdas, switch case
var replaceCircular1 = function(obj, level = 0, already = new WeakSet()) {
switch (typeof obj) {
case 'object':
if (!obj)
return obj
if (already.has(obj)) {
return "CIRCULAR"
}
already.add(obj)
if (Array.isArray(obj)) {
return obj.map(item => replaceCircular1(item, level + 1, already))
}
const newObj = {}
Object.keys(obj).forEach(key => {
const val = replaceCircular1(obj[key], level + 1, already)
newObj[key] = val
})
already.delete(obj)
return newObj
default:
return obj;
}
}
// Simplified, return early, avoids array obj functions, static cache object
var replaceCircular2 = function(obj) {
if (!(obj && typeof(obj) == 'object')) return obj;
var self = replaceCircular2;
self.cache = self.cache || new WeakSet();
if (self.cache.has(obj)) return '[Circular]';
self.cache.add(obj);
var _new = Array.isArray(obj) ? [] : {};
for (var idx in obj) {
_new[idx] = replaceCircular2(obj[idx]);
}
self.cache.delete(obj);
return _new;
};
// Same as before, but using 'self' variable w/ arguments.callee
// retrieving and calling arguments.callee is slow!
var replaceCircular3 = function(obj) {
if (!(obj && typeof(obj) == 'object')) return obj;
var self = arguments.callee;
self.cache = self.cache || new WeakSet();
if (self.cache.has(obj)) return '[Circular]';
self.cache.add(obj);
var _new = Array.isArray(obj) ? [] : {};
for (var idx in obj) {
_new[idx] = self(obj[idx]);
}
self.cache.delete(obj);
return _new;
};
// Simplified, Iteration w/ stack (Quacky2200 response 2)
// Alright min/med/max stats but changes the original object, stack is a bit rediculous
var replaceCircular4 = function(obj) {
var cache = new WeakSet();
var stack = [{obj: arguments, key: 0}];
while (stack.length > 0) {
var item = stack.pop();
var item_val = item.obj[item.key];
if (typeof(item_val) == 'object') {
if (cache.has(item_val)) {
item.obj[item.key] = '[Circular]';
continue;
}
cache.add(item_val);
for(var idx in item_val) {
stack.push({obj: item_val, key: idx});
}
}
}
return obj;
};
// Simplified, Recursive, Cache Argument (Quacky2200 original response)
// Easiest to understand, fastest to run
var replaceCircular5 = function(val, cache) {
cache = cache || new WeakSet();
if (val && typeof(val) === 'object') {
if (cache.has(val)) return '[Circular]';
cache.add(val);
var obj = (Array.isArray(val) ? [] : {});
for(var idx in val) {
obj[idx] = replaceCircular5(val[idx], cache);
}
cache.delete(val);
return obj;
}
return val;
};
// Similar to replaceCircular5, but removes type equality operation (===)
var replaceCircular6 = function(val, cache) {
cache = cache || new WeakSet();
if (val && typeof(val) == 'object') {
if (cache.has(val)) return '[Circular]';
cache.add(val);
var obj = (Array.isArray(val) ? [] : {});
for(var idx in val) {
obj[idx] = replaceCircular6(val[idx], cache);
}
cache.delete(val);
return obj;
}
return val;
};
function Foo() {
this.abc = "Hello";
this.circular = this;
}
var foo;
var stats = {
replaceCircular1: [],
replaceCircular2: [],
replaceCircular3: [],
replaceCircular4: [],
replaceCircular5: [],
replaceCircular6: []
};
for (var test = 0; test < 50; test++) {
//console.log(`Test ${test}/50`);
var now = Date.now();
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular1(foo)
}
stats.replaceCircular1.push(Date.now() - now)
now = Date.now()
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular2(foo)
}
stats.replaceCircular2.push(Date.now() - now)
now = Date.now()
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular3(foo)
}
stats.replaceCircular3.push(Date.now() - now)
now = Date.now()
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular4(foo)
}
stats.replaceCircular4.push(Date.now() - now)
now = Date.now()
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular5(foo)
}
stats.replaceCircular5.push(Date.now() - now)
now = Date.now()
for (let i = 0; i < 100000; i++) {
foo = new Foo();
replaceCircular6(foo)
}
stats.replaceCircular6.push(Date.now() - now)
}
for (var stat in stats) {
console.log(
stat + ": ",
"min: " + stats[stat].sort(function(a,b) {return a-b})[0],
"med: " + stats[stat].reduce(function(a,b) {return a + b}) / stats[stat].length,
"max: " + stats[stat].sort(function(a,b) {return b-a})[0]
);
}Browser:
replaceCircular1: min: 47 med: 67.22 max: 292
replaceCircular2: min: 43 med: 51.82 max: 141
replaceCircular3: min: 48 med: 54.26 max: 123
replaceCircular4: min: 46 med: 52.28 max: 103
replaceCircular5: min: 31 med: 36.44 max: 160
replaceCircular6: min: 33 med: 37.36 max: 85
replaceCircular1: min: 51 med: 70.82 max: 187
replaceCircular2: min: 43 med: 49.22 max: 103
replaceCircular3: min: 49 med: 54.58 max: 104
replaceCircular4: min: 45 med: 53.02 max: 150
replaceCircular5: min: 31 med: 38.38 max: 104
replaceCircular6: min: 30 med: 36.6 max: 91
Node:
$ node test.js
replaceCircular1: min: 42 med: 49.04 max: 115
replaceCircular2: min: 37 med: 40.88 max: 76
replaceCircular3: min: 45 med: 49.42 max: 71
replaceCircular4: min: 43 med: 48.16 max: 88
replaceCircular5: min: 30 med: 32.76 max: 50
replaceCircular6: min: 28 med: 32.08 max: 73
$ node test.js # intensive pc background tasks :(
replaceCircular1: min: 48 med: 65.08 max: 441
replaceCircular2: min: 38 med: 42.24 max: 111
replaceCircular3: min: 47 med: 52.44 max: 111
replaceCircular4: min: 43 med: 52.1 max: 201
replaceCircular5: min: 31 med: 35.7 max: 65
replaceCircular6: min: 29 med: 33.36 max: 58
$ node test.js
replaceCircular1: min: 43 med: 48.88 max: 117
replaceCircular2: min: 37 med: 39.36 max: 61
replaceCircular3: min: 45 med: 48.84 max: 67
replaceCircular4: min: 43 med: 46.48 max: 78
replaceCircular5: min: 30 med: 32.7 max: 48
replaceCircular6: min: 29 med: 31.16 max: 55
Wow, you people are great! @Quacky2200 I'll update the original to replaceCircular6 and mention you if you don't mind
Nifty, but FYI you have a bug: This will destroy arrays.