获取条目的所有后代

Question

我有一个庞大的推荐系统（超过 500k 个条目），其工作原理如下

 [{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];
}

现在我有两个问题：

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

Answer 1

您可以实现广度优先算法，而不是深度优先算法。在 JavaScript 中，aSet将是一个很好使用的数据结构，因为集合的条目总是按插入顺序迭代，并且for..of只要新条目添加到正在循环的集合中，集合上的循环就会继续循环，给出它是队列的行为。

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

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

第二个函数不返回树，而是返回后代列表。所以我也将其重命名为：

// 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);