Python'da yol bulma verimliliği

Question

Bir dendritik akış ağında belirli bir erişimin akış yönündeki tüm yolları bulabilen bir kod yazdım.

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

ebeveyn-çocuk çiftlerinin bir dizi olarak: Aşağıdakilerin ağı temsil eder, bir örnek olarak,

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

bu, örneğin bir düğüm üst tüm yolları döndürür:

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)]] 

Bu kod aşağıda yer almaktadır.

Soruma şudur: Bunu, herhangi bir erişimin milyonlarca yolu olabileceği çok büyük (örneğin, New England) bir bölgedeki her erişime uygulıyorum. Muhtemelen bu uzun bir operasyon olmaktan kaçınmanın bir yolu yoktur, fakat bu operasyonu gerçekleştirmek için pithonik bir yol var mıdır, öyle ki her yolla yepyeni yollar üretilmiyor mu? Örneğin

ben 2'de tüm yolların retracing olmadan (1, h) get_paths (s, 2) yukarı 2 ila tüm yollar bulunmuştur ve, daha sonra çalışabilir get_paths çalıştırmak olur?

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) 

DÜZENLEME: Birkaç hafta önce bir ağda "TÜM" akıntıya karşı ulaşır bulma konusunda benzer bir soru sordu ve çok hızlı oldu mükemmel bir cevap aldı: Fark ettim

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]) 

def upstream(): Bu kodun bir kısmı, sıralı sırada düğümleri ekler, ancak yinelemeli bir işlev olduğundan, bunları tek bir listeye eklemek için iyi bir yol bulamıyorum. Belki de siparişi koruyan bu kodu değiştirmenin bir yolu vardır.

Answer 1

Evet, bunu yapabilirsiniz. Kısıtlamalarınızın ne olduğundan tam olarak emin değilim; Ancak, bu sizi doğru yolda bulmalı. Bunun en kötü durum süresi O (| E | + | V |) olup, p.dfsh'daki tek fark, p.dfs'un aksine daha önce değerlendirilen yolları önbelleğe alıyoruz.

Bu, ek alan ek yükü ekleyeceğinden, bu trajmanın farkında olun - ne kadar olursa olsun, daha fazla hafızanın pahalı olduğu bir çok yinelemeyi (veri kümenize bağlı olarak) kaydedeceksiniz.

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]) 

sadece düzenli p.dfs için çıktıdır: p.dfsh bu çıktısı şöyledir

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) 

edilir

: Maalesef, önbelleğe alma büyüme düzeni, sadece pratik çalışma süresini iyileştirmez :

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]) 

Gördüğünüz gibi, bir DFS yapıyorum, ancak önceki yinelemeleri takip etmem gerekçesiyle. Tüm olası önceki yolları takip etmek istemiyorum çünkü eğer büyük bir veri setinde kullanıyorsanız, bu çok fazla miktarda bellek alacaktır. p.dfsh(2) 1. 8'den gitmek Ve aynı şekilde p.dfsh(6) için sayım nedeniyle de p.dfsh(9) önceki hesaplama 2'ye düşürülür için

çıktısında, yineleme sayısını görebilirsiniz.Bu, özellikle önemli ölçüde büyük veri kümeleri üzerinde standart DFS'den mütevazi bir çalışma zamanı iyileştirmesidir.

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 

Akıl buna sen:

Answer 2

Tabii, her düğümden tüm yolları depolamak için yeterli belleğe sahip varsayarak, sadece o cevap aldık kod basit bir değişiklik kullanabilirsiniz Yaklaşık 20.000 erişim, bu yaklaşım için gereken bellek gigabayt sırasına göre olacaktır. Genel olarak dengeli bir erişim ağacı olduğu varsayılarak gerekli bellek, O (n^2), burada n toplam erişim sayısıdır. Sisteminize bağlı olarak 20.000 erişim için 4-8 GiB olacaktır. Gerekli süre, h[1] yollarından sonra O (1) hesaplanmıştır.