使用递归javascript承诺在树中搜索节点 [英] search node in a tree using recursive javascript promises
问题描述
我被困在基于 Javascript 承诺的程序中，无法弄清楚如何让它以承诺格式返回正确的值.
I am stuck in Javascript promise based program and not able to figure out how to get it to return the right value, in a promise format.
给定一个 Tree API，它返回一个节点的子节点作为 PROMISE.例如:
Given an Tree API that returns children of a node as PROMISE. Eg:
tree.getChildren('/2/4')
.then(function (nodes) {
console.log(nodes); // logs 7,8,9 as children of node 4
}
使用 tree.getChildren 方法，searchNode 方法应该递归地尝试在树中查找 searchValue 并在找到时返回其路径，null 否则.
using tree.getChildren method, the searchNode method should recursively try to look for searchValue in the tree and return its path if found, null otherwise.
下面的方法只是尝试在树路径中搜索节点，但它只是返回 undefined，我认为这是由于方法的异步性质.我如何重写代码以兑现承诺并获得所需的行为?
The method below, simply tries to search for the node in a tree path, but it is just returning undefined, which I believe is due to async nature of the method. How do I rewrite the code to honour promises and get desired behaviour?
function searchNode(searchValue, path){
tree.getChildren(path).then(function(children){
if(children.length>0){
for(var i = 0; i<children.length; i++){
if(children[i] == searchValue){
return path;
} else {
childPath = searchNode(searchValue, path+"/"+children[i]);
if(childPath != null)
return childPath;
}
}
}
else{
return null;
}
})
}
推荐答案
当结果异步可用时，函数 searchNode 将需要返回一个 Promise.
As the result becomes available asynchronously, the function searchNode will need to return a Promise.
但是在两个地方你不这样做:
But at two places you do not do this:
你应该返回对
tree.getChildren的第一次调用
searchNode 的(递归)返回值应该被当作一个 promise 来处理，而你却把它当作一个同步结果:
The (recursive) return value of searchNode should be handled as a promise, yet you treat it as a synchronous result:
childPath = searchNode(searchValue, path+"/"+children[i]);
if (childPath != null) { // ...etc.
这是不可能的.返回值应该是一个promise，因此您需要对其调用then 方法来获取返回值.
This is not possible. The return value should be a promise, and so you would need to call the then method on it to get the return value.
由于您需要迭代多个甚至全部子代，您将获得尽可能多的承诺.但是你可以而且应该只返回一个承诺.
As you need to iterate several, maybe all, of the children, you would get as many promises back. But you can and should only return one promise.
尽管您可以在找不到值的情况下返回 null，但在我看来，它更符合 promise 在这种情况下生成被拒绝的 promise 的想法.
Although you could return null in case of not finding the value, it is in my opinion more in line with the idea of promises to produce a rejected promise in that case.
所以你可以得到第一个承诺的结果，然后如果它解决了，返回那个承诺，但是如果它拒绝(即没有找到)你应该链接下一个承诺，然后下一个，......直到一个解决，并返回那个.如果它们都没有解决，或者没有孩子，则应返回被拒绝的承诺.
So you could get the result of the first of those promises and then if it resolves, return that promise, but if it rejects (i.e. not found) you should chain the next promise, and the next, ... until one resolves, and return that one. If none of them resolve, or there are no children, a rejected promise should be returned.
这是建议的代码:
function searchNode(searchValue, path){
return tree.getChildren(path).then(function(children){
// First look for the value among the immediate children
for(let i = 0; i<children.length; i++){
if(children[i] == searchValue){
return path;
}
}
// Then look deeper
return (function loop(i) {
if (i >= children.length) {
return Promise.reject("not found");
} else {
// after asynchronous result comes in, either
// continue the loop, or resolve with path
return searchNode(searchValue, path+"/"+children[i])
.catch(loop.bind(null, i+1));
}
})(0);
}
"use strict";
// Simple implementation of tree
const tree = {
root: {
'2': {
'4': {
'1': {}
},
'7': {}
},
'0': {}
},
getChildren: function(path) {
return new Promise(function (resolve) {
const node = path.split('/').reduce(function (parent, node) {
return node === '' || !parent ? parent : parent[node];
}, tree.root);
resolve(Object.keys(node));
});
}
};
function searchNode(searchValue, path){
return tree.getChildren(path).then(function(children){
// First look for the value in the immediate children
for(let i = 0; i<children.length; i++){
if(children[i] == searchValue){
return path;
}
}
// Then look deeper
return (function loop(i) {
if (i >= children.length) {
return Promise.reject("not found");
} else {
// after asynchronous result comes in, either
// continue the loop, or resolve with path
return searchNode(searchValue, path+"/"+children[i])
.catch(loop.bind(null, i+1));
}
})(0);
})
}
// Demo
searchNode('1', '').then(function (path) {
console.log(path);
}, function (reason) {
console.log(reason);
});上述解决方案不会在孩子之间并行查找.相反，它将等待一个节点的搜索结果，然后再决定是否应为下一个兄弟节点启动搜索.根据 tree.getChildren 实现的异步程度，这可能效率低下:
The above solution will not look among the children in parallel. Instead it will wait for the search result for one node before deciding whether the search should be launched for the next sibling node. Depending on how asynchronous the tree.getChildren implementation really is, this may be inefficient:
想象一棵树，其中第一个子节点有一个包含 1000 个节点的多级子树，而要查找的值是第二个子节点的直接后代.如果搜索将并行启动，您会期望在这种情况下更快地获得结果.另一方面，一旦找到值，上面的代码将不会搜索其他兄弟节点，而通过并行搜索，即使在找到值并且主要承诺是之后，搜索也会在后台"(异步)继续解决.因此，我们应该确保在找到该值后不会启动更深层次的搜索.
Imagine a tree where the first child node has a multi-level sub-tree of 1000 nodes, while the value being looked for is an immediate descendant of the second child node. If the search would be launched in parallel, you'd expect the result sooner for such a scenario. On the other hand, the above code will not search other sibling nodes once the value has been found, while with a parallel search the search would continue in the "background" (asynchronously) even after the value has been found and the main promise is resolved. So we should make sure that no deeper searches are initiated when the value has been found.
为了实现这种并行搜索的想法，您将立即在所有子节点上启动 searchNode，并在每个子节点上应用 then 方法来监控哪个解析为第一个.
In order to implement this parallel search idea you would launch searchNode on all children immediately, and apply the then method on each to monitor which one resolves as the first.
为此，您实际上可以定义两个通用实用程序方法——Promise.not 和 Promise.some --，就像已经有 Promise 一样.Race 和 Promise.all.这些函数可以在其他问答中找到，比如 Resolve ES6 Promise with第一次成功?":
For this you could in fact define two generic utility methods -- Promise.not and Promise.some --, much like there already are Promise.race and Promise.all. These functions can be found in other Q&A like "Resolve ES6 Promise with first success?":
// Invert the outcome of a promise
Promise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolves
Promise.some = iterable => Promise.not(Promise.all(iterable.map(Promise.not)));
或者，您可以为此使用库解决方案，例如 bluebird 的 Promise.any.
Or, you could use a library solution for this, like bluebird's Promise.any.
然后，您需要添加一些机制来停止启动更深入的搜索，当主要承诺已经用找到的值解决时.为此，只需在解决时听取主要承诺和标志就足够了.这可用于停止异步代码以启动任何进一步的搜索.
Then, you would need to add some mechanism to stop initiating deeper searches when the main promise has already been resolved with the found value. For this it suffices to listen to the main promise and flag when it resolves. This can be used to stop the asynchronous code to initiate any further searches.
在您的情况下，您将如何使用 Promise.some 函数:
Here is how you would use that Promise.some function in your case:
function searchNode(searchValue, path){
let resolved = false;
return (function searchNodeSub(path) {
return tree.getChildren(path).then(function(children){
// If we already found the value via another parallel search, quit
return resolved ? true
// Otherwise look for the value among the immediate children
: children.some(child => child == searchValue) ? path
// If not found there, look deeper -- in parallel
: Promise.some(children.map(child => searchNodeSub(path+"/"+child)));
})
})(path).then( path => (resolved = true, path) ); // register that we have a result
}
注意 children.some 和 Promise.some 之间的相似性.
Note the similarity between children.some and Promise.some.
"use strict";
// Simple implementation of tree
const tree = {
root: {
'2': {
'4': {
'1': {}
},
'7': {}
},
'0': {}
},
getChildren: function(path) {
return new Promise(function (resolve) {
let node = path.split('/').reduce(function (parent, node) {
return node === '' || !parent ? parent : parent[node];
}, tree.root);
resolve(Object.keys(node));
});
}
};
// Invert the outcome of a promise
Promise.not = promise => promise.then(x => {throw x}, e => e);
// Resolve when the first promise resolves
Promise.some = iterable => Promise.not(Promise.all(iterable.map(Promise.not)));
function searchNode(searchValue, path){
let resolved = false;
return (function searchNodeSub(path) {
return tree.getChildren(path).then(function(children){
// If we already found the value via another parallel search, quit
return resolved ? true
// Otherwise look for the value among the immediate children
: children.some(child => child == searchValue) ? path
// If not found there, look deeper -- in parallel
: Promise.some(children.map(child => searchNodeSub(path+"/"+child)));
})
})(path).then( path => (resolved = true, path) ); // register that we have a result
}
// Demo
searchNode('1', '').then(function (path) {
console.log(path);
}, function (reason) {
console.log('Not found');
});这篇关于使用递归javascript承诺在树中搜索节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
