javascript - 使用递归 JavaScript Promise 在树中搜索 Node

Question

我陷入了基于 Javascript Promise 的程序中，无法弄清楚如何让它以 Promise 格式返回正确的值。

给定一个 Tree API，该 API 将 Node 的子 Node 返回为 PROMISE。例如:

tree.getChildren('/2/4')
.then(function (nodes) {    
    console.log(nodes); // logs 7,8,9 as children of node 4
}

使用tree.getChildren方法，searchNode方法应该递归地尝试在树中查找searchValue，如果找到则返回其路径，否则返回null。

下面的方法只是尝试在树路径中搜索 Node ，但它只是返回 undefined，我认为这是由于该方法的异步性质。如何重写代码以兑现 promise 并获得所需的行为？

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;
        }
    })
}

Answer 1

当结果异步可用时，函数 searchNode 将需要返回一个 Promise。

但是在两个地方你不这样做:

1. 您应该返回第一次调用tree.getChildren

2. searchNode 的(递归)返回值应该作为 promise 来处理，但您却将其视为同步结果:

    childPath = searchNode(searchValue, path+"/"+children[i]);
    if (childPath != null) { // ...etc.
   

   这是不可能的。返回值应该是一个 promise ，因此您需要调用 then方法来获取返回值。

由于您需要迭代几个(也许是所有)子级，因此您将得到尽可能多的 promise 。但你可以而且应该只返回一个 promise 。

虽然你可以返回 null如果找不到值(value)，我认为在这种情况下产生被拒绝的 promise 更符合 promise 的想法。

因此，您可以获得第一个 promise 的结果，然后如果它解决了，则返回该 promise ，但如果它拒绝(即未找到)，您应该链接下一个 promise ，然后是下一个，...直到一个解决，然后返回该 promise 。如果他们都没有解决，或者没有 child ，则应返回拒绝的 promise 。

这是建议的代码:

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);
});

并行搜索替代方案

上述解决方案不会在子级之间并行查找。相反，它会等待一个 Node 的搜索结果，然后再决定是否应该启动下一个兄弟 Node 的搜索。取决于异步的方式tree.getChildren实现确实如此，这可能效率低下:

想象一棵树，其中第一个子 Node 具有 1000 个 Node 的多级子树，而正在查找的值是第二个子 Node 的直接后代。如果并行启动搜索，您会期望在这种情况下更快得到结果。另一方面，一旦找到值，上面的代码将不会搜索其他兄弟 Node ，而使用并行搜索，即使在找到值并且主要 promise 得到解决之后，搜索也会在“后台”(异步)继续进行。因此，我们应该确保在找到该值后不会启动更深入的搜索。

为了实现这种并行搜索想法，您需要立即在所有子 Node 上启动 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)));

或者，您可以使用库解决方案，例如 bluebird's Promise.any .

然后，当主要 promise 已经通过找到的值得到解决时，您需要添加一些机制来停止启动更深入的搜索。为此，只需听取主要 promise 并在解决时进行标记即可。这可用于停止异步代码以启动任何进一步的搜索。

以下是如何使用 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');
});