Python-сообщество

Просто в поиск просьба не посылать, я искал

Суть: есть дерево, 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)+' ')

Отредактировано (Окт. 13, 2010 06:57:16)

Ладно, переформулирую проще: почему этот код падает без ошибки, выводя в консоль последнее число 9567 и как это исправить?(я имею в виду, управлять кол-вом итераций до падения)

import sys
def rec(count):
  print count
  rec(count+1)

sys.setrecursionlimit(30000)
rec(1)

Отредактировано (Окт. 13, 2010 22:07:53)

попробуй увеличить глубину рекурсии или переписать алгоритм итерационно :)
http://docs.python.org/library/sys.html#sys.setrecursionlimit

Пробовал запустить на stackless python 2.6.5, тот отрабатывает до 30000.
А в обычном видимо стек ограничен неким значением не позволяющим выполнить такое(>9567) количество вызовов. Возможно если сократить количество передаваемых параметров(count сделать глобальной), количество итераций увеличится.

Отредактировано (Окт. 13, 2010 22:51:41)

Zubchick
попробуй увеличить глубину рекурсии или переписать алгоритм итерационно smile

truporez
А в обычном видимо стек ограничен неким значением не позволяющим выполнить такое(>9567) количество вызовов. Возможно если сократить количество передаваемых параметров(count сделать глобальной), количество итераций увеличится.

mtt, а какая у вас операционка? Помимо питоновского стека есть еще и стек потока. На него тоже существует ограничение.
На моей убунте ваш примерчик честно отработал до конца.

Windows xp, python idle 2.7, скачанный c http://www.python.org/download/ . Проверял на другой машине с виндой, то же самое.

С Виндой - да, печально. Стек в 2 мегабайта.
Чинится, но не очень легко. Microsoft Visual Studio 2008 есть?

Отредактировано (Окт. 14, 2010 07:33:03)

Установлю, если нужно.

Андрей Светлов
mtt, а какая у вас операционка? Помимо питоновского стека есть еще и стек потока. На него тоже существует ограничение.
На моей убунте ваш примерчик честно отработал до конца.