javascript - 使用对象数组

Question

我有一个对象数组，可以包含相同对象类型的子对象，如下所示:

var exampleArray = [
    {
        alias: 'alias1',
        children: [
            {
                alias: 'child1'
            },
            {
                alias: 'child2',
                children: [
                    {
                        alias: 'child4'
                    },
                    {
                        alias: 'child5'
                    }
                ]
            },
            {
                alias: 'child3'
            }
        ]
    },
    {
        alias: 'alias2'
    },
    {
        alias: 'alias3',
        children: [
            {
                alias: 'child6'
            },
            {
                alias: 'child7'
            }
        ]
    }
];

基础对象还有其他属性，但它们对手头的问题并不重要。现在，让我们假设对象可以是:

{
    alias: 'string',
    children: []
}

child 是可选的。

我正在寻找用这样的对象管理某些事物的最佳方法/最快方法。我已经创建了一些递归方法来完成一些我想要的事情，但我想知道是否有更好的方法来完成以下任务:

1. hasAlias(arr, alias) - 我需要确定整个对象是否包含具有给定别名的任何对象。

目前，我递归地执行此操作，但鉴于此数组可以无限增长，递归方法最终会达到堆栈限制。

1. getParent(arr, alias) - 我需要能够获得包含具有给定别名的元素的父元素。鉴于别名对整个数组是唯一的，因此永远不会有两个相同的别名。我现在再次递归地执行此操作，但我想找到更好的方法来执行此操作。

2. deleteObject(arr, alias) - 我不确定目前如何完成这个。我需要能够传递一个数组和一个别名，并从给定的数组中删除该对象(及其所有子对象)。我开始使用递归方法来执行此操作，但停了下来并决定改为在此处发布。

我使用的是 Node.js 并且有 lodash 可用于更快的处理方法。我对 JavaScript 还是很陌生，所以我不确定是否有更好的方法来处理像这样的更大规模数组。

Answer 1

在不支持递归的 FORTRAN 时代，人们通过更改数据集来模拟“递归”级别来实现类似的效果。将此原则应用于示例对象结构，可以编写一个函数来通过其“别名”(名称或另一个词的 id)查找对象而无需递归，如下所示:

function findAlias( parent, alias) // parent object, alias value string
{   function frame( parent)
    {   return {parent: parent, children: parent.children,
        index: 0, length: parent.children.length};
    }
    var stack, tos, child, children, i;

    stack = [];
    if( parent.children)
        stack.push( frame( parent));

    search:
    while( stack.length)
    {   tos = stack.pop();  // top of generation stack
        children = tos.children;
        for( i = tos.index; i < tos.length; ++i)
        {   child = children[i]; 
            if( child.alias == alias)
            {   return { parent: tos.parent, child: child, childIndex: i}
            }
            if( child.children)
            {   tos.index = i + 1;
                stack.push(tos);  // put it back
                stack.push( frame(child));
                continue search;
            }
        }
    }
    return null;
}

简而言之，最终会创建一堆小型数据对象，这些对象在同一个函数中被压入和弹出，而不是进行递归调用。上面的示例返回了一个对象，它具有 parent 和 child 对象值。子值是具有提供的别名属性的值，父对象是其 children 数组中的子值。

如果找不到别名则返回 null，因此可用于 hasAlias 功能。如果它不返回 null，它会执行 getParent 功能。但是，您必须创建一个根 Node :

// create a rootnode
var rootNode = { alias: "root", children: exampleArray}; 
var found = findAlias(rootNode, "alias3");
if( found)
{  console.log("%s is a child of %s, childIndex = %s",
       found.child.alias, found.parent.alias, found.childIndex);
}
else
   console.log("not found");

---

[编辑:添加 childIndex 以搜索返回对象，更新测试示例代码，添加结论。]

结论

在支持树行走应用程序时使用递归函数调用在自记录代码和可维护性方面是有意义的。如果可以证明非递归变体在降低容量压力测试下的服务器负载方面具有显着优势，但需要完善的文档，那么它可能会为自己付出代价。

无论内部编码如何，返回包含父项、子项和子项索引值详细信息的对象的树遍历函数可能会通过减少曾经执行的树遍历总数来提高整体程序效率:

• 搜索返回值的真实性替代了 hasAlias 函数
• 可以将搜索的返回对象传递给更新、删除或插入函数，而无需在每个函数中重复进行树搜索。