¿Hay una forma más rápida de obtener los subárboles de las estructuras tipo árbol en python que el estándar "recursivo"?
tree subtree (4)
Supongamos la siguiente estructura de datos con tres matrices numpy (id, parent_id) (parent_id del elemento raíz es -1):
import numpy as np
class MyStructure(object):
def __init__(self):
"""
Default structure for now:
1
/ /
2 3
/ /
4 5
"""
self.ids = np.array([1,2,3,4,5])
self.parent_ids = np.array([-1, 1, 1, 3, 3])
def id_successors(self, idOfInterest):
"""
Return logical index.
"""
return self.parent_ids == idOfInterest
def subtree(self, newRootElement):
"""
Return logical index pointing to elements of the subtree.
"""
init_vector = np.zeros(len(self.ids), bool)
init_vector[np.where(self.ids==newRootElement)[0]] = 1
if sum(self.id_successors(newRootElement))==0:
return init_vector
else:
subtree_vec = init_vector
for sucs in self.ids[self.id_successors(newRootElement)==1]:
subtree_vec += self.subtree(sucs)
return subtree_vec
Esto es realmente lento para muchos identificadores (> 1000). ¿Hay una forma más rápida de implementar eso?
En teoría, cada algoritmo se puede escribir de forma iterativa y recursiva. Pero esto es una falacia (como Turing-completitud). En la práctica, caminar un árbol anidado arbitrariamente mediante iteración generalmente no es factible. Dudo que haya mucho que optimizar (al menos estás modificando subtree_vec en el lugar). Hacer x en miles de elementos es intrínsecamente costoso, no importa si lo haces de forma iterativa o recursiva. A lo sumo, hay algunas micro-optimizaciones posibles en la implementación concreta, que a lo sumo rendirán <5% de mejora. La mejor opción sería almacenar en caché / memoria, si necesita los mismos datos varias veces. Tal vez alguien tiene un sofisticado algoritmo O (log n) para la estructura de árbol específica en la manga, ni siquiera sé si es posible (supongo que no, pero la manipulación de árboles no es mi personal de la vida).
Creo que no es la recursividad lo que te está perjudicando, sino la multitud de operaciones muy amplias (sobre todos los elementos) para cada paso. Considerar:
init_vector[np.where(self.ids==newRootElement)[0]] = 1
Eso ejecuta un escaneo a través de todos los elementos, calcula el índice de cada elemento coincidente, luego usa solo el índice del primero. Esta operación en particular está disponible como el índice de método para listas, tuplas y matrices, y más rápido allí. Si los ID son únicos, init_vector es simplemente ids == newRootElement de todos modos.
if sum(self.id_successors(newRootElement))==0:
De nuevo, un escaneo lineal de cada elemento, luego una reducción en toda la matriz, solo para verificar si hay alguna coincidencia. Use cualquiera para este tipo de operación, pero una vez más ni siquiera necesitamos verificar todos los elementos - "si newRootElement no está en self.parent_ids" hace el trabajo, pero no es necesario ya que es perfectamente válido para hacer un bucle sobre una lista vacía.
Finalmente está el último ciclo:
for sucs in self.ids[self.id_successors(newRootElement)==1]:
Esta vez, se repite una llamada id_successors, y luego el resultado se compara con 1 innecesariamente. Solo después de eso viene la recursión, asegurándose de que todas las operaciones anteriores se repitan (para diferentes newRootElement) para cada rama.
El código completo es un recorrido inverso de un árbol unidireccional. Tenemos padres y necesitamos niños. Si vamos a hacer operaciones amplias, como numpy está diseñado para, lo mejor será que cuenten, y por lo tanto, la única operación que nos importa es crear una lista de hijos por padre. Eso no es muy difícil de hacer con una iteración:
import collections
children=collections.defaultdict(list)
for i,p in zip(ids,parent_ids):
children[p].append(i)
def subtree(i):
return i, map(subtree, children[i])
La estructura exacta que necesita dependerá de más factores, como la frecuencia con que cambia el árbol, su tamaño, la cantidad de ramificaciones y la cantidad y la cantidad de subárboles que debe solicitar. La estructura del diccionario + lista anterior no es terriblemente eficiente en cuanto a la memoria, por ejemplo. Su ejemplo también está ordenado, lo que podría facilitar aún más la operación.
Esta es mi respuesta (escrita sin acceso a su clase, por lo que la interfaz es ligeramente diferente, pero la adjunto como está para que pueda probar si es lo suficientemente rápida):
======================= Archivo graph_array.py ======================= ===
import collections
import numpy
def find_subtree(pids, subtree_id):
N = len(pids)
assert 1 <= subtree_id <= N
subtreeids = numpy.zeros(pids.shape, dtype=bool)
todo = collections.deque([subtree_id])
iter = 0
while todo:
id = todo.popleft()
assert 1 <= id <= N
subtreeids[id - 1] = True
sons = (pids == id).nonzero()[0] + 1
#print ''id={0} sons={1} todo={2}''.format(id, sons, todo)
todo.extend(sons)
iter = iter+1
if iter>N:
raise ValueError()
return subtreeids
======================= Archivo graph_array_test.py ======================= ===
import numpy
from graph_array import find_subtree
def _random_graph(n, maxsons):
import random
pids = numpy.zeros(n, dtype=int)
sons = numpy.zeros(n, dtype=int)
available = []
for id in xrange(1, n+1):
if available:
pid = random.choice(available)
sons[pid - 1] += 1
if sons[pid - 1] == maxsons:
available.remove(pid)
else:
pid = -1
pids[id - 1] = pid
available.append(id)
assert sons.max() <= maxsons
return pids
def verify_subtree(pids, subtree_id, subtree):
ids = set(subtree.nonzero()[0] + 1)
sons = set(ids) - set([subtree_id])
fathers = set(pids[id - 1] for id in sons)
leafs = set(id for id in ids if not (pids == id).any())
rest = set(xrange(1, pids.size+1)) - fathers - leafs
assert fathers & leafs == set()
assert fathers | leafs == ids
assert ids & rest == set()
def test_linear_graph_gen(n, genfunc, maxsons):
assert maxsons == 1
pids = genfunc(n, maxsons)
last = -1
seen = set()
for _ in xrange(pids.size):
id = int((pids == last).nonzero()[0]) + 1
assert id not in seen
seen.add(id)
last = id
assert seen == set(xrange(1, pids.size + 1))
def test_case1():
"""
1
/ /
2 4
/
3
"""
pids = numpy.array([-1, 1, 2, 1])
subtrees = {1: [True, True, True, True],
2: [False, True, True, False],
3: [False, False, True, False],
4: [False, False, False, True]}
for id in xrange(1, 5):
sub = find_subtree(pids, id)
assert (sub == numpy.array(subtrees[id])).all()
verify_subtree(pids, id, sub)
def test_random(n, genfunc, maxsons):
pids = genfunc(n, maxsons)
for subtree_id in numpy.arange(1, n+1):
subtree = find_subtree(pids, subtree_id)
verify_subtree(pids, subtree_id, subtree)
def test_timing(n, genfunc, maxsons):
import time
pids = genfunc(n, maxsons)
t = time.time()
for subtree_id in numpy.arange(1, n+1):
subtree = find_subtree(pids, subtree_id)
t = time.time() - t
print ''t={0}s = {1:.2}ms/subtree = {2:.5}ms/subtree/node ''.format(
t, t / n * 1000, t / n**2 * 1000),
def pytest_generate_tests(metafunc):
if ''case'' in metafunc.function.__name__:
return
ns = [1, 2, 3, 4, 5, 10, 20, 50, 100, 1000]
if ''timing'' in metafunc.function.__name__:
ns += [10000, 100000, 1000000]
pass
for n in ns:
func = _random_graph
for maxsons in sorted(set([1, 2, 3, 4, 5, 10, (n+1)//2, n])):
metafunc.addcall(
funcargs=dict(n=n, genfunc=func, maxsons=maxsons),
id=''n={0} {1.__name__}/{2}''.format(n, func, maxsons))
if ''linear'' in metafunc.function.__name__:
break
=================== py.test --tb = short -v -s test_graph_array.py ============
... test_graph_array.py:72: test_timing[n=1000 _random_graph/1] t=13.4850590229s = 13.0ms/subtree = 0.013485ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/2] t=0.318281888962s = 0.32ms/subtree = 0.00031828ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/3] t=0.265519142151s = 0.27ms/subtree = 0.00026552ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/4] t=0.24147105217s = 0.24ms/subtree = 0.00024147ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/5] t=0.211434841156s = 0.21ms/subtree = 0.00021143ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/10] t=0.178458213806s = 0.18ms/subtree = 0.00017846ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/500] t=0.209936141968s = 0.21ms/subtree = 0.00020994ms/subtree/node PASS test_graph_array.py:72: test_timing[n=1000 _random_graph/1000] t=0.245707988739s = 0.25ms/subtree = 0.00024571ms/subtree/node PASS ...
Aquí se toma cada subárbol de cada árbol, y el valor interesante es el tiempo medio para extraer un árbol: ~ 0.2ms por subárbol, excepto para árboles estrictamente lineales. No estoy seguro de lo que está sucediendo aquí.
¿Has intentado usar el módulo psyco si estás usando Python 2.6? A veces puede acelerar dramáticamente el código.
¿Ha considerado la estructura de datos recursiva: lista?
Su ejemplo también es una lista estándar:
[1, 2 , [3, [4], [5]]]
o
[1, [2, Ninguno, Ninguno], [3, [4, Ninguno, Ninguno], [5, Ninguno, Ninguno]]]
Por mi bonita impresora :
[1,
[2, None, None],
[3,
[4, None, None],
[5, None, None]]]
Los subárboles están listos allí, le costará algo de tiempo insertar valores en el árbol derecho. También vale la pena comprobar si el módulo heapq se ajusta a sus necesidades.
También el propio Guido da algunas ideas sobre el desplazamiento y los árboles en http://python.org/doc/essays/graphs.html , tal vez usted esté consciente de ello.
Aquí hay algunas cosas de árbol de aspecto avanzado, realmente propuestas para Python como reemplazo de tipo de lista básica, pero rechazadas en esa función. Módulo Blist