使用递归javascript承诺在树中搜索节点
我困在基于Javascript承诺的程序中，无法找到如何让它以承诺格式返回正确的值。
给定返回节点子节点的Tree作为承诺。例：
tree.getChildren('/2/4')
.then(function (nodes) {
console.log(nodes); // logs 7,8,9 as children of node 4
}使用tree.getChildren方法，searchNode方法应该递归地尝试在树中查找searchValue，如果找到它的路径，则返回路径，否则返回null。
下面的方法只是尝试搜索树路径中的节点，但它只是返回undefined，我认为这是由于该方法的异步性质造成的。我如何重写代码以兑现承诺并获得期望的行为？
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;
}
})
}回答 2
Stack Overflow用户
发布于 2017-02-04 22:40:35
当结果异步可用时，函数searchNode将需要返回一个承诺。
但在两个地方，你不能这样做：
- 您应该返回对
tree.getChildren的第一个调用 - 应该将
searchNode的(递归)返回值作为承诺处理，但将其视为同步结果： childPath = searchNode(searchValue，path+"/"+childreni)；if (childPath != null) { // ...etc。 这是不可能的返回值应该是一个承诺，因此您需要调用它上的then方法来获得返回值。
当您需要迭代几个，也许是所有的子程序时，您将得到同样多的承诺。但你可以而且应该只回一个承诺。
虽然您可以在找不到值的情况下返回null，但在我看来，在这种情况下，它更符合承诺产生被拒绝的承诺的想法。
因此，你可以得到第一个承诺的结果，然后如果它解决了，返回那个承诺，但如果它拒绝(即找不到)，你应该连锁下一个承诺，下一个，.直到一个人解决了，然后把那个还回去。如果他们都没有决心，或者没有孩子，就应该回报一个被拒绝的承诺。
以下是建议的代码：
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实现的实际异步性，这可能效率很低：
想象一棵树，其中第一个子节点有一个由1000个节点组成的多层子树，而要查找的值是第二个子节点的直接后代。如果搜索是并行启动的，那么对于这种情况，您将期望更早地得到结果。另一方面，一旦找到值，上述代码将不会搜索其他同级节点，而通过并行搜索，即使在找到值并解决了主要承诺之后，搜索仍将在“背景”(异步)中继续进行。因此，我们应该确保在找到值时不会启动更深层次的搜索。
为了实现这种并行搜索思想，您将立即在所有子节点上启动searchNode，并在每个子节点上应用then方法来监视哪个解析为第一个。
为此，您实际上可以定义两个通用实用程序方法-- Promise.not和Promise.some --就像已经有Promise.race和Promise.all一样。这些函数可以在其他类似于"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)));或者，您可以使用库解决方案来解决这个问题，比如Promise.any。
然后，您需要添加一些机制，以便在主承诺已经用已找到的值解决时，停止启动更深层次的搜索。对于这一点，只要听主要的承诺和标志，当它解决。这可用于停止异步代码以启动任何进一步的搜索。
下面是如何在您的情况下使用该Promise.some函数：
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之间的相似之处。
"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');
});
Stack Overflow用户
发布于 2017-02-04 22:07:15
您需要在.getChildren()中返回searchNode承诺，以便在返回childPath时等待它得到解决。
function searchNode(searchValue, path){
return tree.getChildren(path).then(function(children){ //return the promise so we can later wait for it to resolve
if(children.length>0){
for(var i = 0; i<children.length; i++){
if(children[i] == searchValue){
return path;
} else {
return searchNode(searchValue, path+"/"+children[i])
.then(function(childPath){ //wait for searchNode to complete
if (childPath != null) {
return childPath;
}
});
}
}
}
else{
return null;
}
})
}https://stackoverflow.com/questions/42045988
复制相似问题
腾讯云开发者
