UT Martin Competitive Programming Guidebook

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Input in Python3 ======
There is no magic bullet that leads to the fastest input and output in a programming contest. In particular, when the fastest possible source is needed competitors will have little choice but to go with C++ or Java.

Having said this, there are typically multiple ways of performing and processing input and output in Python3. By understanding the options that are available and how to optimize them (e.g., conducting tests) you can see a real world performance increase, in particular when faced with high volumes of reads and writes.

In this and [[python3:output|related sections]] we will focus on standard (console) input because its us is typical of most programming contests.

===== Input Basics =====
Input in Python3 is handled via the ''%%input()%%'' function, and reads a newline-terminated string from standard input.((Unlike C++ and Java, input is line-based rather than token-based.)) Any additional processing is done to the resulting string.

<code python>
>>> x = input()
Hello World! # x="Hello World!"
</code>


<code python>
>>> x = int(input())
42 # x=42
</code>

<code python>
>>> x = input().split()
Hello World! # x=["Hello", "World!"]
</code>

<code python>
>>> (x, y) = map(int, input().split())
1 2 # x=1, y=2
</code>

''[[python3:map_reduce_filter|map()]]'' applies a function across a sequence or iterable structure. The comma '','' [[python3:unpacking | unpacks]] the map object into ''x'' and ''y''.

<code python>
>>> x = list(map(float, input().split()))
1.2 2.3 3.4 4.5 # x=[1.2, 2.3, 3.4, 4.5]
</code>

===== Advanced Input =====
''input()'' will scale well for many easy and mid-level contest problems. For mid to upper problems with significant bounds on reads and writes ''input()'' will carry an increased risk of //time limit exceeded// judgements.((There is no guaranteed cutoff, but for many problems ''input()'' is //increasingly likely// to fail around 10<sup>3</sup>≤//n//≤10<sup>4</sup> lines.))

=== stdin.readline() ===
''readline()'' is identical to the interface provided by ''input()'' except it //retains// the ''\n'' that is used to terminate the read.((This may require special handling in certain circumstance and can be safely ignored in others. E.g., ''.split()'' will //not// behave differently vs. ''input()''.))

<code python>
>>> from sys import *
>>> x = stdin.readline()
Hello World! # x="Hello World!\n"
</code>


=== stdin.readlines() ===
''readlines()'' processes an entire file, terminated by an //end of file// character.((This behavior can be simulated on the terminal with ''<ctrl>+d''.))

<code python>
>>> from sys import *
>>> x = stdin.readlines()
Hello
To Everyone! # x=["Hello\n", "To Everyone!\n"]
</code>

''<ctrl>+d'' would be used to terminate this example after the ''!''.

''readlines()'' loads //and// stores an entire file into memory (as a list) its performance will exceed other options in Python3 for all but the most enormous files.((See the table below for an example where ''readlines()'' required storing ∼1GB of data.))


===== Benchmarks =====
The following benchmarks demonstrate the increased likelihood of failure of ''input()'' as input sizes increase. All files used for testing can be found [[files:python3:input_tests|here]].

10 character and 1000 character benchmarks were selected to be indicative of many contest problems, and otherwise should indicate performance under most other assumptions.

==== Small Lines ====
10 characters((Selected to be roughly on the order of many similar reads: numeric primitives, small strings, etc.)) per line (//n//= number of lines):
| //n//          | input() | sys.stdin.readline() | sys.stdin.readlines() |
| 10<sup>4</sup> | .034s    | .016s                 | .018s                  |
| 10<sup>5</sup> | .146s    | .052s                 | .030s                  |
| 10<sup>6</sup> | 1.301s   | .301s                 | .130s                  |


==== Large Lines ====
1000 characters((Selected to be roughly on the order of problems with large reads that may be encountered in a contest setting.)) per line (//n//= number of lines):
| //n//          | input() | sys.stdin.readline() | sys.stdin.readlines() |
| 10<sup>4</sup> | .046s    | .037s                 | .033s                  |
| 10<sup>5</sup> | .282s    | .183s                 | .143s                  |
| 10<sup>6</sup> | 2.728s   | 1.430s                | 1.723s((The ''readlines()'' version is actually slower than ''readline()'' on the largest dataset.  It is attempting to store about 1GB in memory here, causing a slowdown, but still faster than ''input()''.
))                 |

The above tests were designed to showcase minimal reading functionality other than temporary storage.((We deliberately avoided additional processing such as typecasts, ''map()'', and ''split()'', as these are non-IO considerations in Python3.))
UT Martin Competitive Programming Guidebook

User Tools

Site Tools

Page Tools
