[PYTHON] TLE seemed to be scary depending on how the input was received

Yes. codeforces http://codeforces.com/contest/373/problem/C

Original tweet https://twitter.com/cocodrips/statuses/412848727175331840 Published Gist https://gist.github.com/cocodrips/8001370

Please refer to the above publication for the full text of the original code.

originally


if __name__ == "__main__":
    num = map(int, raw_input().split())
    num=num[0]
    data = []
    for _ in range(num):
        next=map(int, raw_input().split())
        data.append(next[0])
    solve(data)

my proposal


if __name__ == "__main__":
    num = int(raw_input())
    data = []
    for x in range(num):
        data.append(int(raw_input()))
    solve(data)

For the test data, copy the sample case and prepare 1 line + 200,000 lines of data. The first line is the number of lines to be given, and the subsequent 200,000 lines are the data copied to the texto.

Ichio's CPU and memory Processor 2.5 GHz Intel Core i5 Memory 16 GB 1333 MHz DDR3

Time measurement

time


import=time
start=time.clock()
##Other execution part
end=time.clock()
t=end-start

How you commented


if __name__ == "__main__":
    num = int(raw_input())
    data = (int(raw_input()) for _ in xrange(num))
    solve(data)

Run 3 times and list the middle value in the table below

Part 1: Original data Part 2: num = int (raw_input ()) Only the way to receive the first line is changed Part 3: Change only how to receive data.append (int (raw_input ())) while turning with for Part 4: Both changed Part 5: How you commented

pattern processing time
Part 1 0.990795 seconds
Part 2 0.995793 seconds
Part 3 0.661866 seconds
Part 4 0.677707 seconds
Part 5 0.647318 seconds

The time difference was significant this time because of how to receive the second and subsequent lines ...

The test case in my first line was 200,000, and I received only 6 digits per line from 500000, which was the maximum TLE on the preconditions for the question, and I could not feel the time difference.

At first glance, it seems that there is not much difference between Part 3, 4 and Part 5, and it seems good to say that there is a difference in speed depending on whether or not it is less than 0.65 seconds.

As a bonus

data.append(input())


 When I removed the cast with int, it took several times longer, so it seems better not to remove it.

Recommended Posts

TLE seemed to be scary depending on how the input was received
How to filter foreign keys that can be selected on the Django admin screen
Think about how to program Python on the iPad
How to put Takoyaki Oishikunaru on the segment tree
How to register the same data multiple times with one input on the Django management screen
How to solve the problem that video content cannot be played on Firefox for Linux
How to switch the configuration file to be read by Python
[Hyperledger Iroha] Notes on how to use the Python SDK
How to deploy the easiest python textbook pybot on Heroku
The problem becomes easier to solve depending on the formulation method
Notes on how to use marshmallow in the schema library
How to print characters to the console before booting on ARM
How to use the generator
How to register on pypi
[Python] How to use input ()
How to use the decorator
How to increase the axis
How to start the program
The record I was addicted to when putting MeCab on Heroku
A note on how to check the connection to the license server port
How easy is it to synthesize a drug on the market?
How to judge that the cross key is input in Python3
Django: Fluctuate the number of child forms depending on the number of input items
How to use Jupyter on the front end of supercomputer ITO
Difference in execution speed depending on how to write Cython function
How to update the python version of Cloud Shell on GCP
How to reflect validation error and input contents on the previous page without using render in the action