Connexion élèves

Choisir le(s) module(s) à installer :

Tri de données en tables

Comme vous l'avez peut être remarqué les tableaux que l'on obtient lors des recherches dans les données ne sont pas ordonnées, elle nous parviennent dans un ordre lié à l'ordre dans lequel les données sont stockées dans le fichier.
On peut aussi remarquer que l'on pourrait trier les données pour optimiser la recherche dans le données en utilisant la dichotomie.
Il peut donc être nécessaire de trier les données.

Exemple de tri selon les superficies des pays

La méthode sort() de python

Il existe dans python une fonction qui trie des listes en utilisant des techniques algorithmiques mixtes et efficaces.
Vous pouvez tester cette fonction grâce au code ci dessous : 
				
l=[1, 5, 8, 2, 3, 4, 7]
l.sort()
print(l)
On remarque ici que la liste l est codée "en place".
En effet, après l'application de la fonction sort() (une telle fonction se nomme également méthode) à la liste l, la liste l est modifiée.
  1. Appliquer la fonction sort() à la liste de dictionnaires obtenue en important les données en table.
  2. Analyser l'erreur obtenue, quelle problème se pose ici ?
# codez ces questions ici

SOLUTION

Le critère de tri

On remarque donc ici que pour utiliser la fonction sort() de python, à une liste de dictionnaire il va falloir préciser le critère de ce tri : la clef sur laquelle opérer le tri.
La fonction sort() peut admettre un paramètre key qui désignera une fonction qui précisera quelle comparaison doit être faire pour réaliser le tri.
Cette fonction sera appliquée à chaque élément du tableau lors du tri et c'est sur la valeur renvoyée par cette fonction que s'effectueront les comparaisons lors du tri.
par exemple : 
				
l=['ab','a','abba','bbb','abbabba']
l.sort(key=len)
triera la liste l par longueur de chaîne de caractère (la fonction len ser appliquée à chaque élément de la liste l pour effectuer le tri).

Carte non géographique présentant les pays et leur population
Nous allons donc tenter de trier les pays du tableau de dictionnaires précédent obtenu en important les données en table du fichier countries.csv par ordre de population. Pour cela :
  1. Effectuer ce tri à partir du code : 
    				
def cle_population(p):
   return p['population']

dicoPays.sort(key=cle_population)
  2. Afficher les 3 premiers éléments du dictionnaire. Cela vous semble-t-il cohérent ?
  3. Corriger le code précédent pour réaliser un tri correct.
  4. Compléter votre code pour permettre d'afficher les noms des pays de la zone Euro par ordre de population croissante
  5. Modifier votre code pour permettre d'afficher les noms des pays de la zone Euro par ordre de superficie croissante
# codez ces questions ici

SOLUTION


On peut également tri par ordre décroissant en utilisant le paramètre reverse de la fonction sort() : 
				
dicoPays.sort(key=cle_population, reverse=True)

Optimisation du tri

On peut remarquer ici que l'on a choisit de trier les données avant d'effectuer une recherche.
Dans le cas où on traite une très grande quantité de donnée il est plus judicieux d'effectuer une recherche et d'ensuite trier les résultats.
La même méthode est bien sur applicable.
Vous trouverez ci-dessous un code complet qui permet de tester l'efficacité de chaque technique :
import csv from timeit import timeit def index_dico(nomDeFichier): tab=[] with open(nomDeFichier,'r',encoding='utf-8') as f: lecteur=csv.DictReader(f,delimiter=',') for row in lecteur: tab.append(dict(row)) return tab def recherche(donnees,clef_rech,val_rech): return [p for p in donnees if p[clef_rech]==val_rech] def cle_population(p): return int(p['population']) def triAvant(list): list.sort(key=cle_population) recherche(dicoPays,'currency_code','EUR') def triApres(list): resultats = recherche(dicoPays,'currency_code','EUR') resultats.sort(key=cle_population) ##################### #programme principal ##################### dicoPays=index_dico('countries.csv') #affichage des durées d'exécution des deux techniques (tri avant ou après) print('avant : ',timeit(stmt='triAvant(dicoPays)', globals=globals(), number=1000)) print('apres : ',timeit(stmt='triApres(dicoPays)', globals=globals(), number=1000))
Si l'on analyse ce code, on retrouve les éléments construits prédemment : indexation des données recherche et tri. Deux fonctions ont été ajoutées : triAvant() et triApres() qui seront ensuite appelées parle module timeit.
Le module timeit

Le module timeit de python permet de mesurer la durée d'exécution dune portion de code python.
Comme ce genre de mesure peut être influencée par l'activité du processeur sur d'autres taches système (gestion des fenêtres, accès réseau...), le module permet d'effectuer successivement un grand nombre de tests. C'est alors le temps total qui est affiché. Nous effectuerons ici 1000 tests successifs !
  1. Exécuter le code ci-dessus
  2. Quel est l'ordre de grandeur de l'écart obtenu ?
  3. Quel est l'ordre de grandeur du nombre d'enregistrements dans la table initiale ?
  4. Comment va évoluer cet écart si la quantité de données initiale augmente (une base de donnée moderne peut gérer des milliards d'entrées).

SOLUTION