获取条目的所有后代

Question

我有一个庞大的推荐系统（超过 50 万个条目），其工作方式如下

 [{id: 1, name: "John", ref: 0},
  {id: 2, name: "Jack", ref: 1},
  {id: 3, name: "Bill", ref: 1},
  {id: 5, name: "Jason", ref: 2},
  {id: 6, name: "James", ref: 3},
  {id: 7, name: "Tom", ref: 0}]

每当用户使用其他用户的推荐代码加入时，推荐人都会获得一些积分，它适用于所有级别，因此在此示例中 John 获得此 ID 的积分 [2, 3, 5, 6]

我使用此方法根据推荐 ID 对所有条目进行计数和组织

   const countRefs = (list) => {
      return list.reduce((acc, cur) => {
        if(!acc[cur.ref]) acc[cur.ref] = [];
        acc[cur.ref].push(cur.id);
        return acc;
      },{});
    }

然后使用这个递归函数通过 ID 获取所有推荐的用户。

let depth = 0;
// Keep record of checked IDs
const checked = {};

const getTree = (list, ref) => {
// Check if referrer is already checked to avoid cycles
if(checked[ref]) return [];
  const ids = [];
  const items = list[ref] || [];
  checked[ref] = true;
  if (items.length && depth < 35000) {
    depth += 1;
    for (let ref of items) {
      if(!list[ref]) continue;
      const deep = getTree(list, ref, depth);
      ids.push(...deep);
    }
  }


  checked = {};
  depth = 0;
  return [...ids, ...items];
}

现在我有两个问题：

有更好的方法吗？喜欢在第一个循环中创建所有关系？
通过一些条目，我得到 Maximum Call Stack Error。我在这里做错了什么吗？

Answer 1

您可以实现 breadth-first 算法而不是 depth-first。在 JavaScript 中，Set 将是一个很好的数据结构，因为集合的条目总是在 insertion-order 中迭代，并且集合上的 for..of 循环将保持只要将新条目添加到正在循环的集合中，就会循环，使其具有队列的行为。

一个集合也将作为checked：如果一个条目已经在集合中，再次添加它不会对集合产生任何影响，因此不会再次访问该条目。

不需要对 countRefs 进行更改，但我会给它一个不同的名称，因为它不是 return 计数，而是一棵树。

第二个函数不是 return 树，而是后代列表。所以我也会重命名那个：

// No change to this function
const makeTree = (list) => {
  return list.reduce((acc, cur) => {
    if (!acc[cur.ref]) acc[cur.ref] = [];
    acc[cur.ref].push(cur.id);
    return acc;
  }, {});
}

// Use breadth-first
const getDescendants = (list, ref) => {
  const children = new Set(list[ref] ?? []);
  for (const child of children) {
    for (const grandchild of list[child] ?? []) children.add(grandchild);
  }
  return [...children];
}

const list = [{id: 1, name: "John", ref: 0},
  {id: 2, name: "Jack", ref: 1},
  {id: 3, name: "Bill", ref: 1},
  {id: 5, name: "Jason", ref: 2},
  {id: 6, name: "James", ref: 3},
  {id: 7, name: "Tom", ref: 0}]

const tree = makeTree(list);
const descendants = getDescendants(tree, 1);
console.log(descendants);

Answer 2

这似乎是使用数据结构编写可扩展解决方案的好机会。

从参考数据构建树数据结构
- 为每个唯一的 id 创建一个节点
- 对于数据中的每个条目，添加一个子节点id到节点ref
请注意，根据定义树不应该有循环，即一个条目不应该有自己的 id ref
树就位后，问题归结为找到树的每个子树中的节点总数，这是一个经过充分研究的问题。解决这个问题所需的时间复杂度是 O(n)，其中 n 是节点总数。

在这种情况下，特定 ID 的功劳将是：

Number of nodes in the subtree where that id is the root node - 1（不包括自身）。

迭代地实现 DFS 而不是使用递归调用来避免堆栈溢出（没有双关语意）

获取条目的所有后代

Get all descendants of an entry

javascript

recursion

loops

traversal

node.js