Efficienza di ricerca del percorso in Python

Question

Ho scritto del codice che trova tutti i percorsi a monte di una determinata portata in una rete di flusso dendritico. Come esempio, se rappresento la seguente rete:

 4 -- 5 -- 8 
    /
    2 --- 6 - 9 -- 10 
/   \ 
1    -- 11 
    \ 
    3 ----7 

come un insieme di coppie padre-figlio:

{(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)} 

esso ritornerà tutti i percorsi a monte di un nodo, ad esempio:

get_paths(h, 1) # edited, had 11 instead of 1 in before 
[[Reach(2), Reach(6), Reach(9), Reach(11)], [Reach(2), Reach(6), Reach(9), Reach(10)], [Reach(2), Reach(4), Reach(5), Reach(8)], [Reach(3), Reach(7)]] 

Il codice è incluso di seguito.

La mia domanda è: lo dico in riferimento questo per ogni raggiungere in un grande (ad esempio, New England) per cui un dato portata può avere milioni di percorsi. Probabilmente non c'è modo di evitare che si tratti di un'operazione molto lunga, ma esiste un modo pitonioso per eseguire questa operazione in modo tale che non vengano generati percorsi nuovi ogni volta?

Ad esempio, se corro get_paths (h, 2) get_paths e tutti i percorsi a monte da 2 si trovano, posso successivamente eseguire (h, 1) senza ripercorrere tutti i percorsi a 2?

import collections 

# Object representing a stream reach. Used to construct a hierarchy for accumulation function 
class Reach(object): 
    def __init__(self): 
     self.name = None 
     self.ds = None 
     self.us = set() 

    def __repr__(self): 
     return "Reach({})".format(self.name) 


def build_hierarchy(flows): 
    hierarchy = collections.defaultdict(lambda: Reach()) 
    for reach_id, parent in flows: 
     if reach_id: 
      hierarchy[reach_id].name = reach_id 
      hierarchy[parent].name = parent 
      hierarchy[reach_id].ds = hierarchy[parent] 
      hierarchy[parent].us.add(hierarchy[reach_id]) 
    return hierarchy 

def get_paths(h, start_node): 
    def go_up(n): 
     if not h[n].us: 
      paths.append(current_path[:]) 
     for us in h[n].us: 
      current_path.append(us) 
      go_up(us.name) 
     if current_path: 
      current_path.pop() 
    paths = [] 
    current_path = [] 
    go_up(start_node) 
    return paths 

test_tree = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)} 
h = build_hierarchy(test_tree) 
p = get_paths(h, 1) 

EDIT: Qualche settimana fa ho fatto una domanda simile su come trovare raggiunge "ALL" a monte in una rete e ha ricevuto una risposta eccellente che è stato molto veloce:

class Node(object): 

    def __init__(self): 
     self.name = None 
     self.parent = None 
     self.children = set() 
     self._upstream = set() 

    def __repr__(self): 
     return "Node({})".format(self.name) 

    @property 
    def upstream(self): 
     if self._upstream: 
      return self._upstream 
     else: 
      for child in self.children: 
       self._upstream.add(child) 
       self._upstream |= child.upstream 
      return self._upstream 

import collections 

edges = {(11, 9), (10, 9), (9, 6), (6, 2), (8, 5), (5, 4), (4, 2), (2, 1), (3, 1), (7, 3)} 
nodes = collections.defaultdict(lambda: Node()) 

for node, parent in edges: 
    nodes[node].name = node 
    nodes[parent].name = parent 
    nodes[node].parent = nodes[parent] 
    nodes[parent].children.add(nodes[node]) 

ho notato che la def upstream(): parte di questo codice aggiunge nodi upstream in ordine sequenziale, ma poiché è una funzione iterativa non riesco a trovare un buon modo per aggiungerli a una singola lista. Forse c'è un modo per modificare questo codice che conserva l'ordine.

Answer 1

Sì, è possibile farlo. Non sono completamente sicuro di quali siano i tuoi limiti; tuttavia, questo dovrebbe portarti sulla strada giusta. Il caso peggiore tempo di esecuzione di questo è O (| E | + | V |), con la sola differenza che in p.dfsh, siamo in cache percorsi precedentemente valutati, al contrario di p.dfs, non siamo.

Questo aggiungerà ulteriore sovraccarico di spazio, quindi tenete conto di tale compromesso - salverete molte iterazioni (a seconda del vostro set di dati) al costo di più memoria occupata, non importa quale. Purtroppo, la memorizzazione nella cache non migliora l'ordine di crescita, solo il tempo di funzionamento pratico:

points = set([ 
    (11, 9), 
    (10, 9), 
    (9, 6), 
    (6, 2), 
    (8, 5), 
    (5, 4), 
    (4, 2), 
    (2, 1), 
    (3, 1), 
    (7, 3), 
]) 

class PathFinder(object): 

    def __init__(self, points): 
     self.graph = self._make_graph(points) 
     self.hierarchy = {} 

    def _make_graph(self, points): 
     graph = {} 
     for p in points: 
      p0, p1 = p[0], p[1] 
      less, more = min(p), max(p) 

      if less not in graph: 
       graph[less] = set([more]) 
      else: 
       graph[less].add(more) 

     return graph 

    def dfs(self, start): 
     visited = set() 
     stack = [start] 

     _count = 0 
     while stack: 
      _count += 1 
      vertex = stack.pop() 
      if vertex not in visited: 
       visited.add(vertex) 
       if vertex in self.graph: 
        stack.extend(v for v in self.graph[vertex]) 

     print "Start: {s} | Count: {c} |".format(c=_count, s=start), 
     return visited 

    def dfsh(self, start): 
     visited = set() 
     stack = [start] 

     _count = 0 
     while stack: 
      _count += 1 

      vertex = stack.pop() 
      if vertex not in visited: 
       if vertex in self.hierarchy: 
        visited.update(self.hierarchy[vertex]) 
       else: 
        visited.add(vertex) 
        if vertex in self.graph: 
         stack.extend([v for v in self.graph[vertex]]) 
     self.hierarchy[start] = visited 

     print "Start: {s} | Count: {c} |".format(c=_count, s=start), 
     return visited 

p = PathFinder(points) 
print p.dfsh(1) 
print p.dfsh(2) 
print p.dfsh(9) 
print p.dfsh(6) 
print p.dfsh(2) 
print 
print p.dfs(1) 
print p.dfs(2) 
print p.dfs(9) 
print p.dfs(6) 
print p.dfs(2) 

L'uscita per p.dfsh questo è il seguente:

Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]) 
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11]) 
Start: 9 | Count: 3 | set([9, 10, 11]) 
Start: 6 | Count: 2 | set([9, 10, 11, 6]) 
Start: 2 | Count: 1 | set([2, 4, 5, 6, 8, 9, 10, 11]) 

L'uscita solo per il regolare p.dfs è :

Start: 1 | Count: 11 | set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]) 
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11]) 
Start: 9 | Count: 3 | set([9, 10, 11]) 
Start: 6 | Count: 4 | set([9, 10, 11, 6]) 
Start: 2 | Count: 8 | set([2, 4, 5, 6, 8, 9, 10, 11]) 

Come potete vedere, faccio un DFS, ma tenere traccia di iterazioni precedenti, entro limiti ragionevoli. Non voglio per tenere traccia di tutti i possibili percorsi precedenti, perché se si sta utilizzando questo su un grande insieme di dati, ci sarebbe voluto fino quantità ridicola di memoria.

In uscita, si può vedere il numero di iterazioni per p.dfsh(2) vanno da 8 a 1. Così pure il conteggio per p.dfsh(6) è anche sceso a 2 a causa del calcolo precedente p.dfsh(9).Si tratta di un modesto miglioramento in fase di esecuzione rispetto al DFS standard, in particolare su insiemi di dati di notevoli dimensioni.

Answer 2

Certo, a patto di avere memoria sufficiente per memorizzare tutti i percorsi da ciascun nodo, si può semplicemente utilizzare una modifica diretta del codice che hai ricevuto in questa risposta:

class Reach(object): 
    def __init__(self): 
     self.name = None 
     self.ds = None 
     self.us = set() 
     self._paths = [] 

    def __repr__(self): 
     return "Reach({})".format(self.name) 

    @property 
    def paths(self): 
     if not self._paths: 
      for child in self.us: 
       if child.paths: 
        self._paths.extend([child] + path for path in child.paths) 
       else: 
        self._paths.append([child]) 
     return self._paths 

si badi bene, che per circa 20.000 raggiunge, la memoria richiesta per tale approccio sarà nell'ordine dei gigabyte. La memoria richiesta, presupponendo un albero di portata generalmente bilanciato, è O (n^2), dove n è il numero totale di tratti. Sarebbe 4-8 GiB per 20.000 raggi in base al tuo sistema. Il tempo richiesto è O (1) per qualsiasi nodo, dopo che i percorsi da h[1] sono stati calcolati.