beginner1010's blog

A Memory-efficient Python Implementation Needed
By beginner1010, history, 5 years ago, In English

Hello,

I have recently started learning Python. I tried F. Vus the Cossack and a Graph from Codeforces Round #571 (Div. 2). To solve this problem, first I wrote a recursive function to find an Euler circuit, and I got MLE (Memory Limit Exceeded). Using an iterative method (with stack) did not help me either.

You may find the Python implementation here in 59832390

I would appreciate if you give me some hints to make the implementation more efficient in terms of memory. Of course, any hint to make it faster is welcomed.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

I implemented the same solution in Java. It gets TLE: 59876165.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hmm so while I agree the ML and TL is pretty tight, this problem is definitely possible in python using PyPy.

Here is my first try with PyPy2, it got AC.

Here are two solutions using the header that I normally use

I think the main thing that takes down the memory cost in python is using pure integer lists, this is because PyPy has a special strategy for pure integer lists, making it only use 4 bytes per integer. Note that this is not true for tuples, nor list of tuples, nor lists containing big integers.

→ Reply