与对象数组一起工作

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: []
}

孩子们是可选的。

我正在寻找管理像这样的对象的最佳方法/最快方法。我已经创建了一些递归方法来执行我想要的一些操作，但我想知道是否有更好的方法来完成以下任务：

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

目前，我使用递归来实现，但考虑到这个数组可以有限地增长，递归方法最终会达到堆栈限制。

2. getParent（arr，alias）-我需要能够获得包含具有给定别名的元素的父级。鉴于别名对整个数组是唯一的，永远不会有两个相同的别名。 我现在也是递归做这个，但我想找到更好的方法。

3. deleteObject（arr，alias）-我现在不确定如何完成此操作。我需要能够传递一个数组和一个别名，并将该对象（及其所有子项）从给定数组中删除。我开始了一个递归方法来做到这一点，但停止并决定在这里发布。

我正在使用Node.js，并且有lodash可用于更快地处理事务。 对于像这样的大规模数组，我仍然是相对较新的JavaScript用户，因此不确定有没有更好的方法来处理。

- atom0s

---

我认为你可以将整个数组分成两个或三个部分，并单独调用当前的方法。这样你就可以针对一个特定的部分进行操作。你会有很大的改进。 - Hugo S. Mendes

我不确定我会这样做，但是顺便说一下，如果单词“alias”没有出现在其他地方等等，hasAlias可以使用类似于JSON.stringify(arr).indexOf('alias')的东西来完成。 - adeneo

我认为递归是有意义的，除非你有成千上万个嵌套子元素，否则不太可能达到堆栈限制。你可以尝试将其变成尾递归并使用跳板函数，或者运行一个转换器将其转换为循环。 - elclanrs

你会考虑使用索引来加速吗？当前版本的Node.js列出了对Map和WeakMap的支持，这在这方面可能很有用，但是构建和维护索引的复杂性也会被引入。 - traktor

我无法更改对象的构造，因为它们是预定义数据，超出了我的控制范围，无法编辑其模型。 - atom0s

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功能。但是，您必须创建根节点：

// 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函数
• 可以将搜索返回的对象传递给update、remove或insert函数，而无需在每个函数中重复进行树形搜索。

- traktor

---

它在每次搜索时不断分配内存。在服务器上可能会导致严重后果。在客户端上只会变得缓慢。 - Peter Aron Zentai

Answer 2

保证最快的方法显然是拥有

- an index for the aliases (thats actually a unique id)
- have a parent backlink on each child item (if it has a parent)

你查询了id为index的元素

var index = {}
(function build(parent) {
   index[parent.alias] = parent;
   (parent.children || []).forEach( item => {
       item.parent = parent
       build(item)
   })
})(objectRoot)


function hasAlias(alias) { return alias in index }

function getAlias(alias) { return index[alias] } 

function getParent(alias) { return index[alias] && index[alias].parent}

删除别名意味着将其及其子项从索引中和仍留在索引中的父项中删除。

function deleteAlias(alias) {

   function deleteFromIndex(item) {
      delete index[item.alias]
      (item.children || []).forEach(deleteFromIndex)
   }
   var item = index[alias]
   item.parent.children.splice(item.parent.children.indexOf(item))
   deleteFromIndex(item)

}

- Peter Aron Zentai

Answer 3

我可能会以稍微不同的方式处理您的主数组，并将其保留为引用其他项而不是完全合并它们的平坦数组。

var flat = [
    {
        alias : "str1",
        children : [ flat[1], flat[2] ],
        parent : null   
    },

    {
        alias : "str1",
        children : [],
        parent : flat[0]    
    },

    {
        alias : "str1",
        children : [],
        parent : flat[0]    
    }
]

这有点像“链表”的方法。链表有优缺点，但你可以快速地迭代所有项目。

- bob