H4wk3ye's blog

By H4wk3ye, history, 5 years ago, In English

So I was trying to solve few graph questions and during dfs if the graph has nodes and edges of magnitude ~10**5 python was giving run time or sigsev error even if the recursion limit is set explicitly using sys.setrecursionlimit(10**6). After googling about the stack size issues in pyhton I came across a Stackoverflow blog.

The second answer using the resource module was helpful

    import resource, sys
    resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
    sys.setrecursionlimit(10**6)

and I was able to avoid the recursion depth issue on this question on hackerearth.

But the problem is resource module is not available on Codeforces. Even though its available on Codechef as well as hackerearth.

So I tried another module threading

    sys.setrecursionlimit(10**6)
    threading.stack_size(10**8)
    t = threading.Thread(target=main)
    t.start()
    t.join()

and its available here in codeforces as well but the issue is the memory consumption is huge if we use threading module and it sometimes even causes memory lmiit exceeded error.

The question I mentioned above on articulation point and bridges.

Solution using Resource module.

Solution using Threading module.

You can see the second test case threw memory limit exceeded. And every test case has huge memory consumption.

So are the Codeforces machines running a windows system as resource module is not avilable for windows according to an old comment on the stackoverflow blow.

And if you are python programmer what else do you use for programs with huge recursion depth.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by H4wk3ye (previous revision, new revision, compare).

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So in general in python, you can't really do recursion well. The main problem is that there exists a built-in limit in how deep you can go. Depending on exactly what python version you are running there are ways to get around this limit, but I've had problems using this in general, especially with pypy.

So what I've come up with is a way to deep recursion in python without actually doing recursion. The method is based on generators in which you use "yield" to be able to basically do something very similar to recursion, but without ever doing the recursion.

The only problem is that this is somewhat slow, but it should be possible to do > 10^6 recursive calls in < 1 s on cf, so not completely unusably slow, but still pretty slow.

This is Bootstrap recursion. if you want the code...I can provide u.