Python :- Exit code is -1073741571

Блог пользователя TheNoOneCoder

Автор TheNoOneCoder, история, 5 лет назад, По-английски

I was doing this problem in python. I am receiving Runtime error on test 3 with exit code -1073741571. I am not able to understand the fault in my code. Any help is greatly appreciated.

Link to my submission .

The main part of the code is below:


cnt = 1
d = defaultdict(lambda:0)
travesal = []
subtreesize = defaultdict(lambda:0)

def dfs(node,parent):
    global adj,cnt
    travesal.append(node)
    ans = 1
    for child in adj[node]:
        if child==parent:
            continue
        d[child]=cnt
        cnt+=1
        ans+=dfs(child,node)
    subtreesize[node]=ans
    return ans

n,q = li()
p = li()
adj = [[] for i in range(200002)]
for i in range(len(p)):
    adj[i+1].append(p[i]-1)
    # print(p[i]-1)
    adj[p[i]-1].append(i+1)
dfs(0,-1)
for i in range(len(travesal)):
    travesal[i]+=1
for i in range(q):
    u,k = li()
    u-=1
    dis = d[u]
    x = dis+k-1
    # print("x",x)
    if x>=len(travesal) or subtreesize[u]<k:
        print(-1)
    else:
        print(travesal[x])

#python, #pypy3, #runtime, *1600, #help

TheNoOneCoder
5 лет назад
11

Комментарии (11)

Написать комментарий?

TheNoOneCoder

5 лет назад, скрыть # |

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

→ Ответить

pajenegod

5 лет назад, скрыть # |

+22

You are getting stack overflow.

The problem here is that sys.setrecursionlimit(10000) does not directly mean you can actually reach a recursion depth of 10000. CPython and PyPy both internally use the standard stack for recursion, which by default is pretty tiny. C++ would have the same problem too, but it doesn't because of the compile flag --stack=268435456.

So how do you get around this in Python? A while back made this bootstrapper to completely get around any issues with deep recursion. The way it works is kind of weird but it is pretty easy to use. Here is your submission getting AC using it 118526672.

→ Ответить

TheNoOneCoder

5 лет назад, скрыть # ^ |

Thanks a lot brother

→ Ответить

notTehlka

5 лет назад, скрыть # ^ |

Hi pajenegod, can you please tell me how to remove runtime error from my Codejam Round 2 C problem. My code link. My code also uses recursion.

→ Ответить

pajenegod

5 лет назад, скрыть # ^ |

← Rev. 2 →

+18

Here is how to use the bootstrapper in your case

def find(l, r, val, inde):
    if l >= r:
        return 1
    x = inde[val][br(inde[val],r) - 1]
    return comb(r-l,x-l) * find(l,x-1,val,inde) * find(x+1,r,val+1,inde) % mod

switch it to

@bootstrap
def find(l, r, val, inde):
    if l >= r:
        yield 1
    x = inde[val][br(inde[val],r) - 1]
    yield comb(r-l,x-l) * (yield find(l,x-1,val,inde)) * (yield find(x+1,r,val+1,inde)) % mod

→ Ответить

notTehlka

5 лет назад, скрыть # ^ |

Thanks man, you are a python GOD

→ Ответить

HETRAKESHFADIA

5 лет назад, скрыть # ^ |

← Rev. 2 →

Dear sir pajenegod,

I have a question, Which one is faster recursion code vs iterative code(bootstrap on that recursive code)

I ran two codes in pypy3

First recursive code: recursive It takes around 0.04 seconds every time I run

Second iterative code of the same recursive code(using bootstrap): iterative It takes around 0.4 seconds every time I run

The iterative code using bootstrap is slowing 10 times. So my question is does the bootstrap slow down the code. Or I am making some mistake.

Also please tell us how to fasten bootstrap. The bootstrap is very fine library for large recursions. So I wanted to know how to optimise it.

Thank you in advance for spending your precious time.

→ Ответить

pajenegod

5 лет назад, скрыть # ^ |

The bootstrapper definitely slow things down. I've never suggested that it runs fast compared to native recursion. The role of the bootstrapper is to get around the issue of deep recursion. It also uses far less memory compared to native recursion.

However, the overhead of using the bootstrapper is still surprisingly small. When I first designed it I thought it was going to be useless because of the overhead. But to my surprise it actually works pretty well.

There is always going to be a trade off between usability and overhead. If you really want to lower the overhead, you can for example try this:

Bootstrapper (without decorator)

from types import GeneratorType

def bootstrap(to, stack=[]):
    while True:
        if type(to) is GeneratorType:
            stack.append(to)
            to = next(to)
        else:
            stack.pop()
            if not stack:
                break
            to = stack[-1].send(to)
    return to

def fun(n):
    if n == 0:
        yield
    yield fun(n-1)
    yield

for i in range(10000):
    bootstrap(fun(400))

Another thing is that if you are ok with even more overhead, then in Python 3 you can do this:

Bootstrapper (with returns)

def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = stack.append(f(*args, **kwargs))
            while True:
                try:
                    to = stack.append(stack[-1].send(to))
                except StopIteration as e:
                    stack.pop()
                    to = e.value
                    if not stack:
                        break
            return to
 
    return wrappedfunc
 
@bootstrap
def fun(n):
    if n == 0:
        return 1
    return (yield fun(n-1)) + 1
 
for i in range(10000):
    fun(400)

→ Ответить

vermakunal088

5 лет назад, скрыть # ^ |

Hi pajenegod can you please tell me how to use bootstrapper in this solution since it does not have a return statement in my recursive function. Thanks in advance.

→ Ответить

pajenegod

5 лет назад, скрыть # ^ |

There are a lot of examples in this blog already. You should be able to learn from that. But here is your code bootstrapped 119799338.

About having no return. The way Python works is that all functions have a return value. If you don't explicitly set a return value, then the function returns None. So to get the same behaviour with the bootstrapper you need to add yield None (or just yield) on the last line in the function.

→ Ответить

HETRAKESHFADIA

4 года назад, скрыть # ^ |

← Rev. 2 →

Thank you very much for the suggestion.

I have one more question. I tried to do problem C of today contest using recursion. Using lru_cache it got runtime error due to python stack size as seen submission_runtime_error_stack_overflow

I also tried to do using bootstrap method as seen here in submission But it got tled. How should I do only using recursion and python?

Update: It got AC here but it will probably get hacked. Thanks in advance

→ Ответить