我有一個龐大的推薦系統（超過 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。我在這里做錯什么了嗎？
uj5u.com熱心網友回復：
您可以實作廣度優先演算法，而不是深度優先。在 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);uj5u.com熱心網友回復：
這似乎是使用資料結構撰寫可擴展解決方案的好機會。
從參考資料構建樹形資料結構
- 為每個唯一 ID 創建一個節點
- 為資料中的每一個條目，添加一個子節點
id到該節點ref
請注意，根據定義樹不應該有回圈，即條目不應該有自己的 id
ref一旦樹就位，問題歸結為找到樹的每個子樹中的節點總數，這是一個經過深入研究的問題。解決這個問題所需的時間復雜度是
O(n)，其中 n 是節點的總數。在這種情況下，特定 id 的信用將是：
Number of nodes in the subtree where that id is the root node - 1（不包括自身）。迭代地實作 DFS，而不是使用遞回呼叫來避免堆疊溢位（沒有雙關語）
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/440652.html
標籤：javascript 节点.js 循环 递归 遍历