में मेमोरी उपयोग मैंने कुछ सामान्य उपकरण जैसे Heapy को मापने के लिए देखा है ताकि प्रत्येक ट्रैवर्सल तकनीक द्वारा कितनी मेमोरी का उपयोग किया जा सके लेकिन मुझे नहीं पता कि वे मुझे सही परिणाम दे रहे हैं या नहीं। संदर्भ देने के लिए यहां कुछ कोड दिया गया है।रिकर्सिव बनाम एक पुनरावर्तक ग्राफ ट्रैवर्सल
कोड आसानी से ग्राफ में अद्वितीय नोड्स की संख्या को मापता है। प्रदान की गई दो ट्रैवर्सल तकनीकें जैसे। count_bfs और 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()
मैं क्या कारक कुल स्मृति उपयोग दो ट्रेवर्सल तकनीक अर्थात् में अलग है द्वारा जानना चाहते हैं। count_dfs और count_bfs? किसी के पास अंतर्ज्ञान हो सकता है कि dfs महंगा हो सकता है क्योंकि प्रत्येक फ़ंक्शन कॉल के लिए एक नया स्टैक बनाया गया है। प्रत्येक ट्रैवर्सल तकनीक में कुल मेमोरी आवंटन कैसे मापा जा सकता है?
क्या (टिप्पणी की गई) hpy कथन वांछित उपाय देते हैं?
नमूना फ़ाइल:
4
1 2 3
2 1 3
3 4
4
क्या आप चरम स्मृति उपयोग की तलाश में हैं? क्योंकि दोनों एल्गोरिदम के लिए, ग्राफ का उपयोग होने के कारण उपयोग की जाने वाली राशि ऊपर और नीचे जायेगी। जिसकी बड़ी चोटी ग्राफ के विवरण पर निर्भर हो सकती है। – Blckknght
@Blckknght मैं कुल मेमोरी उपयोग की तलाश में हूं। एक संभावित एवेन्यू अलग-अलग ज्ञापन दिखाते हुए आंकड़ों का एक सेट हो सकता है। प्रत्येक ट्रैवर्सल तकनीक पर लागू 'एन' ग्राफ के लिए आवंटन। – ajmartin