Utilizzo memoria in ricorsiva rispetto a un grafico iterativo trasversale

Question

Ho esaminato alcuni strumenti comuni come Heapy per misurare la quantità di memoria utilizzata da ciascuna tecnica di attraversamento ma non so se mi stanno dando i risultati corretti. Ecco un codice per dare il contesto.

Il codice misura semplicemente il numero di nodi univoci in un grafico. Due tecniche di attraversamento fornite vale a dire. count_bfs e count_dfs

import sys 
from guppy import hpy 
class Graph: 
    def __init__(self, key): 
     self.key = key  #unique id for a vertex 
     self.connections = [] 
     self.visited = False 

def count_bfs(start): 
    parents = [start] 
    children = [] 
    count = 0 
    while parents: 
     for ind in parents: 
      if not ind.visited: 
       count += 1 
       ind.visited = True 
       for child in ind.connections: 
         children.append(child) 

     parents = children 
     children = [] 
    return count 

def count_dfs(start): 
    if not start.visited: 
      start.visited = True 
    else: 
      return 0 

    n = 1 
    for connection in start.connections: 
     n += count_dfs(connection) 
    return n 


def construct(file, s=1): 
    """Constructs a Graph using the adjacency matrix given in the file 

    :param file: path to the file with the matrix 
    :param s: starting node key. Defaults to 1 

    :return start vertex of the graph 
    """ 
    d = {} 
    f = open(file,'rU') 
    size = int(f.readline()) 
    for x in xrange(1,size+1): 
     d[x] = Graph(x) 
    start = d[s] 
    for i in xrange(0,size): 
      l = map(lambda x: int(x), f.readline().split()) 
      node = l[0] 
      for child in l[1:]: 
       d[node].connections.append(d[child]) 
    return start 


if __name__ == "__main__": 
    s = construct(sys.argv[1]) 
    #h = hpy() 
    print(count_bfs(s)) 
    #print h.heap() 
    s = construct(sys.argv[1]) 
    #h = hpy() 
    print(count_dfs(s)) 
    #print h.heap() 

Voglio sapere da quale fattore è l'utilizzo della memoria totale diverso nelle due tecniche traversal viz. count_dfs e count_bfs? Si potrebbe avere l'intuizione che dfs potrebbe essere costoso come viene creato un nuovo stack per ogni chiamata di funzione. Come si possono misurare le allocazioni di memoria totali in ciascuna tecnica di attraversamento?
Le dichiarazioni (commentate) hpy indicano la misura desiderata?

Esempio di file con collegamenti:

4 
1 2 3 
2 1 3 
3 4 
4 

Answer 1

Trattandosi di una domanda python, potrebbe essere più importante la quantità di spazio dello stack rispetto alla quantità di memoria totale. Cpython ha un limite inferiore di 1000 frame perché condivide lo stack di chiamate con lo stack di chiamate c, che a sua volta è limitato all'ordine di un megabyte nella maggior parte dei casi. Per questo motivo dovresti quasi * preferire sempre le soluzioni iterative a quelle ricorsive quando la profondità della ricorsione è illimitata.

_{* altre implementazioni di python potrebbero non avere questa restrizione. Le varianti senza stack di cpython e pypy hanno questa proprietà esatta}

Answer 2

E 'difficile misurare esattamente la quantità di memoria utilizzata in quanto i sistemi variano nel modo in cui implementare stack frame. In generale, gli algoritmi ricorsivi utilizzano molta più memoria degli algoritmi iterativi, perché ogni frame dello stack deve memorizzare lo stato delle sue variabili ogni volta che si verifica una nuova chiamata di funzione. Considerare la differenza tra soluzioni di programmazione dinamica e soluzioni ricorsive. Il runtime è molto più veloce su un'implementazione iterativa di un algoritmo rispetto a uno ricorsivo.

Se davvero si deve sapere quanta memoria utilizza il codice, caricare il software in un debugger come OllyDbg (http://www.ollydbg.de/) e contare i byte. Buona programmazione!

Answer 3

Per il tuo problema specifico, non so se ci sarà una soluzione facile. Questo perché, l'utilizzo della memoria di picco di un attraversamento grafico dipende dai dettagli del grafico stesso.

Per un deep-first traversal, l'utilizzo più grande arriverà quando l'algoritmo sarà arrivato alla profondità più profonda. Nel grafico di esempio, attraverserà 1->2->3->4 e creerà una cornice di stack per ogni livello. Quindi mentre è a 4 ha assegnato più memoria.

Per l'attraversamento in ampiezza, la memoria utilizzata sarà proporzionale al numero di nodi a ciascuna profondità più il numero di nodi figlio alla profondità successiva. Tali valori sono memorizzati in elenchi, che sono probabilmente più efficienti dei frame di stack. Nell'esempio, poiché il primo nodo è connesso a tutti gli altri, avviene immediatamente durante il primo passo [1]->[2,3,4].

Sono sicuro che ci sono alcuni grafici che faranno molto meglio con una ricerca o l'altra.

Ad esempio, immagina un grafico simile a un elenco collegato, con tutti i vertici in un'unica lunga catena. L'attraversamento in profondità avrà un utilizzo di memoria di picco molto elevato, poiché si ripeterà lungo tutta la catena, allocando una cornice di stack per ogni livello. L'attraversamento in ampiezza utilizzerà molta meno memoria, dal momento che avrà un solo vertice con un solo bambino da tenere traccia di ogni passaggio.

Ora, contrasto quello con un grafico che è un albero di profondità 2. Cioè, c'è un singolo elemento radice che è collegato a un numero elevato di bambini, nessuno dei quali è connesso l'uno all'altro. Il primo attraversamento di profondità non utilizzerà molta memoria in un dato momento, in quanto avrà solo bisogno di attraversare due nodi prima di eseguire il backup e provare un altro ramo. L'attraversamento in profondità, d'altra parte, metterà immediatamente in memoria tutti i nodi figli, il che per un grande albero potrebbe essere problematico.

Il codice di profilazione corrente non troverà l'utilizzo di memoria di picco desiderato, poiché trova la memoria utilizzata dagli oggetti nell'heap nel momento in cui si chiama heap. È probabile che sia lo stesso prima e dopo i tuoi attraversamenti. Invece, dovrai inserire il codice di profilazione nelle stesse funzioni di attraversamento. Non riesco a trovare un pacchetto pre-costruito di guppy di provare io stesso, ma penso che questo codice non testato funzionerà:

from guppy import hpy 

def count_bfs(start): 
    hp = hpy() 
    base_mem = hpy.heap().size 
    max_mem = 0 
    parents = [start] 
    children = [] 
    count = 0 
    while parents: 
     for ind in parents: 
      if not ind.visited: 
       count += 1 
       ind.visited = True 
       for child in ind.connections: 
         children.append(child) 
     mem = hpy.heap().size - base_mem 
     if mem > max_mem: 
      max_mem = mem 
     parents = children 
     children = [] 
    return count, max_mem 

def count_dfs(start, hp=hpy(), base_mem=None): 
    if base_mem is None: 
     base_mem = hp.heap().size 

    if not start.visited: 
      start.visited = True 
    else: 
      return 0, hp.heap().size - base_mem 

    n = 1 
    max_mem = 0 
    for connection in start.connections: 
     c, mem = count_dfs(connection, base_mem) 
     if mem > max_mem: 
      max_mem = mem 
     n += c 
    return n, max_mem 

Entrambe le funzioni di attraversamento ora restituiscono una tupla (count, max-memory-used). Puoi provarli su una varietà di grafici per vedere quali sono le differenze.

Answer 4

Dei due, depth-first utilizza meno memoria se la maggior parte degli attraversamenti finisce per colpire la maggior parte del grafico.

Larghezza-prima può essere migliore quando l'obiettivo si trova vicino al nodo di partenza o quando il numero di nodi non aumenta molto rapidamente in modo che gli array di genitori/figli nel codice rimangano piccoli (ad esempio, un'altra risposta menziona l'elenco collegato come peggiore per DFS).

Se il grafico si sta cercando è dati spaziali, o ha ciò che è noto come un "euristica ammissibile," A * è un altro algoritmo che è abbastanza buono: http://en.wikipedia.org/wiki/A_star

Tuttavia, l'ottimizzazione prematura è la radice di tutti i mali . Guarda i dati reali che vuoi utilizzare; se rientra in una quantità ragionevole di memoria e la ricerca viene eseguita in un tempo ragionevole, non importa quale algoritmo si utilizza. NB, ciò che è "ragionevole" dipende dall'applicazione utilizzata e dalla quantità di risorse sull'hardware che lo eseguirà.

Answer 5

Per entrambi gli ordini di ricerca implementati in modo iterativo con la struttura dati standard che lo descrive (coda per BFS, stack per DFS), posso costruire un grafico che utilizza banalmente la memoria O(n). Per BFS, è un n-star, e per DFS è una n-catena. Non credo che nessuno dei due possa essere implementato nel caso generale per fare meglio di così, così da dare anche un limite inferiore a Omega(n) sull'utilizzo massimo della memoria. Quindi, con implementazioni efficienti di ciascuno, dovrebbe generalmente essere un lavaggio.

Ora, se i grafici di input hanno alcune caratteristiche che li spingono più verso uno di questi estremi o l'altro, ciò potrebbe informare la decisione su quale usare nella pratica.