在递归函数中计算 objects

Calculating on objects in recursive function

我正在尝试制作一个以递归方式计算“已完成任务”百分比的函数。

这是我现在所拥有的,但这只计算 parent 的百分比,而不是 grandparent 等:

const tasks = [
    { id: 1, task: 'Clean apartment', completed: null, parentId: null},
    { id: 2, task: 'Make app', completed: null, parentId: null},
    { id: 3, task: 'Clean bathroom', completed: null, parentId: 1},
    { id: 4, task: 'Clean kitchen', completed: null, parentId: 1},
    { id: 5, task: 'Wash sink', completed: true, parentId: 3},
    { id: 6, task: 'Wash shower', completed: null, parentId: 3},
    { id: 7, task: 'Wash glass panes', completed: null, parentId: 6},
    { id: 8, task: 'Wash floor', completed: null, parentId: 6},
]

function compileTask(tasks, taskId) {
    var task = (typeof taskId === 'number') ? tasks.find(task => task.id === taskId) : taskId;
    var children = tasks.filter(t => t.parentId === task.id);

    task.percent = children.filter(c => c.completed === true).length / children.length * 100


    task.children = children.map(child => compileTask(tasks, child));
    return task
}

console.log(compileTask(tasks, 1))

如您所见,任务 ID 3 已完成 50%,因为两个 child 任务之一已标记为已完成,但任务 ID 1 已完成 0%。如果我在脑海中计算正确,任务 ID 1 应该 return 25% 已完成。

有什么建议吗?

您正在混合 objects 和整数。

var task = (typeof taskId === 'number') ? tasks.find(task => task.id === taskId) : taskId;

returns 一种情况下是任务,另一种情况下是 id

那么这里

task.children = children.map(child => compileTask(tasks, child));

您传递的是 child 而不是 child.id。应该是

task.children = children.map(child => compileTask(tasks, child.id));

我不太确定你想要的输出格式,所以我将生成如下所示的格式。我们可能会根据您的需要对其进行更改:

[
  {id: 1, task: 'Clean apartment', percent: 25, parentId: null}
  {id: 2, task: 'Make app', percent: 0, parentId: null}
  {id: 3, task: 'Clean bathroom', percent: 50, parentId: 1}
  {id: 4, task: 'Clean kitchen', percent: 0, parentId: 1}
  {id: 5, task: 'Wash sink', percent: 100, parentId: 3}
  {id: 6, task: 'Wash shower', percent: 0, parentId: 3}
  {id: 7, task: 'Wash glass panes', percent: 0, parentId: 6}
  {id: 8, task: 'Wash floor', percent: 0, parentId: 6}
]

初始方法

这是一个相当简单的递归技术:

const sum = (ns) => ns .reduce ((a, b) => a + b, 0)

const findPercent = (task, tasks, children = tasks .filter (({parentId}) => task .id == parentId)) => 
  children .length 
    ? sum (children .map (c => findPercent(c, tasks))) / children .length
    : task .completed ? 100 : 0

const compileTasks = (tasks) => tasks .map (
  (task, _, __, {completed, parentId, ...rest} = task) => ({
    ...rest, 
    percent: findPercent (task, tasks), 
    parentId
  })
)

const tasks = [{id: 1, task: 'Clean apartment', completed: null, parentId: null}, {id: 2, task: 'Make app', completed: null, parentId: null}, {id: 3, task: 'Clean bathroom', completed: null, parentId: 1}, {id: 4, task: 'Clean kitchen', completed: null, parentId: 1}, {id: 5, task: 'Wash sink', completed: true, parentId: 3}, {id: 6, task: 'Wash shower', completed: null, parentId: 3}, {id: 7, task: 'Wash glass panes', completed: null, parentId: 6}, {id: 8, task: 'Wash floor', completed: null, parentId: 6}]

console .log (compileTasks (tasks))
.as-console-wrapper {max-height: 100% !important; top: 0}

findPercent 是一个辅助函数,它递归地查看 children,并对它们的百分比进行平均。当没有 children 时它触底,然后根据任务是否 completed 选择 0% 或 100%。它使用了一个简单的 sum 帮助程序,该帮助程序将数字数组相加。

主要功能是compileTasks。它只是将任务列表映射到略有改动的版本,删除 completed 并添加 percent,这是通过调用 findPercent.

找到的

不过,此技术存在潜在问题。对于小测试来说完全没有关系,但是有很多工作是多次完成的。我们把7和8的百分比平均,建1的时候,然后建3的时候再做一次,建6的时候再做一次。这是有问题的,所以我会建议:

更高效的方法

这里的问题是我们的平面列表并不是跟踪树结构的最佳方式。这会更容易使用:

[
    {id: 1, task: "Clean apartment", completed: null, children: [
        {id: 3, task: "Clean bathroom", completed: null, children: [
            {id: 5, task: "Wash sink", completed: true},
            {id: 6, task: "Wash shower", completed: null, children: [
                {id: 7, task: "Wash glass panes", completed: null},
                {id: 8, task: "Wash floor", completed: null}
            ]}
        ]},
        {id: 4, task: "Clean kitchen", completed: null}
    ]},
    {id: 2, task: "Make app", completed: null}
]

我建议您考虑一直在内部使用这种更有用的结构,并且只使用平面列表进行存储。但如果你不能,就这样做,然后我们可以在两种结构之间来回转换,并在更好的树结构上进行计算。它可能看起来像这样:

const sum = (ns) => ns .reduce ((a, b) => a + b, 0)

const nest = (tasks, parent = null) =>
  tasks .filter (({parentId}) => parentId === parent) .map (
    ({id, parentId, ...rest}, _, __, children = nest (tasks, id)) => ({
      id, ...rest, ...(children.length ? {children} : {})
    }))

const unnest = (nodes, parentId = null) => [
  ...nodes .map (({children, ...rest}) => ({...rest, parentId})),  
  ...nodes .flatMap (node => unnest (node .children || [], node.id))
]

const calcPcts = (tasks) =>
  tasks .map (({completed, children = [], ...rest}, _, __, kids = calcPcts (children)) => ({
    ... rest,
    ... (kids .length 
          ? {percent: sum (kids .map (k => k.percent)) / kids .length, children: kids} 
          : {percent: completed ? 100 : 0}
        )
  }))

const compileTasks = (tasks) => 
  unnest (calcPcts (nest (tasks)))

const tasks = [{id: 1, task: 'Clean apartment', completed: null, parentId: null}, {id: 2, task: 'Make app', completed: null, parentId: null}, {id: 3, task: 'Clean bathroom', completed: null, parentId: 1}, {id: 4, task: 'Clean kitchen', completed: null, parentId: 1}, {id: 5, task: 'Wash sink', completed: true, parentId: 3}, {id: 6, task: 'Wash shower', completed: null, parentId: 3}, {id: 7, task: 'Wash glass panes', completed: null, parentId: 6}, {id: 8, task: 'Wash floor', completed: null, parentId: 6}]

console .log (compileTasks (tasks))
.as-console-wrapper {max-height: 100% !important; top: 0}

在这里,在 sum 助手之后,我们有一个 nest 函数可以将平面列表转换为树结构,还有一个 unnest 函数可以将其转换为树状结构进入平面列表。

我们的主要函数是compileTasks,它只是将这两个函数组合起来,运行它们之间的核心函数calcPcts,生成这个中间格式:

[
    {id: 1, task: "Clean apartment", percent: 25, children: [
        {id: 3, task: "Clean bathroom", percent: 50, children: [
            {id: 5, task: "Wash sink", percent: 100},
            {id: 6, task: "Wash shower", percent: 0, children: [
                {id: 7, task: "Wash glass panes", percent: 0},
                {id: 8, task: "Wash floor", percent: 0}
            ]}
        ]},
        {id: 4, task: "Clean kitchen", percent: 0}
    ]},
    {id: 2, task: "Make app", percent: 0}
]

现在我们需要讨论 calcPcts。这与上面的工作方式非常相似,除了因为我们正在调用 top-down 并从下向上滚动结果,所以我们不必为嵌套节点 re-call 它。

这种方法的一个有趣之处在于,您可以围绕其他递归节点转换技术重用 nestunnest。从completedpercent的roll-up在那个地方是孤立的,但是整体机制是共享的。