1 Introduction

Le but de cet exercice est de manipuler en C++ des vecteurs, des arbres binaires de recherche et des hash map en s’inspirant du One Billion Row Challenge. Comme expliqué dans l’un des projets C de l’UE CSC4103, ce challenge de programmation consiste à traiter le plus rapidement possible un fichier contenant une grande quantité de données, chaque ligne contenant un nom de ville et une température :

Riga;0.3
Skopje;6.8
Tokyo;22.1
Riga;-3.3
Riga;7.1

En sortie, le programme doit afficher la liste des villes, triées alphabétiquement, et la température minimum, maximum, et moyenne de chaque ville au format JSON :

[
{"city": "Riga", "min": -3.3, "max": 7.1, "mean": 1.4},
{"city": "Skopje", "min": 6.8, "max": 6.8, "mean": 6.8},
{"city": "Tokyo", "min": 22.1, "max": 22.1, "mean": 22.1}
]

2 Analyse des données avec un vecteur (0h20)

• Décompressez l’archive OneBillionRowChallengeSimplifie.zip dans le répertoire de votre choix (par exemple, dans C:\CPP).
• Exploitez le canevas de projet obtenu selon la procédure Construire un projet C++ avec cmake.
• Dans src/core/my_main.cpp, modifiez la ligne const vector<data_t> data; de manière à initialiser data avec les 5 paires ville/température ci-dessus.

const vector<data_t> data{{"Riga",0.3},{"Skopje",6.8},{"Tokyo",22.1},{"Riga",-3.3},{"Riga",7.1}};

• Corrigez src/core/analyze_data.h pour que la passage du paramètre data à process_data_with_vector() soit le plus pertinent possible.
• Dans src/core/analyze_data.cpp, complétez la fonction process_data_with_vector() pour qu’elle fasse le travail attendu.
• Exécutez votre code et vérifiez que sa sortie est le “JSON” ci-dessus.
• Plutôt que de faire une vérification visuelle de la sortie de main() :
  1. Modifiez le fichier src/test/unitTests.cpp pour remplacer l’instruction EXPECT_TRUE(false); par un EXPECT_EQ() vérifiant que result_ref est égale à la chaîne renvoyée par process_data_with_vector(data_for_tests).
  2. Exécutez vos tests unitaires pour vérifier que votre test passe.
• Attendez la prochaine séance pour faire la suite de ce TP.

3 Analyse des données avec un arbre binaire de recherche (0h15)

• Dans src/code/analyze_data.h, ajoutez la déclaration d’une fonction process_data_with_binary_tree.
• Implantez cette fonction dans src/code/analyze_data.cpp. NB : Avez-vous besoin de faire explicitement un tri comme vous en aviez eu besoin pour process_data_with_vector()) ?
• Dans src/code/unitTests.cpp, créez un test TEST(TestAnalyseData, Test_process_data_with_binary_tree) pour vérifier que votre implantation est correcte.

4 Analyse des données avec une table de hash (0h15)

• Dans src/code/analyze_data.h, ajoutez la déclaration d’une fonction process_data_with_hash_map.
• Implantez cette fonction dans src/code/analyze_data.cpp.
• Dans src/code/unitTests.cpp, créez un test TEST(TestAnalyseData, Test_process_data_with_hash_map) pour vérifier que votre implantation est correcte.

5 Conclusion

Corrigé (à exploiter selon la procédure Construire un projet C++ avec cmake).

Cet exercice vous a permis de manipuler trois conteneurs C++, sans vous intéresser aux performances obtenues. L’étude de ces performances (qui est au cœur du One Billion Row Challenge) sera probablement approfondie dans un exercice lors du cours JIN Sensibilisation à la programmation concurrente (multitâche) à travers C++ de 3ème année. Toutefois, vous pouvez déjà faire des mesures avec le TP optionnel Quelques manipulations sur les vecteurs.