Esto es una pequeña guía al uso de algunas utilidades poco conocidas
de los entornos estándares de Linux usados en concursos de programación
tipo ICPC / CUPCAM. Está pensada para dar ideas útiles a concursantes.
Se pueden cronometrar programas, para ver cómo va el programa de tiempo:
$ time ./t < treasure.in > out.txt real 0m0.032s user 0m0.005s sys 0m0.000s
(nota: la E/S requiere mucho tiempo de CPU; es recomendable redirigir la salida para evitar alterar los resultados).
Si se quiere saber cómo va de memoria (el otro recurso limitado), se debe usar una variante:
$ \time ./t < treasure.in > out.txt 0.00user 0.00system 0:00.03elapsed 16%CPU (0avgtext+0avgdata 0maxresident)k 0inputs+0outputs (0major+115minor)pagefaults 0swaps
(aquí sí que se ve el uso de memoria; en este caso, es insignificante)
La utilidad 'bc' es una calculadora de precisión infinita por línea de comando. Por ejemplo:
$ bc bc 1.06 Copyright 1991-1994, 1997, 1998, 2000 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type `warranty'. 999999999999999999999999999999999999999999 + 1 1000000000000000000000000000000000000000000 quit
También se puede usar desde la consola, sin necesidad de entrar en el entorno:
$ echo 999999999999999999999999999999999999999999 + 1 | bc 1000000000000000000000000000000000000000000
La utilidad 'factor' devuelve una lista con los factores de un número cualquiera. Por ejemplo,
$ factor `echo '2^64-1'|bc` 18446744073709551615: 3 5 17 257 641 65537 6700417
A menudo programas perfectos fallan por pequeñas imperfecciones en su entrada o salida. La táctica recomendad es, para todos los ficheros de entrada, tener listos ficheros de salida. Y no mirar a ver si la salida está bien 'a ojímetro', sino con la utilidad 'diff' o 'cmp'; y en casos extremos, con 'hexdump'.
$ cmp a.txt b.txt a.txt b.txt differ: byte 25, line 2 $ diff a.txt b.txt 2c2 < harto curiosa --- > harto curiosa $ hexdump -C a.txt 00000000 75 6e 61 20 73 61 6c 69 64 61 0a 68 61 72 74 6f |una salida.harto| 00000010 20 63 75 72 69 6f 73 61 20 0a | curiosa .| 0000001a $ hexdump -C b.txt 00000000 75 6e 61 20 73 61 6c 69 64 61 0a 68 61 72 74 6f |una salida.harto| 00000010 20 63 75 72 69 6f 73 61 0a | curiosa.| 00000019
Hay un espacio de más al final de la primera cadena; esto puede ocasionar un error en un juez.
Si tu programa causa un Segmentation Fault (violación de segmento, usar memoria que no es suya, como lo quieras llamar), querrás saber dónde se ha producido. Por ejemplo:
$ cat docore.c
#include <stdlib.h>
int main() {
int *a=(int *)malloc(10*sizeof(int));
int i;
for (i=0;i<1000000; i++) a[i] = i;
return 0;
}
$ gcc -g -Wall docore.c -o c
$ ./c
Segmentation fault (core dumped)
NOTA: si sólo te sale el 'Segmentation fault', y no te sale el 'core dumped', tendrás que ejecutar
$ ulimit -c unlimited
Ahora lo puedes examinar con los siguientes comandos de GDB:
$ ./c Segmentation fault (core dumped) $ gdb c GNU gdb 6.3-debian Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "i386-linux"...Using host libthread_db library "/lib/tls/libthread_db.so.1". (gdb) core core Core was generated by `./c'. Program terminated with signal 11, Segmentation fault. warning: current_sos: Can't read pathname for load map: Input/output error Reading symbols from /lib/tls/libc.so.6...done. Loaded symbols for /lib/tls/libc.so.6 Reading symbols from /lib/ld-linux.so.2...done. Loaded symbols for /lib/ld-linux.so.2 #0 0x080483c5 in main () at docore.c:5 5 for (i=0;i<1000000; i++) a[i] = i; (gdb) print i $1 = 33790 (gdb) quit
Esto no es demasiado útil: el error debería haber saltado nada más llegar a la posición a[10]; no obstante, el programa ha logrado continuar hasta llegar a a[33790].
Para detectar un error tan pronto como sucede, es recomendable usar una librería especializada en depurar malloc()s, como por ejemplo Electric Fence. Abajo, un ejemplo de su uso:
$ gcc -g -Wall docore.c -o c -lefence $ ./c Electric Fence 2.1 Copyright (C) 1987-1998 Bruce Perens. Segmentation fault (core dumped) $ gdb c GNU gdb 6.3-debian Copyright 2004 Free Software Foundation, Inc. GDB is free software, covered by the GNU General Public License, and you are welcome to change it and/or distribute copies of it under certain conditions. Type "show copying" to see the conditions. There is absolutely no warranty for GDB. Type "show warranty" for details. This GDB was configured as "i386-linux"...Using host libthread_db library "/lib/tls/libthread_db.so.1". (gdb) core core Core was generated by `./c'. Program terminated with signal 11, Segmentation fault. warning: current_sos: Can't read pathname for load map: Input/output error Reading symbols from /usr/lib/libefence.so.0...done. Loaded symbols for /usr/lib/libefence.so.0 Reading symbols from /lib/tls/libc.so.6...done. Loaded symbols for /lib/tls/libc.so.6 Reading symbols from /lib/tls/libpthread.so.0...done. Loaded symbols for /lib/tls/libpthread.so.0 Reading symbols from /lib/ld-linux.so.2...done. Loaded symbols for /lib/ld-linux.so.2 #0 0x080484b5 in main () at docore.c:5 5 for (i=0;i<1000000; i++) a[i] = i; (gdb) print i $1 = 10 (gdb) quit
Usando un "script" adecuado se pueden acelerar partes tediosas necesarias para resolver un programa. Pongamos, por ejemplo, que nuestro programa se vería beneficiado por tener una tabla de números primos entre 1 y 1000 (por ejemplo, nos están pidiendo calcular todos los números expresables como producto de dos primos, o algo así de rebuscado).
Una solución es programar una rutina que lo calcule al comienzo del programa. Otra solución es precalcularlo, e incluirlo como datos estáticos dentro del programa: por ejemplo,
$ echo 'int primos[] = {'; for ((i=0;i<1000;i++)) ; do
factor $i | sed -ne 's/\(\w*\): \w*$/ \1,/ip' ;
done ; echo ' -1 };'
(funciona copiando y pegando en un terminal; también se podría pegar dentro de un fichero y ejecutarlo) genera esta lista, y la formatea como un array 'C', listo para ser copiado y pegado en un programa.
También se puede precalcular en un programa C, pero en este caso no tendremos disponibles todas las herramientas que nos ofrece el entorno estándar de Unix.
NOTA: los programas 'precalculados' son legales. No hay ninguna razón para no usarlos cuando puedan ser efectivos. En estos concursos no importa la "elegancia" del código: elegancia es que funcione y se pueda escribir en poco tiempo, no que sea legible o use un algoritmo tremendamente sofisticado.