Как размножить узлы дерева в Python - PullRequest
Новая
       10

Как размножить узлы дерева в Python

1 голос
/ 28 августа 2011

Я имею дело с древовидной структурой в программе Python. У каждого узла в дереве есть словарь «сыновья», ключи которого содержат информацию о дуге и значения являются узлами сына. Вопрос в том, чтобы распространить список узлов всем их сыновьям. Я использую: 

current_nodes = reduce(lambda s,x:s+x, map(lambda node:node.sons.values(),current_nodes),[])

Где current_nodes - начальный (и обновленный) список узлов.

Моя программа тратит большую часть времени на выполнение этой операции уменьшения. Есть ли более быстрый способ реализовать это?

Спасибо!

EDIT: Привет, Просто дай знать, что код: sum((node.sons.values() for node in current_nodes), []) хотя pythonic, на самом деле не значительно быстрее - если список узлов является длинным (> 20000), распространение замедляется непропорционально, на самом деле, очень медленно. Я не знаю почему.

Тогда я определяю: 

def Ext(nodes)
    l=[]
    for node in nodes:
        l.extend(node.sons.values())
    return l

Тогда я использую: current_node = Ext(current_node). Этот подход на самом деле намного быстрее. Я предполагаю, что функция sum () не так эффективна, как метод расширения списка при обработке конкатенации списка.

1 Ответ

4 голосов
/ 28 августа 2011 
from itertools import chain
list(chain.from_iterable(node.sons.values() for node in current_nodes))

Должно быть быстрее.map и reduce на lambda с медленные.Я не знаю, как быстро chain;Вы можете попробовать 

sum((node.sons.values() for node in current_nodes), [])

.

...