Liste imbriquée à la chaîne

J'ai une liste d'instances de la classe Test. Cette classe a comme méthode name et parentListe imbriquée à la chaîne

[Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')]

Le premier argument est le nom, second parent. L'argument parent est simplement un argument name de la classe parente. Je veux convertir cette liste à chaîne comme:

Test('a', '') 
    |-- Test('c', 'a') 
     |-- Test('e', 'c') 
    |-- Test('d', 'a') 
Test('b', '')

Je recherche de la façon la plus CPU efficace pour convertir cette liste à chaîne. Les éléments de la liste peuvent être imbriqués à des niveaux multiples (10, 100, 1000, ...), et je me fiche de la mémoire utilisée.

Source

2011-07-03 Galmi

Avez-vous une question ou un endroit précis où vous êtes bloqué? Pouvez-vous poster le code que vous avez essayé jusqu'à présent et obtenez une erreur avec, ou vous cherchez des idées sur la meilleure solution? –

Modifié. Désolé pour cela :) Je cherche du code ou une idée pour le faire de manière CPU-efficace. – Galmi

Voici le code qui fonctionne tel quel. Fondamentalement convertir le tableau dans un arbre, puis utiliser DFS récursive pour imprimer (vous pouvez utiliser DFS itérative si vous voulez):

class Test: 
    def __init__(self, name, parent): 
     self.name = name 
     self.parent = parent 
    def __repr__(self): 
     return "Test('"+self.name+"', '"+self.parent+"')" 



li = [Test('a', ''), Test('b', ''), Test('c', 'a'), Test('d', 'a'), Test('e', 'c')] 

dict = {"":(None,[])} #name to (node,children) 
#add nodes 
for item in li: 
    dict[item.name] = (item, []) 
#add children 
for item in li: 
    dict[item.parent][1].append(dict[item.name]) 

def printTree(dict, name, indent): 
    newIndent=indent 
    if name!="": 
     print(indent + str(dict[name][0])) 
     if indent == "": newIndent=" |-- " 
     else: newIndent = "  "+indent 
    for child in dict[name][1]: 
     printTree(dict, child[0].name, newIndent) 


printTree(dict, "", "")

Source

2011-07-03 05:00:11

vous créez N références à chaque élément (où N est la profondeur). Ce code sera mauvais pour les grandes entrées ... –

non, je ne ... pourquoi le pensez-vous? –

vous avez: '{'': [a: [c: e, d], b], a: [c: e, d], b, c: e, d, e}' –

Vous devez utiliser un autre conteneur, comme ça:

class Test: 
    def __init__(self, name, sub=None): 
     self.name = name 
     self.sub = sub if sub is not None else [] 

elements = [Test('a', [Test('c', [Test('e')]), Test('d')]), Test('b')]

puis juste itérer elements à imprimer:

def show(x, indent=0): 
    for i in x: 
     print('\t'*indent + 'Test(%r)' % i.name) 
     show(i.sub, indent+1) 

show(elements)

devrait imprimer:

Test('a') 
    Test('c') 
     Test('e') 
    Test('d') 
Test('b')

Vous pouvez changer l'indentation à tout ce que vous préférez (j'utilise des onglets).

Source

2011-07-03 04:47:48 JBernardo

Si vous vous retrouvez à l'aide DFS comme vous pouvez suggérez fiver utiliser NetworkX

import networkx as nx 
stuff=[('a', ''), ('b', ''), ('c', 'a'), ('d', 'a'), ('e', 'c')] 
G=nx.DiGraph() 
for i in stuff: 
    G.add_edge(i[1],i[0]) 
print G.adj

Ensuite, il est une question d'itérer avec DFS

Source

2011-07-03 05:15:48

Liste imbriquée à la chaîne

Répondre

Questions connexes