Найти - Пользователи
Полная версия: Проблемы с рекурсией
Начало » Python для новичков » Проблемы с рекурсией
1 2
mtt
Просто в поиск просьба не посылать, я искал

Суть: есть дерево, 50к вершин, нужно от вывода предков относительно корня r1 перейти к выводу предков r2. Задача простая, но я решил написать поиск в глубину, и с ним проблемы.
from sys import stdout
import sys
def dfs(x,parent):
res[x]=parent
for i in a[x]:
if res[i]==-1:
dfs(i,x)
#print (x,parent)
return

sys.setrecursionlimit(50000)

f=open('C://input.txt','r')
#(n,r1,r2)=map(int,raw_input().split())
#parent=map(int,raw_input().split())

(n,r1,r2)=map(int,str(f.readline()).split())
parent=map(int,str(f.readline()).split())

a=map(apply,[list]*(n+1))
for i in xrange(n-1):
j=i+1
if r1<=j:
j+=1
#(Это список смежности)
a[j]+=[parent[i]]
a[parent[i]]+=[j]

res=[-1]*(n+1)
dfs(r2,0)
for i in res:
if i>0:
stdout.write(str(i)+' ')
Вчера программа погибала на моем компьютере с ошибкой что-то вроде memory limit, теперь просто молча выключается после посещения около 19 тысяч вершин из 50, так ничего и не выведя.
Забыл добавить, на паскале это отлично работает.
mtt
Ладно, переформулирую проще: почему этот код падает без ошибки, выводя в консоль последнее число 9567 и как это исправить?(я имею в виду, управлять кол-вом итераций до падения)
import sys
def rec(count):
print count
rec(count+1)

sys.setrecursionlimit(30000)
rec(1)
Zubchick
попробуй увеличить глубину рекурсии или переписать алгоритм итерационно :)
http://docs.python.org/library/sys.html#sys.setrecursionlimit
truporez
Пробовал запустить на stackless python 2.6.5, тот отрабатывает до 30000.
А в обычном видимо стек ограничен неким значением не позволяющим выполнить такое(>9567) количество вызовов. Возможно если сократить количество передаваемых параметров(count сделать глобальной), количество итераций увеличится.
mtt
Zubchick
попробуй увеличить глубину рекурсии или переписать алгоритм итерационно smile
Спасибо конечно, но я уже увеличил глубину рекурсии, а итерационное переписывание всех алгоритмов не выход.

truporez
А в обычном видимо стек ограничен неким значением не позволяющим выполнить такое(>9567) количество вызовов. Возможно если сократить количество передаваемых параметров(count сделать глобальной), количество итераций увеличится.
А можно сам стек увеличить? Что-то это не гуглится, только модуль никсовый нашел(resource)
Андрей Светлов
mtt, а какая у вас операционка? Помимо питоновского стека есть еще и стек потока. На него тоже существует ограничение.
На моей убунте ваш примерчик честно отработал до конца.
mtt
Windows xp, python idle 2.7, скачанный c http://www.python.org/download/ . Проверял на другой машине с виндой, то же самое.
Андрей Светлов
С Виндой - да, печально. Стек в 2 мегабайта.
Чинится, но не очень легко. Microsoft Visual Studio 2008 есть?
mtt
Установлю, если нужно.
o7412369815963
Андрей Светлов
mtt, а какая у вас операционка? Помимо питоновского стека есть еще и стек потока. На него тоже существует ограничение.
На моей убунте ваш примерчик честно отработал до конца.
linux 32bit, python 2.6.6, тоже отработал до конца
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB