在递归函数中计算 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 它。
这种方法的一个有趣之处在于,您可以围绕其他递归节点转换技术重用 nest
和 unnest
。从completed
到percent
的roll-up在那个地方是孤立的,但是整体机制是共享的。
我正在尝试制作一个以递归方式计算“已完成任务”百分比的函数。
这是我现在所拥有的,但这只计算 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 它。
这种方法的一个有趣之处在于,您可以围绕其他递归节点转换技术重用 nest
和 unnest
。从completed
到percent
的roll-up在那个地方是孤立的,但是整体机制是共享的。