BFS requires O(b^d) memory, whereas IDDFS is known to run in only O(bd) memory. However, when I profile these two implementations they turn out to use exactly the same amount of RAM - what am I missing?
I'm using a Tree class with a branching factor or 10 to run the tests:
class Tree(object):
def __init__(self, value):
self.key = value
self.children = [ ]
def insert(self, value):
if len(self.children) == 0:
self.children = [ Tree(value) for x in range(10) ]
else:
for ch in self.children:
ch.insert(value)
My implementation of iddfs:
def iddfs(t):
for i in range(0,8):
printGivenLevel(t, i)
def printGivenLevel(t, level):
if not t:
return
if level == 1:
pass
elif level > 1:
for ch in t.children:
printGivenLevel(ch, level - 1)
BFS is
def bfs(t):
currLevel = [t]
nextLevel = []
while currLevel:
for node in currLevel:
if node:
nextLevel.extend([ x for x in node.children ])
currLevel = nextLevel
nextLevel = []
The code is not really doing anything, just looping through the whole tree. I'm using https://github.com/fabianp/memory_profiler to profile the code.
IDDFS's memory benefits only apply to an implicit tree, where nodes are generated as they're reached and discarded soon after. With a tree represented completely in memory, the tree itself already takes O(b^d) memory, and the memory required for either IDDFS or BFS is minor in comparison.