Existe-t-il un moyen plus rapide d'obtenir des sous-arbres à partir de structures arborescentes en python que le "récursif" standard?

Question

Supposons que le structur de données suivantes avec trois tableaux numpy (id, id_parent) (parent_id de l'élément racine est -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 

Ce get vraiment lent pour beaucoup ids (> 1000). Existe-t-il un moyen plus rapide de mettre en œuvre cela?

Answer 1

En théorie, chaque algorithme peut être écrit de manière itérative ou récursive. Mais c'est une erreur (comme Turing-complétude). En pratique, la marche d'un arbre arbitrairement imbriqué par itération n'est généralement pas réalisable. Je doute qu'il y ait beaucoup à optimiser (au moins vous modifiez subtree_vec in-place). Faire x sur des milliers d'éléments est intrinsèquement sacrément cher, peu importe si vous le faites de manière itérative ou récursive. Tout au plus quelques micro-optimisations sont possibles sur la mise en œuvre concrète, ce qui donnera au mieux une amélioration de 5%. Le meilleur pari serait la mise en cache/mémo, si vous avez besoin des mêmes données plusieurs fois. Peut-être que quelqu'un a un algorithme O (log n) sophistiqué pour votre structure arborescente spécifique dans leur manche, je ne sais même pas si c'est possible (je suppose que non, mais la manipulation des arbres n'est pas mon personnel).

Answer 2

Avez-vous essayé d'utiliser le module psyco si vous utilisez Python 2.6? Il peut parfois faire une accélération spectaculaire du code.

Avez-vous considéré la structure de données récursive: liste?

Votre exemple est également sous forme de liste standard:

[1, 2, [3, [4], [5]]]

ou

[1 , [2, Aucune, Aucune], [3, [4, Aucune, Aucune], [5, Aucune, Aucune]]]

mes pretty printer:

[1, 
    [2, None, None], 
    [3, 
    [4, None, None], 
    [5, None, None]]] 

Subtrees sont prêts là, vous coûtent un certain temps d'insérer des valeurs à arbre droit. Aussi la peine de vérifier si heapq module répond à vos besoins.

Aussi Guido lui-même donne un aperçu sur la traversée et les arbres dans http://python.org/doc/essays/graphs.html, peut-être vous le savez.

Voici quelques trucs d'arborescence à la recherche avancée, actuellement proposés pour Python comme remplacement de type liste de base, mais rejetés dans cette fonction. Blist module

Answer 3

Voici ma réponse (écrit sans accès à votre classe, de sorte que l'interface est légèrement différente, mais je suis tout comme l'attacher afin que vous puissiez tester si elle est assez rapide):
==== =================== fichier 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 

fichier ======================= 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 = court -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 
... 

Ici, chaque sous-arbre de chaque arbre est prise, et la valeur intéressante est le temps moyen de extraire un arbre: ~ 0.2ms par sous-arbre, sauf pour les arbres strictement linéaires. Je ne suis pas sûr de ce qui se passe ici.

Answer 4

Je pense que ce n'est pas la récursivité en tant que telle qui vous fait mal, mais la multitude d'opérations très larges (sur tous les éléments) pour chaque étape. Tenir compte:

init_vector[np.where(self.ids==newRootElement)[0]] = 1 

qui exécute un balayage à travers tous les éléments, calcule l'indice de chaque élément correspondant, utilise alors que l'indice de la première. Cette opération particulière est disponible en tant qu'index de méthode pour les listes, les tuples et les tableaux - et plus rapidement. Si les ID sont uniques, init_vector est simplement ids == newRootElement.

if sum(self.id_successors(newRootElement))==0: 

Encore une fois un balayage linéaire de chaque élément, puis une réduction sur la totalité du tableau, juste pour vérifier si les matchs sont là. Utilisez any pour ce type d'opération, mais encore une fois, nous n'avons même pas besoin de vérifier tous les éléments - "si newRootElement n'est pas dans self.parent_ids" fait le travail, mais ce n'est pas nécessaire car il est parfaitement boucle sur une liste vide.

Enfin, il y a la dernière boucle:

for sucs in self.ids[self.id_successors(newRootElement)==1]: 

Cette fois-ci, un appel id_successors est répété, et le résultat est comparé à 1 inutilement. Seulement après cela vient la récursivité, en s'assurant que toutes les opérations ci-dessus sont répétées (pour newRootElement différent) pour chaque branche.

Le code entier est une traversée inversée d'un arbre unidirectionnel. Nous avons des parents et avons besoin d'enfants. Si nous devons effectuer des opérations de grande envergure comme celles pour lesquelles numpy est conçu, nous ferions mieux de les compter - et donc la seule opération qui nous intéresse est de dresser une liste d'enfants par parent. Ce n'est pas très difficile à faire avec une itération:

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 structure exacte dont vous avez besoin dépendra de plusieurs facteurs, tels que la fréquence des changements d'arbres, la taille, il est, comment les branches bien, et la taille et de nombreux sous-arbres que vous devez demander. La structure de dictionnaire + liste ci-dessus n'est pas très efficace sur le plan de la mémoire, par exemple. Votre exemple est également trié, ce qui pourrait rendre l'opération encore plus facile.