CSC 4103 – Programmation système

Devoir hors présentiel: One billion row challenge

L'objectif de ce projet est de faire le One billion row challenge en C. Ce challenge de programmation consiste à traiter le plus rapidement possible un fichier contenant des données.

Dans le challenge originel, le fichier à traiter contient un milliard de lignes. Pour ce devoir, nous proposons plusieurs fichiers plus ou moins grands. Chaque ligne contient un nom de ville et une température:

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
    

Le programme doit afficher la liste des villes (triées alphabétiquement) et la température minimum, moyenne, et maximum de chaque ville au format json:

 [ {"city": "Abha", "min": 10.1, "max": 27.6, "mean": 17.7},{"city": "Abidjan", "min": 17.9, "max": 34.7, "mean": 25.5},{"city": "Abu Dhabi", "min": 15.5, "max": 40.7, "mean": 28.2},{"city": "Abéché", "min": 22.2, "max": 36.4, "mean": 30.8},{"city": "Accra", "min": 16.1, "max": 32.6, "mean": 24.4},{"city": "Addis Ababa", "min": 8.1, "max": 23.9, "mean": 15.8},...]
    

L'objectif de ce projet est de vous faire implémenter diverses structures de données (liste, arbres, hashmap, etc.). il vous est donc demandé de les implémenter vous-même plutot que de vous reposer sur des implémentations existantes.

Générer le fichier d'entrée

Téléchargez le fichier one_billion_row_sujet.tgz. Ce fichier contient quelques petit fichiers d'entrée: (

measurements_10k.csv: contient 10 000 mesures
measurements_1k_16_cities.csv: contient 1000 mesures issues de 16 villes

D'autres fichiers plus volumineux peuvent être téléchargés ici: https://stark2.int-evry.fr/csc4103/one_billion_row/

Vous pouvez également générer vos propres fichiers de données avec le script generate_data.py:

$ python generate_data.py 100000000 Generating 100000000 data points in measurements.csv [...]

Attention ! Un fichier d'1 milliard de lignes occupe environ 13 Go sur votre disque dur, et sa génération est très longue !

Implémentation naïve

Dans un premier temps, implémentez une version naïve (c'est à dire non optimisée) du programme 1b_challenge.c. Cette implémentation doit:

allouer un tableau de struct city nommé cities
lire le fichier input_file ligne par ligne
détecter le nom de la ville (V) et la température (T) de la ligne lue
mettre à jour les statistiques du struct city correspondant à la ville V dans cities. Si c'est la première fois que la ville V est lue, il faut ajouter une nouvelle entrée dans cities (et éventuellement agrandir le tableau).
appeler la fonction print_cities. Cette fonction écrit dans le fichier output_file au format JSON la liste des villes (triée alphabétiquement) et leur température minimum, maximum et moyenne.

Pour visualiser le fichier JSON obtenu, vous pouvez utiliser la commande jq (nom du packet Debian/Ubuntu: jq) :

$ cat output_file.csv |jq
[
  {
    "city": "Abha",
    "min": 10.1,
    "max": 27.6,
    "mean": 17.7
  },
  {
    "city": "Abidjan",
    "min": 17.9,
    "max": 34.7,
    "mean": 25.5
  },
  {
    "city": "Abu Dhabi",
    "min": 15.5,
    "max": 40.7,
    "mean": 28.2
  },
...
	    

Les fichiers de données fournis contient un nombre limité de villes. Un étudiant rusé pourrait être tenté d'en tirer partie (par exemple en pré-allouant un tableau cities suffisamment grand). Son programme risquerait alors de ne pas fonctionner avec un autre jeu de données. Faites-donc en sorte que vos solutions fonctionnent quel que soit le nombre de villes.

Optimisation

L'implémentation naïve que vous avez faite a probablement des performances médiocres. Le but de la suite du devoir est d'implémenter plusieurs stratégies d'optimisation et de les évaluer.

Parmi les stratégies qui semblent intéressantes, vous pouvez considérer:

Des méthodes pour accélérer la recherche d'une ville (par exemple en implémentant une hashmap ou un radix tree
Des méthodes pour accélérer la lecture du fichier d'entrée
La parallélisation des traitements (par exemple en utilisant des threads ou des processus)