Can you see any immediately changes I can do to increase speed and optimization in the script below?
We are suppose to write a script which implements dfs/bfs searches to find "ratatosk". Input is which function to use (dfs or bfs), number of nodes in the tree, root node, which node "ratatosk" is in and the rest of the node numbers.
from sys import stdin
from collections import deque
True = 1
False = 0
class Node:
barn = None
ratatosk = None
nesteBarn = None # bare til bruk i DFS
def __init__(self):
self.barn = []
self.ratatosk = False
self.nesteBarn = 0
def dfs(rot):
stack = [ [rot, 0] ]
while True:
current = stack.pop()
if current[0].ratatosk == True:
return current[1]
if len(current[0].barn) > 0 :
for unge in current[0].barn:
stack.append([unge, current[1]+1])
return False
def bfs(rot):
a = 0;
onthislevel = 1
level = 0
nextlevel = 0
queue = deque([rot])
app = queue.append
while True:
current = queue.popleft()
onthislevel=onthislevel-1
if current.ratatosk == True:
return level
a = len(current.barn)
if a > 0 :
nextlevel = a+nextlevel
map(app, current.barn)
if onthislevel == 0:
level+=1
onthislevel = nextlevel
nextlevel = 0
return 1
funksjon = stdin.readline().strip()
antall_noder = int(stdin.readline())
noder = []
nodeappend = noder.append;
for i in range(antall_noder):
nodeappend(Node())
start_node = noder[int(stdin.readline())]
ratatosk_node = noder[int(stdin.readline())]
ratatosk_node.ratatosk = True
for linje in stdin:
tall = linje.split()
temp_node = noder[int(tall.pop(0))]
temp_node_append = temp_node.barn.append;
for barn_nr in tall:
temp_node_append(noder[int(barn_nr)])
if funksjon == 'dfs':
print dfs(start_node)
elif funksjon == 'bfs':
print bfs(start_node)
elif funksjon == 'velg':
print bfs(start_node)