Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

Travailler efficacement avec le compilateur et le shell

Arthur Charguéraud pour www.france-ioi.org

Introduction

Ce document décrit diverses techniques destinées à vous faire gagner du temps lorsque vous travaillez sur vos algorithmes.

Plan

  1. Ligne de commande de compilation C/C++
  2. Ligne de commande de compilation Caml
  3. Redirection des flux de données
  4. Compilation et exécution en une commande
  5. Gérer plusieurs fichiers tests
  6. Mesurer le temps d'exécution
  7. Vérifier la mémoire utilisée
  8. [C/C++] Redirection des flux de données avec freopen
  9. [C/C++] Préprocesseur C/C++ pour commenter
  10. [C/C++] Préprocesseur C/C++ pour déboguer
  11. [Avancé] Utiliser 'diff' pour comparer des résultats
  12. [Avancé] Script bash pour tester en batch
  13. [Avancé] Script bash pour évaluer en batch

Notations

En C/C++ :

  • fichier source : "algo.cpp"
  • compilateur : "g++" ou "gcc" (resp. compilateurs C++ et C)

En Caml :

  • fichier source : "algo.ml"
  • compilateur : "ocamlc" ou "ocamlopt" (respectivement compilateur en bytecode et en code natif)

Dans tous les cas :

  • exécutable : "output.exe"
  • fichier d'entrée : "test.in"
  • fichier de sortie : "test.out"

On suppose que votre fichier source s'appelle si vous codez en C++, et "algo.ml" si vous codez en Caml.

Ligne de commande de compilation C/C++

   g++ -Wall -O2 -o output.exe algo.cpp

Remarque : si vous voulez vraiment faire du C et non du C++, remplacez "g++" par "gcc".

L'option -Wall active un maximum de warnings, ce qui permet de minimiser le nombre de bugs potentiels. Il est plus que fortement déconseillé de travailler avec un code qui produit des warnings.

L'option -O2 (c'est un 'O' et non un '0') indique au compilateur qu'il faut qu'il se fatigue un peu plus pour essayer de produire du code plus performant. On peut gagner un facteur 2 ou 3 en vitesse dans certain cas.

Ligne de commande de compilation Caml

En mode "bytecode" (compilation rapide, programme peu performant) :

   ocamlc -o output.exe algo.ml

En mode "code natif" (compilation plus lente, programme beaucoup plus performant) :

   ocamlopt -o output.exe algo.ml

Le rapport de performance entre ocamlc et ocamlopt est compris généralement entre 5 et 10. Autrement dit, un programme en bytecode (ocamlc) est toujours au moins 5 fois plus lent que le même programme compilé en code natif (ocamlopt).

En conclusion, le plus simple c'est de travailler avec ocamlc, et d'utiliser ocamlopt uniquement lorsque vous avez besoin de tester votre programme dans des cas extrêmes.

Attention, pour que "ocamlopt" marche, vous devez avoir installé "MinGW". Pour tous les détails, allez voir sur la page du cours Caml.

Redirection des flux de données

  • Votre programme peut lire des données :
    • soit sur l'entrée standard, avec scanf
    • soit dans des fichiers, avec fscanf
  • Votre programme peut écrire des données :
    • soit sur la sortie standard, avec printf
    • soit dans des fichiers, avec fprintf

Sur notre site, presque tout se fait avec l'entrée standard, et nous vous recommandons donc de travailler exclusivement avec des scanf et des printf. N'utilisez pas les entrées-sorties C++ (cin et cout) qui peuvent être beaucoup plus lentes dans certains cas (jusqu'à un facteur 10 !).

Pour tester votre programme sur des fichiers tests, il faut donc envoyer les données d'un fichier ("test.in") vers l'entrée standard de votre programme. Et si votre programme affiche beaucoup d'informations, il faut rediriger la sortie standard vers un fichier ("test.out"). Voici comment faire :

  • Pour envoyer les données du fichier test.in sur l'entrée standard, et obtenir les résultats dans la console :
    output.exe < test.in
  • Pour simplement rediriger la sortie du programme vers le fichier test.out :
    output.exe > test.out
  • Pour faire les deux à la fois, c'est-à-dire donner le fichier test.in sur l'entrée standard et écrire la sortie du programme dans le fichier test.out :
    output.exe < test.in > test.out

Compilation et exécution en une commande

Ce que l'on montre ici marche dans une console Linux, mais pas sous Windows. On peut aussi faire la même chose sous Windows si on installe les outils "MSys". Mais en pratique, on utilise un IDE avec des bons raccourcis claviers, et il n'y a donc pas besoin de faire ce qui est décrit ici.

La séquence que vous allez utiliser le plus souvent est la suivante :

   Essayer de compiler le programme
   Si ça marche
      Alors tester le programme
      Sinon aller corriger le code

Il existe un moyen très efficace d'automatiser cela à l'aide d'une seule ligne de commande. L'idée est de lancer la commande de compilation, et si elle réussit, demander à ce que soit automatiquement lancé la commande d'exécution. Pour cela on utilise l'opérateur && (c'est le même opérateur qu'en C/C++ ou Caml).

   g++ -Wall -O2 -o output.exe algo.ml  &&  output.exe < test.in > test.out

L'intérêt c'est que le programme "output.exe" n'est pas exécuté si la compilation ne réussit pas.

Gérer plusieurs fichiers tests

En pratique vous devez avoir plusieurs fichiers tests, car un seul test n'est jamais suffisant. Pour tester votre programme sur différents fichiers tests, utilisez les commandes :

   output.exe < test1.in
   output.exe < test2.in 
   output.exe < test3.in 

Pour afficher le contenu du fichier d'entrée juste avant de voir le résultat, utilisez "cat"

   cat test1.in ; output.exe < test1.in

Vous pouvez en ajoutez un trait pour séparer l'entrée et la sortie en utilisant "echo" :

   cat test1.in ; echo ; echo ---- ; output.exe < test1.in

On verra plus tard comment automatiser cette commande avec un script.

Mesurer le temps d'exécution

On décrit la méthode sous Linux. Sous Windows, c'est plus délicat; la solution simple : sortez votre chronomètre ;)

Pour évaluer le temps d'exécution de votre programme sur votre machine, utilisez la commande "time" :

   time output.exe < big1.in

Cette commande affichera trois lignes, du genre :

   real 0m0.522s
   user 0m0.324s
   sys  0m0.051s

Le temps real correspond au temps qui s'est effectivement écoulé, dans le monde réel, entre le début et la fin de l'exécution de votre programme. Il peut dépendre de nombreux facteurs, comme par exemple les autres programmes exécutés au même moment par la machine.

Le temps user correspond au temps que le processeur a passé à exécuter les instructions de votre programme, sans compter les appels systèmes.

Le temps sys correspond au temps que le processeur a passé à exécuter les appels systèmes, c'est à dire une partie du temps utilisé par des fonctions systèmes comme malloc, printf ou scanf.

Le temps qui vous intéresse est le total du temps user et du temps sys.

N'oubliez pas que votre machine n'est pas nécessairement du même type que celle sur laquelle votre programme sera évalué, et donc le temps d'exécution du programme sur votre machine ne sera pas le même que le temps d'exécution sur le serveur. Nous vous invitons à faire quelques tests pour établir une correspondance.

[Unix] Vérifier la mémoire utilisée

Pour vérifier que votre programme n'utilise pas trop de mémoire, sous linux, vous pouvez utiliser la commande bash "ulimit", qui permet de fixer une limite pour certaines ressources. Ces limites seront appliquées à tout programme lancé à partir de ce shell.

Attention : une fois que vous avez fixé une limite, vous ne pouvez pas la réaugmenter sans quitter le shell. Lancer donc un nouveau shell temporairement (commande sh) pour faire votre test.

>Pour fixer une limite globale à l'utilisation de la mémoire :

   ulimit -v taille_memoire

où taille_memoire est une valeur en kilo-octets. Par exemple pour limiter à 16 Mo :

   ulimit -v 16000

Si vous exécutez ensuite votre programme dans ce shell, une erreur sera affichée si la mémoire est insuffisante. Il peut s'agir d'un simple message "Killed", ou d'une erreur d'allocation, ou de segmentation. Si vous utilisez des mallocs, vérifiez qu'ils n'ont pas renvoyé un pointeur nul.

Dans certain cas, on peut vous indiquer une limite séparée pour la taille de la pile. Vous pouvez la fixer avec l'option -s :

   ulimit -s taille_pile

où taille_pile est en kilo-octets.

A tout moment, vous pouvez afficher les limites actuelles du shell en appelant "ulimit -v" ou "ulimit -s" sans indiquer la taille. Pour plus de détails, utilisez la commande "ulimit -a" qui permet d'afficher toutes les limites qu'il est possible de fixer.

[Windows] Vérifier la mémoire utilisée

Pour commencer, ajoutez à votre programme une instruction pour l'empêcher de se terminer :

en C/C++ :   system("PAUSE");          // nécessite #include <stdlib.h>
en Caml  :   Sys.command "PAUSE";

Attention, si vous exécutez le programme dans un IDE avec une redirection de l'entrée standard, il sera nécessaire de killer le programme pour le terminer (soit à l'aide d'un bouton adapté dans votre IDE, soit par ALT+CTLR+SUPPR).

Ensuite, lancez votre programme, et faîtes ALT+CTRL+SUPPR pour accéder au gestionnaire de tâches. Là, allez dans l'onglet "processus". Là cherchez la ligne contenant le nom de votre programme, c'est-à-dire "output.exe". Regardez dans la colonne "utilisation de mémoire". Cela vous donne la mémoire utilisée à ce moment là.

Dans la plupart des cas, cela suffit. Cependant, si vous utilisez allocations dynamiques (des malloc et des free en C++, ou alors si vous codez en Caml), il faut afficher une autre colonne. Pour cela, allez dans le menu "Affichage", sur "Sélection des colonnes", et cochez "utilisation maximale de la mémoire". Vous pouvez maintenant visualiser la consommation maximale de mémoire d'un programme au cours de son exécution.

[C/C++] Redirection des flux de données avec freopen

Si le sujet vous impose de lire et écrire dans des fichiers, il existe un moyen pratique pour le gérer. L'idée est d'utiliser une instruction à l'intérieur de votre programme pour rediriger l'entrée et la sortie standard. Cette fonction s'appelle "freopen". Voici un exemple de programme, où l'on montre comment lire un entier dans un fichier puis en écrire la valeur dans un autre fichier, le tout en utilisant "scanf" et "prinf" et non "fscanf" et "fprintf" qui sont plus lourds à manipuler.

int main()
{
   freopen("test.in", "r", stdin);
   freopen("test.out", "w", stdout);

   int unEntier;
   scanf("%d", &unEntier);
   printf("%d\n", unEntier);

   return 0;
}

[C/C++] Préprocesseur C/C++ pour commenter

Le préprocesseur permet d'ignorer un certain nombre de lignes du programme. Cela peut être utile si vous désirez conserver dans le code certaines fonctions que vous n'utilisez plus. On pourrait utiliser la syntaxe /* ... */, mais elle ne gère pas les imbrications.

En bref, il suffit d'écrire :

   #if 0

   lignes complètement ignorées
   ...

   #endif

Non seulement ce système permet d'imbriquer les zones ignorées les unes dans les autres, mais en plus on peut rétablir un passage très facilement : il suffit de changer le 0 en 1 pour annuler le commentaire.

[C/C++] Préprocesseur C/C++ pour déboguer

Le préprocesseur peut aussi servir à maintenir dans un même fichier une version de test, avec des affichages permettant de debugger, et une version finale contenant uniquement ce qui sera soumis à la fin. Concrètement, on met dans le code les instructions d'affichage entre les balises #ifdef DEBUG et #endif:

   #ifdef DEBUG
      printf("Distances des noeuds\n");
      for (int noeud = 0; noeud < nbNoeuds; noeud++)
         print("%d\t", noeud);
      printf("\n");
      for (int noeud = 0; noeud < nbNoeuds; noeud++)
         print("%d\t", dist[noeud]);
      printf("\n");
   #endif

Par défaut, la variable DEBUG n'est pas définie, et toutes ces lignes sont donc ignorées. Si l'on souhaite que ces lignes soient exécutées, on ajoute une ligne en haut du source pour définir DEBUG :

   #define DEBUG

Pour passer rapidement du mode déboguage au mode normale, on commente ou décommente cette ligne

   // #define DEBUG

Surtout, n'oubliez pas d'enlever ou de commenter la ligne #define DEBUG au moment de soumettre le code de votre programme !

Une autre solution très pratique permet de gérer la définition ou non de la variable DEBUG. Le truc, c'est de spécifier une option au compilateur pour qu'il définisse la valeur DEBUG. Cette option est "-DDEBUG".

   g++ -Wall -O2 -DDEBUG -o output.exe algo.cpp

[Avancé] Utiliser 'diff' pour comparer des résultats

Le programme 'diff' est disponible par défaut sous Linux. Sous Windows, trois possibilités : a) récupérer le programme diff.exe, b) installer MSys, diff viendra avec, c) utiliser "fc" un programme équivalent préinstallé sous Windows.

Si vous souhaitez comparer les résultats de deux algorithmes différents sur un même fichier test et que les sorties des programmes sont trop grosses pour être comparées à la main, le programme 'diff' est là pour vous aider. C'est très simple, donnez à 'diff' deux fichiers, et il vous montrera les différences entre les deux fichiers.

   diff fichier1 fichier2

Si vous voulez juste savoir si les fichiers sont égaux ou non et ne pas visualiser tous les détails, utilisez l'option "-q" (q comme quiet) :

   diff -q fichier1 fichier2

Si vous souhaitez ignorer les différences qui sont simplement des caractères d'espacement comme ' ', '\t', '\n', utilisez l'option "-w" (w comme white-space) :

   diff -w fichier1 fichier2

Remarque, notre serveur d'évaluation utilise en général ces deux options pour déterminer si votre programme passe le test ou non :

   diff -q -w sortie_attendue votre_sortie

[Avancé] Script bash pour tester en batch

Les scripts bash marchent sous Linux, et sous Windows à condition que MSys soit installé (ou cygwin).

Si vous avez plusieurs fichiers tests et que vous voulez regarder ce que donne votre programme sur tous ces tests, un petit script peut vous faire gagner beaucoup de temps. On suppose que tous les fichiers tests ont pour extension ".in" et on va générer pour chaque fichier test la sortie dans un fichier ".out" correspondant. On écrit le script dans un fichier "test_all.sh", dont voici le contenu :

   g++ -Wall -O2 -o output.exe $1
   for test_in in *.in; do
   	echo Solving $test_in ...;
      ./output.exe < $test_in > `basename $test_in .in`.out;
   done

La syntaxe est difficile à lire, mais en gros on fait une boucle sur tous les fichiers ".in", on affiche un petit message pour afficher le nom du fichier que l'on va traiter, et ensuite on exécute le programme sur ce fichier. Le $1 sur la première ligne fait référence à l'argument donné au script.

Pour utiliser ce script, il suffit d'appeler avec en argument votre fichier source :

   ./test_all.sh algo.cpp

Si vous êtes sous unix et que cette commande ne marche pas, vérifiez que le fichier est marqué comme exécutable. Faites éventuellement "chmod +x test_all.sh" pour régler le problème.

Si vous souhaitez vérifier que votre fichier source compile effectivement avant de lancer son exécution, utilisez un "if" :

   if g++ -Wall -O2 -o output.exe algo.cpp
   then 
   for test_in in *.in; do
   	echo Solving $test_in ...;
      ./output.exe < $test_in > `basename $test_in .in`.out;
   done
   else
      echo Erreur de compilation
   fi

[Avancé] Script bash pour évaluer en batch

On va combiner l'utilisation du script et du diff pour évaluer un programme de la même manière que c'est fait sur notre serveur :

  • le dossier courant contient votre source, des fichiers tests (*.in), et les solutions correspondantes (*.out)
  • le source va être compilé
  • le programme va être exécuté sur tous les fichiers tests (*.res)
  • les sorties de votre programme vont être comparées au solutions attendues (*.out vs *.res)

Voici le contenu du script "evaluate.sh" :

   g++ -Wall -O2 -o output.exe $1
   for test_in in *.in; do
   	echo Checking $test_in ...;
      ./output.exe < $test_in > `basename $test_in .in`.res;
      diff -q -w `basename $test_in .in`.out `basename $test_in .in`.res;
   done

Pour utiliser ce script, il suffit d'appeler avec en argument votre fichier source :

   ./evaluate.sh algo.cpp

Un message sera donné pour chaque fichier test utilisé, et une ligne supplémentaire précise si la sortie du programme n'est pas identique à la sortie attendue.

Regardons le résultat sur un exemple complet. On suppose que dans le dossier courant on a :

   - algo.cpp    le source du programme
   - test1.in    contenant "5 4 20 25"
   - test1.out   contenant "45 1" (sortie attendue pour test1.in)
   - test2.in    contenant "8 3 41 67"
   - test2.out   contenant "17 12" (sortie attendue pour test2.in)

On lance alors la commande "./evaluate algo.cpp", et ceci produit dans le dossier courant :

   - output.exe  le programme compilé
   - test1.res   la sortie du programme exécuté sur le fichier test1.in
   - test2.res   la sortie du programme exécuté sur le fichier test2.in

on va par exemple supposer que :

   - test1.res   contient "45 1"  (le résultat attendu pour ce test)
   - test2.res   contient "20 4"  (autre chose que le résultat attendu)

Le message affiché sera dans ce cas :

   Checking test1.in ...
   Checking test2.in ...
   Files test2.out and test2.res differ

À ce moment, vous souhaitez probablement connaître les différences entre test2.out et test2.res. Si les fichiers sont petits, un "cat" sera le plus pratique :

   cat test2.out
   cat test2.res

Ou bien en une seule commande :

   cat test2.out ; echo --- ; cat test2.res

Et dans le cas où les fichiers tests sont plus gros, utilisez diff :

   diff test2.out test2.res
Pensez à vous inscrire pour valider les cours et résoudre les exercices.