Tengo un enorme sistema de referidos (más de 500k entradas) que funciona así
[{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}] Cada vez que un usuario se une con el código de referencia de otro usuario, el remitente obtiene algunos créditos y se aplica a todos los niveles, por lo que en este ejemplo, John obtiene crédito por estas ID [2, 3, 5, 6]
Utilizo este método para contar y organizar todas las entradas en función de su ID de referencia.
const countRefs = (list) => { return list.reduce((acc, cur) => { if(!acc[cur.ref]) acc[cur.ref] = []; acc[cur.ref].push(cur.id); return acc; },{}); }Y luego use esta función recursiva para obtener todos los usuarios referidos por una 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]; }Ahora tengo dos preguntas:
Maximum Call Stack Error . ¿Estoy haciendo algo mal aquí?En lugar de primero en profundidad, podría implementar un algoritmo primero en amplitud. En JavaScript, un Set será una buena estructura de datos con la que trabajar, ya que las entradas de un conjunto siempre se for..of en orden de inserción, y un bucle for...of sobre un conjunto seguirá en bucle mientras se agreguen nuevas entradas al conjunto. siendo enlazado, dándole el comportamiento de una cola.
Un conjunto también actuará como checked : si una entrada ya está en el conjunto, agregarla de nuevo no tendrá ningún efecto en el conjunto y, por lo tanto, la entrada no se visitará por segunda vez.
No se necesita ningún cambio para countRefs , pero le daría un nombre diferente, ya que no devuelve un recuento, sino un árbol.
Y la segunda función no devuelve un árbol, sino una lista de descendientes. Así que también cambiaría el nombre de ese:
// 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);Esta parece una buena oportunidad para usar una estructura de datos para escribir una solución escalable.
Cree una estructura de datos de árbol a partir de los datos de referencia
id de nodo secundario a la ref del nodo Tenga en cuenta que, por definición, el árbol no debe tener ciclos, es decir, una entrada no debe tener su propia identificación como ref .
Una vez que el árbol está en su lugar, el problema se reduce a encontrar el número total de nodos en cada uno de los subárboles del árbol, que es un problema bien estudiado. La complejidad de tiempo requerida para resolver esto es O(n) , donde n es el número total de nodos.
En este caso, el crédito para un id en particular será:
Number of nodes in the subtree where that id is the root node - 1 (excluyéndose a sí mismo).
Implemente el DFS de forma iterativa en lugar de usar llamadas recursivas para evitar el desbordamiento de la pila (sin juego de palabras)