TLE in FCTRL

[nquangtrung]

I'm new to SPOJ, and is practically using this site's problems to practice my Python.
I tried FCTRL and got TLE every time. I don't quite understand the reason, I timed my solution myself and I get a 3-sec result which has included time for input and output, and this problem's time limit is 6s.
Another weird thing is that, I checked the best solution for this problems, there're people who get this solved in almost no time at all (in PYTH, of course). How can that happen? Just by input I lost 1s and another 0.7s for output. Any optimization?
Any idea, about this?

I search the forum and found someone suggested using sys.stdin.readline to reduce input time, but still, TLE.
And I'm quite sure my solution is correct.

[numerix]

Another weird thing is that, I checked the best solution for this problems, there're people who get this solved in almost no time at all (in PYTH, of course). How can that happen?

There is one 0.00 s Python solution because of an error in the judge system. Maybe one day it will be deleted or rejudged.
If you look at the memory consumption, you can see that all fast Python AC submissions for that problem use about 37 MB, which is an indicator
for the use of psyco. Without psyco a fast solution will be able to get AC in less than 2 s.

And I'm quite sure my solution is correct.

Maybe, but doesn't help if it times out.If you post the code here, you may get help.

[nquangtrung]

Many thanks for your reply, after reading it, I take a look at my solution again and came up with a faster solution, and I got accepted.
I'm gonna try another problem right away

[rabbicse]

Hi, I'm new to spoj. I've written almost same code both in c++ and python. But my c++ code is accepted and Python 2.5 code occurs TLE For 'FCTRL' Problem. What the problem in my code. Please anyone help me. Here is my code. In my system it takes less execution time and is less than 2 seconds.

from math import pow
def operation(num):
    res = 0
    if(num > 4):
        i = 1
        while 1:
            x = pow(5, i)
            y = (int)(num / x )
            res += y
            i = i + 1
            if(y < 1):
                break
    else:
        res = 0
    return res
num_of_line = int(raw_input())
while num_of_line > 0:
    inp = int(raw_input())
    res = operation(inp)
    print res
    num_of_line = num_of_line - 1

[numerix]

Indentation is wrong.

[francky]

I work only with Python3,
I think there are few (4 or 5) real* Python3 solutions for FCTRL, but it seems there are some.

(* Now, thanks numerix, I know that there were the Python2.6-psyco-->>Python3.1 "bug")

I have a correct function, and imho quite efficient, but I always got TLE.

So I tested speed on my machine with this : (not a spoil)

testString=str(5**11-5)+"\n" # 9 digits. ;-)
from time import time
st=time()
import sys
for n in range(10**5):
  sys.stdout.write(testString)
sys.stdout.flush()
print(time()-st)

It's 1.9s on my machine, so I can easily imagine TLE on SPOJ. (about ×30? slower)
How is it possible to do FCTRL in python3 knowing that ???
Worse, I can't understand how I solved PRIME1 (more to compute and print !!!) in less a second.
But it seems sven recently did it in 2.55s on spoj in pure python3, isn't it ?

After that, I make a sample size=10⁵ in population(1--10⁹), and test my function:

from random import *
entree = list(map(str, sample(range(1, 10**9), 10**5)))
def Z(n):
  " n is a string"
  # (...) would be a spoil
  return result
from time import time
st=time()
import sys
#_ = sys.stdin.readline()
#for n in sys.stdin:
for n in entree:
  sys.stdout.write(Z(n))
print(time()-st)

My simulation is done in 2.2s, quite good for me.

So I think the problem is in my read/write on I/O,
is it true or is there an other reason ?

Many thanks.

[numerix]

But it seems sven recently did it in 2.55s on spoj in pure python3, isn't it ?

True. I guess he used the same approach as he used for his veeeery fast Python 2.5 submission: 0.14 s without psyco(!) is unbelievable.
But you can get a Python 3.1 solution AC within 5 s without a sophisticated algorithm. My AC solution with approx. 4.7 s is simple and straight forward with 10 lines of code. Nothing special. But, indeed, you have to choose the right way of I/O. Just do some more experimenting on that ...

[francky]

@ numerix :
Thanks, but where can I learn how to read/write very efficiently in Python3 ?
I ever read all python threads here and links given for I/O.

I tried :

import sys
testString=(str(5**11-5)+"\n")*(10**5)
sys.stdout.write(testString)
sys.stdout.flush()

and

import sys
testString=(str(5**11-5)+"\n")
for n in range(10**5):
  sys.stdout.write(testString)
sys.stdout.flush()

both seems slow at 1.9s at home.

I also tried avoid the for loop, with a map

list(map( lambda x:sys.stdout.write(str(5**11-5)+"\n"), range(10**5)))

Result : the same.

Please tell me where can I learn that.
Do I have to put my hands in the darkness of encoding, or rather custom buffering, or both ?
Many thanks.
Edit : with custom buffering, I got 10% faster, 'latin-1' encoding : 0% faster. In which way should I study.

[numerix]

1.9 s runtime for the code shown above? I cannot reproduce that. On my machine it takes < 0.1 s.

What I mean with "experimenting" is:
Produce a (larger) file with random data and then:
- write a program to just read it
- read and write it
- read it, convert it into numbers
- read it, convert it into numbers and write it
- try different methods to split input data into pieces
- try different methods to prepare output data for output
Find the bottlenecks. Be creative and find ways to make them wider. That's the way I did it.

As there seem to be only few people interested in getting Python code really fast, you won't find much inforrmation about that in the web. If people want it fast, they switch the language ...

[francky]

1.9 s runtime for the code shown above? I cannot reproduce that. On my machine it takes < 0.1 s.

I use :
Python 3.2 (r32:88445, Mar 25 2011, 19:56:22)
[GCC 4.5.2] on linux2

My computer is quite recent/decent : ×2 AMD Athlon II 3GHz. 4GB of RAM.

instruction : time python3 ./FCTRL.py

(... long result ... 10⁵ lines)
1.7305917739868164
real 0m2.009s
user 0m0.410s
sys 0m0.120s

How could it takes 1.9s vs <0.1s ?

[numerix]

Ah, I see. What you are measuring is the time needed to print all the output to the terminal. That's not relevant for SPOJ timing.
Just redirect output into a file to get the relevant runtime:

time python3 test.py > tmp.txt
real	0m0.047s
user	0m0.050s
sys	0m0.000s

[francky]

Many thanks, numerix.
My problem was not really I/O, my Z function was very bad, I found a better straight way ; divmod was too slow and unnecessary in fact. With your guidance I managed interesting tests.

I now have got a good chono in Python3 ; my new Z function is great.
With the memory print (5.7MB), it seems that there are only 7 real Python3 submissions.

Here my presentation for I/O, the function Z is not given here. (watch your MP )
Was it a good way in your opinion ?

def Z(n):
  # stuff
  return Zn
from sys import stdin, stdout
def main():
  stdin.readline()
  stdout.write("\n".join(map(str, map(Z, map(int, stdin)))))
  stdout.flush()
main()