Dev Faq
4
votes

Trouvez la profondeur de l'objet de manière itérative

J'écris une fonction pour calculer la profondeur d'un objet.

Voici ma version récursive qui semble fonctionner comme prévu: 

while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }

J'essaye maintenant d'écrire une version itérative, mais je ne trouve pas le meilleur moyen de faire fonctionner la boucle. 

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }
  let max = 1;
  let copy = Object.assign({}, obj);
  let keys = Object.keys(copy);
  while (keys.length) {
    if (typeof copy[keys[0]] !== "object" && copy[keys[0]] !== null) {
      delete copy[keys[0]];
      keys = Object.keys(copy);
    } else {
      max++;
      copy = Object.assign({}, copy[keys[0]]);
      keys = Object.keys(copy);
    }
  }
  return max;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

Comme vous pouvez le voir à partir de la sortie et du code, il ne prend que la première propriété à l'intérieur de la boucle: 

function findDepth(obj, firstCall = true) {
  if (firstCall && typeof obj !== "object") {
    return -1;
  }
  return Object.keys(obj).reduce((max, k) => {
    if (typeof obj[k] === "object" && obj[k] !== null) {
      const val = findDepth(obj[k], false) + 1;
      if (val > max) {
        max = val;
      }
    }
    return max;
  }, 1);
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepth(input1));
console.log(findDepth(input2));

L'idée était de supprimer la propriété chaque itération, mais je ne suis pas dans le bon sens. J'ai essayé de le changer avec copy [keys [keys.length - 1]] mais de cette façon, il ne prend que la dernière propriété à la place. En fait, le problème est de savoir comment boucler toutes les touches, à tous les niveaux de profondeur, comme dans la version récursive.

Une suggestion sur la façon d'implémenter cet algorithme de manière itérative?

Même toute suggestion sur la façon d'améliorer la récursive (ou si je manque quelque chose) est plus que bienvenue.

p.s. PAS DE LOADASH, UNDERSCORE, RAMDA, ou autre. Just Vanilla JS

0 commentaires

3 Réponses :

2
votes

Une façon d'itérer pourrait être une première recherche approfondie à l'aide d'une pile. 

function f(obj){
  if (typeof obj !== 'object' || obj === null)
    return 0;

  return Object.keys(obj).reduce((acc, k) => 
    Math.max(acc, 1 + f(obj[k])), 0);
}

Nous pourrions également rendre la récursion un peu plus succincte: 

function f(obj){
  let stack = Object.keys(obj).map(k => [obj[k], 1]);
  let max = 0;

  while (stack.length){
    let [maybeObj, d] = stack.pop();
    max = Math.max(max, d);
    if (typeof maybeObj == 'object' && maybeObj !== null)
      Object.keys(maybeObj).map(k =>
        stack.push([maybeObj[k], d + 1]));
  }

  return max;
}

5 commentaires

Heh, ou comme Mark Meyer l'a suggéré, utilisez Object.values.

votre k est indéfini à l'intérieur du while, il existe juste dans la première fonction map

@quirimmo cette réponse ne semble pas être appréciée, nonobstant les fautes de frappe.

Pour l'instant, tu vas devoir vivre avec mon erreur. (Cette réponse a le même algorithme que celui de Mark Meyer. Allez comprendre.)

brillant merci un million, et merci aussi pour le sucre syntaxique de la version récursive :) Super!

5
votes

Il vous suffit de garder une pile et d'y pousser les enfants tout en gardant une trace de la profondeur actuelle. Vous pouvez garder une trace de cela en poussant un tableau de [depth, obj] dans la pile, puis lorsque vous pop () ajoutez un à la profondeur avant de pousser les enfants. p> 

const input1  = {w: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk",q: {w: {z: "dsajkdasjdla"}}},h: "dsiaodsiad"}},a: "test",b: "test2",c: {d: "hello",f: {g: "dsadas",z: {b: "dsajkdasjldk"},h: "dsiaodsiad"}},e: "bye"};
  
  
function findDepthIterative(obj) {
    if (typeof obj !== "object") {
      return -1;
    }
    let max = 0;
    // current depth, children
    let stack = [[0, Object.values(obj)]];
    
    while(stack.length){
        let [depth, cur] = stack.pop()
        if (depth > max) max = depth

        if (typeof cur === "object" && cur !== null){
            Object.values(cur).forEach(c => stack.push([depth+1, c]))     
        }
    }
    return max
  }
  

console.log(findDepthIterative(input1))

// sanity check:
const depth0 = {}
const depth1 = {a:1}
const depth2 = {a:{b:2}}

console.log(findDepthIterative(depth0))
console.log(findDepthIterative(depth1))
console.log(findDepthIterative(depth2))

8 commentaires

désolé mon mauvais j'ai supprimé le commentaire, il y avait un typeof, même l'égal pas strict était bien :) désolé encore

C'est bien === c'est mieux.

@quirimmo génial? J'ai posté exactement le même algorithme une minute avant. Pas de manque de respect pour votre réponse éloquente, Mark Meyer. +1 de moi.

@ גלעדברקן pourquoi le prenez-vous si mal? Je suis aussi en train de passer en revue votre solution, donnez-moi juste le temps de le faire

@quirimmo J'ai dû passer une mauvaise journée, ha ha. Désolé pour ça.

@ גלעדברקן Les gars de MarkMeyer, vos solutions sont en fait les mêmes, et elles sont toutes les deux excellentes. J'ai voté pour les deux, mais je peux en marquer un comme correct (je suppose). Mark, ça vous dérange si je choisis le sien? Il a moins de points que vous, et il a également pris moins de votes positifs :)

C'est toujours à l'OP, @quirimmo - et ils sont venus en une minute plus vite!

merci à vous deux les gars ... Mark il a eu une mauvaise journée, alors essayons de le rendre plus heureux: D merci encore!

2
votes

Vous devriez utiliser un tableau au lieu de l'objet qui ne fonctionnera pas correctement s'il y a des clés en double. Le tableau doit contenir tous les objets qui se produisent à un certain niveau. Pour chaque itération, vous mappez le tableau dans un nouveau contenant les enfants directs des objets précédents: 

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];
  let levels = 0;

  do {
    levels++;
    
    let newArr = [];
    arr.forEach(obj => {
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;
  } while (arr.length);

  return levels;
}

const input1 = {
  a: {
    b: "test",
    c: {
      d: {
        e: {
          f: [1, 2, 3],
          g: {
            a: null,
            z: {
              d: "casdsadasdsa",
              q: {
                z: {
                  i: undefined
                }
              }
            }
          }
        }
      },
      c: {
        a: "sad"
      }
    },
    d: {
      e: 5
    }
  },
  b: {
    c: {
      d: "dsada"
    }
  }
};

const input2 = {
  w: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk",
        q: {
          w: {
            z: "dsajkdasjdla"
          }
        }
      },
      h: "dsiaodsiad"
    }
  },
  a: "test",
  b: "test2",
  c: {
    d: "hello",
    f: {
      g: "dsadas",
      z: {
        b: "dsajkdasjldk"
      },
      h: "dsiaodsiad"
    }
  },
  e: "bye"
};

console.log(findDepthIterative(input1));
console.log(findDepthIterative(input2));

Démo:

p > 

function findDepthIterative(obj) {
  if (typeof obj !== "object") {
    return -1;
  }

  let arr = [obj];                                          // the array containing the objects that occur at a certain level, initially contains obj being the only object at the first level
  let levels = 0;                                           // levels counter

  do {                                                      // keep doing this
    levels++;                                               // increment the levels counter

    let newArr = [];                                        // make a new array for the next level
    arr.forEach(obj => {                                    // populate it with the old level objects' children
      for(let key in obj) {
        if(obj[key] && typeof obj[key] === "object") {
          newArr.push(obj[key]);
        }
      }
    });
    arr = newArr;                                          // make arr the new array of object (next level)
  } while (arr.length);                                    // while there are still levels with objects in them

  return levels;
}

1 commentaires

Merci beaucoup! est absolument logique. Peut-être que je préfère simplement la solution avec la pile, même si la logique est à peu près la même. Merci encore :)

Articles qui pourrait vous intéresser :

Impossible d'importer le module "@ angular / material"
Interaction profonde avec break and catch
Utilisation de node.js comment renommer tous les fichiers d'un dossier
Google Chrome Uncaught (promis) DOMException lors de la lecture AUDIO