Skip to Content
CTRL K

Entrada y salida rápidas

La página de instrucciones de USACO  menciona brevemente algunas formas de acelerar la E/S:

En algunos de los problemas más avanzados con entradas más grandes, puede convenir usar entrada/salida rápida para pasar más fácilmente el límite de tiempo. Quienes usan C++ pueden querer agregar ios_base::sync_with_stdio(false); cin.tie(0); al inicio del método main si usan cin/cout. Quienes usan Java pueden querer usar BufferedReader en lugar de Scanner.

¿Qué hacen estas cosas y cuánta diferencia marcan en la práctica? Vamos a usar la siguiente tarea para medir la velocidad de E/S:

Tarea de ejemplo

La entrada consiste en dos enteros MM (0≤M≤10\le M\le 1) y NN (1≤N≤1061\le N\le 10^6), seguidos de una secuencia de NN enteros no negativos, cada uno menor que 109+710^9+7.

  • Si M=0M=0, imprimir la suma de la secuencia de entrada módulo 109+710^9+7.
  • Si M=1M=1, imprimir la suma de cada prefijo de la secuencia de entrada módulo 109+710^9+7.

Entrada de ejemplo 1:

1 6
1
2
3
4
5
1000000000

Salida de ejemplo 1:

1
3
6
10
15
8

Entrada de ejemplo 2:

0 6
1
2
3
4
5
1000000000

Salida de ejemplo 2:

8

Al generar datos de prueba al azar se obtienen archivos de entrada y de salida de unos ~10MB cada uno. Es posible ver archivos de entrada de este tamaño (el 11.º archivo de entrada de Robotic Cow Herd  mide unos ~10.3MB), aunque no archivos de salida (el más grande que conocemos es el de Minimum Cost Paths , cuyo archivo de salida mide unos ~2.8MB).

HechoFuenteNombreDificultadTagsSolución
PlatinumRobotic Cow HerdInsano—

E/S estándar

Lenta

Algunos métodos simples de E/S no se acercan a terminar dentro del límite de tiempo:

cin/cout + endl (5.8s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	int M, N;
	cin >> M >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		ans = (ans + x) % MOD;
		if (M == 1) { cout << ans << endl; }
	}
	if (M == 0) { cout << ans << endl; }
}
Scanner + System.out.println (16.7s)
import java.io.*;
import java.util.*;
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int M = sc.nextInt();
		int N = sc.nextInt();
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + sc.nextInt()) % MOD;
			if (M == 1) { System.out.println(ans); }
		}
		if (M == 0) { System.out.println(ans); }
	}
}
input + print (18.9s)
MOD = 10**9 + 7
 
M, N = map(int, input().split())
 
ans = 0
for _ in range(N):
	x = int(input())
	ans = (ans + x) % MOD
	if M == 1:
		print(ans)
 
if M == 0:
	print(ans)

Rápida

cin/cout

Si se usan cin y cout, hay que incluir las dos líneas siguientes.

ios::sync_with_stdio(false);
cin.tie(nullptr);

Explicación breve:

  • Si se incluye ios::sync_with_stdio(false), mezclar E/S al estilo C (scanf, printf) y al estilo C++ (cin, cout) puede producir resultados inesperados. La ventaja es que tanto cin como cout se vuelven más rápidos.
  • Incluir cin.tie(nullptr) reduce el tiempo de ejecución si se intercalan cin y cout (como ocurre en la tarea de este módulo).

Hay más información sobre estas líneas al final de este módulo.

cin/cout + unsync + \n (0.41s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	int M, N;
	cin >> M >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		ans = (ans + x) % MOD;
		if (M == 1) { cout << ans << "\n"; }
	}
	if (M == 0) { cout << ans << "\n"; }
}

scanf/printf

scanf/printf (0.52s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	int M, N;
	scanf("%d%d", &M, &N);
 
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		ans = (ans + x) % MOD;
		if (M == 1) { printf("%d\n", ans); }
	}
	if (M == 0) { printf("%d\n", ans); }
}

Usar BufferedReader y PrintWriter en su lugar.

BufferedReader + PrintWriter (1.2s)
import java.io.*;
import java.util.*;
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + Integer.parseInt(br.readLine())) % MOD;
			if (M == 1) { pw.println(ans); }
		}
		if (M == 0) { pw.println(ans); }
		pw.close();
	}
}

Reemplazar input por sys.stdin.readline produce una aceleración enorme.

readline + print (2.9s)
import sys
 
input = sys.stdin.readline
 
MOD = 10**9 + 7
 
M, N = map(int, input().split())
 
ans = 0
for _ in range(N):
	x = int(input())
	ans = (ans + x) % MOD
	if M == 1:
		print(ans)
if M == 0:
	print(ans)

Usar sys.stdin.readline y sys.stdout.write es un poco más rápido:

readline + write (2.4s)
import sys
 
read = sys.stdin.readline
write = sys.stdout.write
 
MOD = 10**9 + 7
 
M, N = map(int, read().split())
 
ans = 0
for _ in range(N):
	x = int(read())
	ans = (ans + x) % MOD
	if M == 1:
		write(str(ans) + "\n")
if M == 0:
	write(str(ans) + "\n")

E/S por archivos

Bastante similar a la E/S estándar.

Lenta

freopen + cin/cout (5.7s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	freopen("speed.in", "r", stdin);
	freopen("speed.out", "w", stdout);
 
	int M, N;
	cin >> M >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		ans = (ans + x) % MOD;
		if (M == 1) { cout << ans << "\n"; }
	}
	if (M == 0) { cout << ans << "\n"; }
}

Rápida

freopen + cin/cout + unsync + \n (0.42s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
 
	freopen("speed.in", "r", stdin);
	freopen("speed.out", "w", stdout);
 
	int M, N;
	cin >> M >> N;
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		ans = (ans + x) % MOD;
		if (M == 1) { cout << ans << "\n"; }
	}
	if (M == 0) { cout << ans << "\n"; }
}
freopen + scanf/printf (0.52s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	freopen("speed.in", "r", stdin);
	freopen("speed.out", "w", stdout);
	int M, N;
	scanf("%d%d", &M, &N);
	int ans = 0;
	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);
		ans = (ans + x) % MOD;
		if (M == 1) { printf("%d\n", ans); }
	}
	if (M == 0) { printf("%d\n", ans); }
}
ifstream/ofstream (0.43s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int main() {
	ifstream fin("speed.in");
	ofstream fout("speed.out");
	int M, N;
	fin >> M >> N;
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int x;
		fin >> x;
		ans = (ans + x) % MOD;
		if (M) fout << ans << "\n";
	}
	if (!M) fout << ans << "\n";
}

Lenta

Scanner + PrintWriter (3.4s)
import java.io.*;
import java.util.*;
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(new File("speed.in"));
		PrintWriter pw = new PrintWriter("speed.out");
 
		int M = sc.nextInt();
		int N = sc.nextInt();
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + sc.nextInt()) % MOD;
			if (M == 1) { pw.println(ans); }
		}
		if (M == 0) { pw.println(ans); }
		pw.close();
	}
}

Rápida

BufferedReader + PrintWriter (1.2s)
import java.io.*;
import java.util.*;
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new FileReader("speed.in"));
		PrintWriter pw = new PrintWriter("speed.out");
		StringTokenizer st = new StringTokenizer(br.readLine());
		int M = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + Integer.parseInt(br.readLine())) % MOD;
			if (M == 1) { pw.println(ans); }
		}
		if (M == 0) { pw.println(ans); }
		pw.close();
	}
}

Una variante del método de arriba consiste en envolver el BufferedReader con un StreamTokenizer:

StreamTokenizer (1.2s)
import java.io.*;
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
 
	static StreamTokenizer st;
	static int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
 
	public static void main(String[] args) throws Exception {
		st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter pw = new PrintWriter(System.out);
		int M = nextInt();
		int N = nextInt();
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + nextInt()) % MOD;
			if (M == 1) { pw.println(ans); }
		}
		if (M == 0) { pw.println(ans); }
		pw.close();
	}
}
readline + write (2.4s)
read = open("speed.in", "r").readline
write = open("speed.out", "w").write
 
MOD = 10**9 + 7
 
M, N = map(int, read().split())
ans = 0
for _ in range(N):
	x = int(read())
	ans = (ans + x) % MOD
	if M == 1:
		write(str(ans) + "\n")
if M == 0:
	write(str(ans) + "\n")

Métodos aún más rápidos

Los métodos de entrada descritos arriba son fáciles de escribir desde cero y suelen ser lo suficientemente rápidos para contests de USACO. Pero si se busca algo aún más rápido…

Usar fread y fwrite reduce todavía más el tiempo de ejecución.

fread/fwrite (0.17s)
#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
const int BUF_SZ = 1 << 15;
 
// BeginCodeSnip{Input}
inline namespace Input {
char buf[BUF_SZ];
int pos;
int len;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) { return EOF; }
	}
	return buf[pos++];
}
 
int read_int() {
	int x;
	char ch;
	int sgn = 1;
	while (!isdigit(ch = next_char())) {
		if (ch == '-') { sgn *= -1; }
	}
	x = ch - '0';
	while (isdigit(ch = next_char())) { x = x * 10 + (ch - '0'); }
	return x * sgn;
}
}  // namespace Input
// EndCodeSnip
// BeginCodeSnip{Output}
inline namespace Output {
char buf[BUF_SZ];
int pos;
 
void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}
 
void write_char(char c) {
	if (pos == BUF_SZ) { flush_out(); }
	buf[pos++] = c;
}
 
void write_int(int x) {
	static char num_buf[100];
	if (x < 0) {
		write_char('-');
		x *= -1;
	}
	int len = 0;
	for (; x >= 10; x /= 10) { num_buf[len++] = (char)('0' + (x % 10)); }
	write_char((char)('0' + x));
	while (len) { write_char(num_buf[--len]); }
	write_char('\n');
}
 
// hacer flush automático de la salida al terminar el programa
void init_output() { assert(atexit(flush_out) == 0); }
}  // namespace Output
// EndCodeSnip
 
int main() {
	init_output();
	int M = read_int();
	int N = read_int();
	int ans = 0;
	for (int i = 0; i < N; i++) {
		ans = (ans + read_int()) % MOD;
		if (M == 1) { write_int(ans); }
	}
	if (M == 0) { write_int(ans); }
}

Métodos aún más rápidos

Los métodos de entrada descritos arriba son fáciles de escribir desde cero y suelen ser lo suficientemente rápidos para contests de USACO. Pero si se busca algo aún más rápido…

Aún más rápido que BufferedReader es una clase de E/S rápida escrita a medida que lee bytes directamente de un InputStream.

InputStream + PrintWriter (0.84s)
import java.io.*;
import java.util.*;
 
// BeginCodeSnip{FastIO}
class FastIO extends PrintWriter {
	private InputStream stream;
	private byte[] buf = new byte[1 << 16];
	private int curChar;
	private int numChars;
 
	// entrada estándar
	public FastIO() { this(System.in, System.out); }
 
	public FastIO(InputStream i, OutputStream o) {
		super(o);
		stream = i;
	}
 
	// entrada por archivo
	public FastIO(String i, String o) throws IOException {
		super(new FileWriter(o));
		stream = new FileInputStream(i);
	}
 
	// lanza InputMismatchException() si ya se detectó el fin de archivo
	private int nextByte() {
		if (numChars == -1) { throw new InputMismatchException(); }
		if (curChar >= numChars) {
			curChar = 0;
			try {
				numChars = stream.read(buf);
			} catch (IOException e) { throw new InputMismatchException(); }
			if (numChars == -1) {
				return -1;  // fin de archivo
			}
		}
		return buf[curChar++];
	}
 
	// para leer líneas enteras, reemplazar c <= ' '
	// por una función que compruebe si c es un salto de línea
	public String next() {
		int c;
		do { c = nextByte(); } while (c <= ' ');
 
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = nextByte();
		} while (c > ' ');
		return res.toString();
	}
 
	public int nextInt() {  // nextLong() se implementaría de forma similar
		int c;
		do { c = nextByte(); } while (c <= ' ');
 
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = nextByte();
		}
 
		int res = 0;
		do {
			if (c < '0' || c > '9') { throw new InputMismatchException(); }
			res = 10 * res + c - '0';
			c = nextByte();
		} while (c > ' ');
		return res * sgn;
	}
 
	public double nextDouble() { return Double.parseDouble(next()); }
}
// EndCodeSnip
 
public class Solution {
	static final int MOD = (int)1e9 + 7;
	public static void main(String[] args) throws Exception {
		FastIO io = new FastIO();
		int M = io.nextInt();
		int N = io.nextInt();
		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans = (ans + io.nextInt()) % MOD;
			if (M == 1) { io.println(ans); }
		}
		if (M == 0) { io.println(ans); }
		io.close();
	}
}

Notas adicionales

Recursos
FuenteRecursoNotas
CFYet again on C++ I/O

tiempos de varios métodos de E/S

ios::sync_with_stdio(false)

Recursos
FuenteRecursoNotas
CPPios_base::sync_with_stdio

documentación

SOSignificance of ios_base::sync_with_stdio(false);

Del segundo recurso:

Esto desactiva la sincronización entre los flujos estándar de C y de C++. Por defecto, todos los flujos estándar están sincronizados, lo que en la práctica permite mezclar E/S al estilo C y al estilo C++ y obtener resultados coherentes y esperados. Si se desactiva la sincronización, los flujos de C++ pueden tener sus propios buffers independientes, lo que convierte mezclar E/S al estilo C y C++ en una aventura.

cin.tie(nullptr)

Recursos
FuenteRecursoNotas
CPPios::tie

documentación

SOSignificance of cin.tie(NULL);

Del segundo recurso:

Esto desvincula cin de cout. Los flujos vinculados aseguran que uno se vacíe (flush) de forma automática antes de cada operación de E/S sobre el otro flujo.

Por defecto cin está vinculado a cout para asegurar una interacción razonable con el usuario. Por ejemplo:

std::cout << "Enter name:";
std::cin >> name;

Si cin y cout están vinculados, se puede esperar que la salida se vacíe (es decir, que sea visible en la consola) antes de que el programa pida entrada al usuario. Si se desvinculan los flujos, el programa puede bloquearse esperando a que el usuario ingrese su nombre pero el mensaje “Enter name” todavía no es visible (porque cout está bufferizado por defecto; la salida se vacía/muestra en la consola solo bajo demanda o cuando el buffer está lleno).

Así, si se desvincula cin de cout, hay que asegurarse de hacer flush de cout a mano cada vez que se quiera mostrar algo antes de esperar entrada en cin.

Problemas

HechoFuenteNombreDificultadTagsSolución
CFSoldier and Number GameNormal—
C++ con la línea de comandosDepuración básica