Algorithme pour agréger les valeurs des noeuds enfant

J'ai des objets dans une structure arborescente, je voudrais agréger les informations d'état des noeuds enfants et mettre à jour le noeud parent avec l'état agrégé. Disons que le noeud A a les enfants B1, B2 et B1 a C1, C2, C3 comme enfants. Chacun des nœuds a un attribut d'état. Maintenant, si C1, C2, C3 sont toutes terminées, je voudrais marquer B1 comme terminé. Et si C4, C5, C6, C7 sont complets, complétez B2. Lorsque B1 et B2 sont tous les deux remplis, marquez A comme terminée.Algorithme pour agréger les valeurs des noeuds enfant

Je peux passer ces nœuds en mode de force brute et faire des mises à jour, quelqu'un pourrait-il suggérer un algorithme efficace pour le faire.

A { B1 {C1, C2, C3}, B2 {C4, C5, C6, C7} }

Source

2010-03-24 tech20nn

Tout ce qui va aider à sauver les cycles de CPU/mémoire. – tech20nn

Quelle est la taille de votre arbre? À quelle fréquence effectuez-vous cette opération? Pouvez-vous permettre une certaine "staleness"? La façon de résoudre cela plus efficacement n'est généralement pas à travers une optimisation de bas niveau, mais en utilisant toutes les connaissances que vous avez sur votre problème. Vous pouvez mettre en cache des résultats dans certains sous-arbres, propager des drapeaux "incomplets" dans l'arbre quand un enfant devient incomplet, etc. –

J'ai environ 5000 arbres. Chaque arbre a de 3 à 4 niveaux de profondeur. Chaque niveau pourrait avoir environ 20-50 nœuds. Je prévois d'exécuter ce processus une fois par jour. Le processus pour les arbres individuels peut être exécuté sur demande. On dirait qu'avec ces données, je n'ai pas besoin de mise en cache, mais je vais l'explorer. Merci de faire ressortir ces paramètres importants. – tech20nn

Vous avez besoin traversal post-order - première visite aux enfants d'un noeud, marquez ensuite le noeud lui-même, de manière récursive.

Quelque chose comme (pseudo-code):

iscomplete(node): 
    if node == Null: 
    return False 
    elsif no children: 
    return some "complete" value according to node value 
    else: 
    for child in node.children: 
     if not iscomplete(child): 
      return False 

    return True

Source

2010-03-24 17:20:30

Vous pouvez éviter de traverser l'arborescence entière si vous pompez continuellement le statut dans l'arborescence, marquant ainsi le nœud parent de manière appropriée avec chaque modification apportée à l'enfant. Cela nécessite que l'enfant connaisse le parent, bien sûr, mais vous permet de connaître l'état général avec une simple vérification de la racine. – Yuval

@Yuval: oui, c'est un compromis. Il peut être plus efficace dans certaines situations, selon la fréquence à laquelle vous changez d'enfant et à quelle fréquence vous interrogez le statut. –

@Yuval: Voir ma réponse ci-dessous pour un pseudocode pour cela. –

-1

Je ne peux pas voir que vous pouvez échapper à la "force brute".

Je voudrais utiliser le modèle de conception de visiteur.

http://www.javaworld.com/javaworld/javatips/jw-javatip98.html

http://sourcemaking.com/design_patterns/visitor

Source

2010-03-24 17:24:37 Yaneeve

Utilisation d'un "modèle de conception" pour résoudre une traversée arborescente algorithmique triviale. Bon sang ... ce que les jours sont sur nous ;-) –

Comme il n'a pas été précis sur son code, je pensais que je lui remettre des outils plus « puissants » – Yaneeve

(-1) Je ne vois pas comment peut être résolu par arbre traversal un modèle de visiteur. – harschware

Eli Bendersky a raison, la réponse générale à ce problème est traversal post-commande.

Pour plus d'efficacité, cependant, vous devez utiliser tout ce que vous savez du problème. Par exemple, si vous pouvez autoriser une certaine "staleness", il peut être préférable de mettre en cache un indicateur complete et un horodatage dans chaque nœud.

Une autre possibilité est que l'état interne complete des nœuds change rarement. Dans ce cas, il peut être préférable de propager jusqu'à informations d'exhaustivité. Quelque chose comme ça:

class NodeWithCompletenessInfo : public Node { 

    private bool internalComplete; // Am I personally done? 
    private bool childrenComplete; // Are my children done? 

    public bool isComplete() { 
    return internalComplete && childrenComplete; 
    } 

    public void markComplete() { 
    internalComplete = true; 
    if(isComplete()) 
     parent.markChildComplete(); 
    } 

    public void markIncomplete() { 
    if(isComplete()) 
     parent.markChildIncomplete(); 
    internalComplete = false; 
    } 

    private void markChildComplete() { 
    for(child in children) { 
     if(!child.isComplete()) 
     return; 
     childrenComplete = true; 
    } 
    if(isComplete()) 
     parent.markChildComplete() 
    } 

    private void markChildIncomplete() { 
    if(isComplete()) 
     parent.markChildIncomplete(); 
    this.childrenComplete = false; 
    } 
}

Source

2010-03-24 17:24:45

Merci Philippe pour la logique globale. – tech20nn

Si vous savez quels sont les nœuds de feuilles puis

A { 
    B1 
     {C1, C2 = false, C3}, 
    B2 
     {C4, C5=false, C6=false, C7} 
    } // those not marked false are true ;) 

not_complete_leaf_nodes_with_different_parents = [ C2 , C5] 

mark_not_complete(node): 
    node.complete = false 
    if parent != null 
     mark_not_complete(node.parent) 

for each in not_complete_leaf_nodes_with_different_parents: 
    mark_not_complete(each.parent)

Source

2010-03-24 17:41:38

Algorithme pour agréger les valeurs des noeuds enfant

Répondre

Questions connexes