नोडज में, इस मामले में रिकर्सिव और गैर-रिकर्सिव ऑब्जेक्ट ट्रैवर्सल लगभग समान क्यों हैं - जावास्क्रिप्ट, नोड.जेएस, प्रदर्शन, रिकर्सन, v8

तुलना के लिए मेरा कोड निम्नलिखित है।मैं अपनी परियोजना के लिए कुछ अनुकूलन कर रहा हूं और पाया कि गैर-पुनरावर्ती समाधान को रिकर्सिव एक पर कोई फायदा नहीं है, जो कि मेरे अंतर्ज्ञान के खिलाफ है: प्रदर्शन लगभग रैखिक रूप से समान है।

मैं सोच रहा हूं कि क्या यह मामला विशिष्ट है या वी 8 इंजन के बारे में कुछ विवरण हैं जो मुझे नहीं पता।

संपादित:

मैंने लूप के बाहर यादृच्छिक वस्तु की पीढ़ी डाली है, वे अभी भी लगभग रैखिक रूप से वही हैं।

"use restrict";

if (!Array.prototype.fill) {
Array.prototype.fill = function(content) {
for (var i = 0; i < this.length; i++) {
this[i] = content;
}
};
}

var getClassName = (function () {

var NULL_OBJECT = {};

return function(obj) {
return NULL_OBJECT.toString.apply(obj).slice(8, -1);
}
})();

var Stack = function(opts) {
opts = opts || {};
var capacity = opts.capacity;
if (!capacity) {
capacity = 64;
}
this.capacity = capacity;
this.list = new Array(this.capacity);
this.cursor = 0;
};

Stack.prototype.__doubleTheSize = function() {
this.list = this.list.concat(new Array(this.capacity));
this.capacity = this.capacity * 2;
};

Stack.prototype.push = function(obj) {
if (this.cursor == this.capacity - 1) {
this.__doubleTheSize();
}
this.list[this.cursor] = obj;
this.cursor += 1;
};

Stack.prototype.clear = function() {
this.cursor = 0;
this.list.fill(undefined);
};

Stack.prototype.pop = function() {
if (this.cursor == 0) {
throw new Error("Stack is empty, pop is illegal.");
}
var val = this.list[this.cursor - 1];
this.list[this.cursor - 1] = undefined;
this.cursor -= 1;
return val;
};

function traverseRecursivly(obj, funcVisit) {

var className = getClassName(obj);
funcVisit(obj);
if (className != "Object" && className != "Array") {
return;
}
for (var i in obj) {
traverseRecursivly(obj[i], funcVisit);
}
}

var traverseNonRecursivly = (function() {

var stack = new Stack({
capacity: 1024
});

return function(obj, funcVisit) {

var __obj = obj;
stack.push(__obj);
while (stack.cursor > 0) {
__obj = stack.pop();
var className = getClassName(__obj);
funcVisit(__obj);
if (className != "Object" && className != "Array") {
continue;
}
for (var i in __obj) {
stack.push(__obj[i]);
}
}
};
})();

var genRandomTreeObject = (function() {

var stack = new Stack();

return function(size) {

var head = {
value: 0
};
stack.push(head);

for (var i = 1; i <= size; i++) {
var node = {
value: i
};

var parent = stack.list[Math.floor(Math.random() * stack.cursor)];
parent[i] = node;
stack.push(node);
}

stack.clear();
return head;
}

})();

var randomObject = genRandomTreeObject(1024);

console.time("recursive");
for (var i = 0; i < 1000; i++) {
var sum = 0;
traverseNonRecursivly(randomObject, function(o) {
if (o.value) {
sum += o.value;
}
})
}
console.log(sum);
console.timeEnd("recursive");

console.time("non-recursive");
for (var i = 0; i < 1000; i++) {
var sum = 0;
traverseRecursivly(randomObject, function(o) {
if (o.value) {
sum += o.value;
}
})
}
console.log(sum);
console.timeEnd("non-recursive");

उत्तर:

जवाब के लिए 0 № 1

यह सही है (प्रश्न पर टिप्पणियां देखें)। मैंने प्रोफाइलिंग किया और यह खुलासा करता है कि केवल 4% समय बिताया जाता है traverse[Non]Recursivly() जबकि 83% से अधिक सी ++ रनटाइम में खर्च किया जाता है v8::internal::JSObject::GetOwnElementKeys() (> 57%)।

[JavaScript]:
ticks  total  nonlib   name
98    4.0%    4.0%  LazyCompile: ~traverseRecursivly

...

[C++]:
ticks  total  nonlib   name
1399   57.6%   57.7%  v8::internal::JSObject::GetOwnElementKeys(...)

...

[Summary]:
ticks  total  nonlib   name
389   16.0%   16.0%  JavaScript
2037   83.8%   84.0%  C++
11    0.5%    0.5%  GC
4    0.2%          Shared libraries

[C++ entry points]:
ticks    cpp   total   name
1665   82.4%   68.5%  v8::internal::Runtime_GetPropertyNamesFast(...)
207   10.2%    8.5%  v8::internal::Runtime_SubStringRT(...)
...

निष्पादन में कोड प्रकार के लिए काला रंग का मतलब रनटाइम है


संबंधित सवाल
सबसे लोकप्रिय