Favicon
NSI Première

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és; ces données nous parviennent dans un ordre lié à l'ordre dans lequel elles stockées dans le fichier.
On peut aussi remarquer que l'on pourrait trier les données pour optimiser la recherche dans les 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 les tableaux 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 le tableau l est trié "en place".
En effet, après l'application de la fonction sort ( une telle fonction se nomme également méthode ) au tableau l, celui-ci est modifié.

Un algorithme qui ne trie pas en place crée un nouveau tableau trié, celui d’origine n'est pas modifié.

  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, à un tableau de dictionnaires, il va falloir préciser le critère de ce tri, c'est à dire ici la clef selon 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 le tableau l selon la longueur des éléments de ce tableau (la fonction len sera 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 ci-dessous.
  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
def cle_population(p): return p['population'] tabDico.sort(key = cle_population)

SOLUTION

On peut également trier 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 seulement trier les résultats.

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(dico): dico.sort(key = cle_population) recherche(dicoPays, 'currency_code', 'EUR') def triApres(dico): resultats = recherche(dico,'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écé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 d'une 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 !

Exécuter le code ci-dessus. 1. Quel est l'ordre de grandeur de l'écart obtenu ? 2. Quel est l'ordre de grandeur du nombre d'enregistrements dans la table initiale ? 3. 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