1
votes

Comment puis-je raccourcir les appels massifs de la même méthode?

Je veux créer un arbre binaire avec des nombres aléatoires. Pour cela, j'ai une fonction qui génère l'arbre et une fonction qui génère les nombres aléatoires. En tant que variables d'instance, j'ai les éléments suivants:

public static void generateBinaryTree() {
        Position<Integer> root = tree.addRoot(generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child1 = tree.insertChild(root, generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child2 = tree.insertChild(root, generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child3 = tree.insertChild(child1, generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child4 = tree.insertChild(child1, generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child5 = tree.insertChild(child2, generateRandomInt(MIN_VALUE, MAX_VALUE));
        Position<Integer> child6 = tree.insertChild(child2, generateRandomInt(MIN_VALUE, MAX_VALUE));
        tree.insertChildren(child3, generateRandomInt(MIN_VALUE, MAX_VALUE), generateRandomInt(MIN_VALUE, MAX_VALUE));
        tree.insertChildren(child4, generateRandomInt(MIN_VALUE, MAX_VALUE), generateRandomInt(MIN_VALUE, MAX_VALUE));
        tree.insertChildren(child5, generateRandomInt(MIN_VALUE, MAX_VALUE), generateRandomInt(MIN_VALUE, MAX_VALUE));
        tree.insertChildren(child6, generateRandomInt(MIN_VALUE, MAX_VALUE), generateRandomInt(MIN_VALUE, MAX_VALUE));      
    }

Je pense que cela n'a pas l'air "beau" avec tous les appels generateRandomInt. Existe-t-il un moyen de raccourcir cela ou de le rendre plus efficace? Existe-t-il également un moyen de créer au hasard un arbre binaire (nombre de nœuds)? J'ai les méthodes suivantes pour ajouter quelque chose à un arbre:

public static int generateRandomInt(int MIN_VALUE, int MAX_VALUE) {
        return random.nextInt((MAX_VALUE - MIN_VALUE) + 1) + MIN_VALUE;
}

addRoot ajoute un nœud racine, insertLeftChild et insertRightChild ajoute un enfant gauche ou droit au nœud, insertChild fait de même, mais il vérifie si l'enfant gauche ou droit est libre, insertChildren ajoute un gauche et un enfant droit en même temps au nœud

addRoot(value)
insertLeftChild(node, value)
insertRightChild(node, value)
insertChild(node, value)
insertChildren(node, value1, value2)

private static final int MIN_VALUE = 1;
private static final int MAX_VALUE = 100;
private static LinkedBinaryTree<Integer> tree = new LinkedBinaryTree<>();
private static Random random = new Random();

java random

5 commentaires

Y a-t-il une différence entre insertChild et insertChildren ou est-ce une sorte d'erreur de copier-coller?

Et sans rapport: il est parfaitement juste d'avoir ces deux constantes MIN_VALUE et MAX_VALUE. Mais il est très faux de nommer les paramètres de votre méthode de la même manière . Votre méthode doit aller ... generateRandomIntInRange (int min, int max) . En utilisant les mêmes noms que vous avez déjà en place, vous ouvrez une boîte de problèmes!

@tobias_k Oui, il y a une différence. insertChildren ajoute un enfant gauche et un enfant droit à un nœud en même temps. insertChild insère un enfant (enfant droit ou gauche) dans un nœud.

Donc, insertChildren est fondamentalement juste deux appels à insertChild ? Dans ce cas, vous pouvez en effet créer une fonction récursive buildTree (int depth) pour faire tout cela pour vous.

@tobias_k insertChildren appelle insertLeft et insertRight. Ces méthodes proviennent d'une interface donnée. Je l'ai implémenté en utilisant insertLeft et insertRight. Mais vous avez raison, cela fonctionnerait également avec deux appels insertChild.

3 Réponses :

3
votes

Ajoutez simplement un autre assistant, comme:

public static int generateRandomInt() {
  return generateRandomInt(MIN_VALUE, MAX_VALUE);
}

Ensuite, vous pouvez créer des méthodes d'assistance qui créent simplement un enfant et l'ajoutent à une racine. Pour appeler ensuite cette méthode dans une boucle.

En gros, vous avez un modèle ici:

vous créez des objets Position (quels qu'ils soient, ne devraient-ils pas s'appeler Node ?)
vous ajoutez ces positions dans votre arborescence

Tout cela se produit à un niveau d'abstraction très bas. Vous devriez ajouter quelques abstractions utiles qui éliminent la nécessité de toujours noter tous les détails.

2 commentaires

En fait, je suggérerais d'appeler également la fonction generateRandomInt , pour préciser qu'il s'agit d'une version sans paramètre de la même fonction.

@tobias_k Bonne idée!

2
votes

Vous pouvez supprimer le passage des MIN_VALUE et MAX_VALUE partout, car c'est la même chose, vous pouvez donc supprimer les paramètres de votre fonction (ou créer un proxy) .

Mais vous ne pourrez pas avoir moins d'appels, car le résultat ne peut pas être mis en cache.

Ce que vous pouvez faire pour "embellir" votre code est d'utiliser une fonction récursive de terminal. Quelque chose comme:

public static void addChild(int depth, Position<Integer>  currentRoot) {
    Position<Integer> leftChild = currentRoot.insertLeftChild(generateRandomInt());
    Position<Integer> rightChild = currentRoot.insertRightChild(generateRandomInt());
    if(depth > 0) {
        addChild(depth - 1, leftChild);
        addChild(depth - 1, rightChild);
    }
}

Vous devrez peut-être modifier votre méthode insertChild () pour renvoyer le nœud inséré.

EDIT: Appelez les méthodes deux fois pour obtenir un arbre binaire.

3 commentaires

Juste ce que je pensais après avoir lu le commentaire d'OP sur addChildren , mais je pense que vous devriez appeler addChild deux fois de manière récursive pour obtenir un arbre binaire.

@tobias_k vous avez raison, je n'ai pas creusé dans les détails de l'implémentation, je voulais juste exposer l'idée générale de l'utilisation de la récursivité. Je modifierai alors pour utiliser addChildren () .

@Kevin FONTAINE merci beaucoup pour le partage de votre idée

2
votes

Semblable à ce que @GhostCat a suggéré, mais au lieu de définir une autre fonction, vous pouvez également simplement définir un Fournisseur dans le cadre de votre méthode. Surtout si les paramètres de la fonction aléatoire ne sont pas toujours les mêmes (peut-être des limites différentes lorsqu'elles sont utilisées dans une autre méthode), cela peut être avantageux. De plus, il est encore un peu plus court, car le Fournisseur déclaré localement n'a pas besoin d'avoir un nom trop descriptif.

public static void generateBinaryTree() {
    Supplier<Integer> rand = () -> generateRandomInt(MIN_VALUE, MAX_VALUE);

    Position<Integer> root = tree.addRoot(rand.get());
    Position<Integer> child1 = tree.insertChild(root, rand.get());
    ...
}

Mise à jour: em > Après avoir compris la différence entre addChild et addChildren , il est clair que vous pouvez en effet réécrire votre fonction de manière récursive comme addChildren (racine, profondeur) code> comme suggéré par @Kevin .

0 commentaires