# TD6: Listes, Dictionnaires
## Préliminaires
#### Objectif
Plusieurs structures de données existent au sein de Python et ont chacune **leurs avantages** (ordre maintenu, garanti d'unicité, ...) et les **performances d'accès** à un élément liées.
Nous allons d'abord utiliser la fonction de Fibonacci pour comparer une implémentation **récursive classique**, **récursive terminale** et **récursive avec un dictionnaire**.
#### Fonctions utiles
- **Dictionnaire :**
```python
# Création
dico = {'cle0': 0}
# Ajout d'éléments
dico['cle1'] = 14 # valeur
dico['cle2'] = 15
# Accès à un élément
dico['cle1']
```
- **Graphes avec Python :**
```python
import matplotlib.pyplot as plt
plt.figure()
plt.semilogy(x, y) # ou plt.plot(x, y)
plt.xlabel('Label de X')
plt.ylabel('Label de Y')
plt.title('Titre')
plt.show()
```
- **Calcul du temps :**
```python
import time
beginning = time.time()
# ou time.time_ns()
# ou time.perf_counter_ns()
# Exécution de la fonction à mesurer
end = time.time() - beginning
```
## Première Partie : Fibonacci
Mesure de la performance de **trois** fonctions de Fibonacci différentes :
1. **Récursive classique :**
```python
def fibo_rec(n):
"""
Fonction Fibonacci récursive. Complexité exponentielle.
"""
if n == 0:
return 1
elif n == 1:
return 1
else:
return fibo_rec(n-1) + fibo_rec(n-2)
```
---
2. **Récursive terminale :**
```python
def fib_rec_term(n, a=1, b=1):
"""
Fonction Fibonacci récursive terminale
"""
if n == 0 :
return a
elif n == 1 :
return b
else :
return fib_rec_term(n - 1, b, a + b)
```
---
3. **Récursive avec dictionnaire :**
**Solution :**
```python
def fib_dict(n, dico={0:0,1:1}):
if n not in dico :
dico[n]= fib_dict(n-1, dico) + fib_dict(n-2, dico)
return dico[n]
```
---
Écrire une fonction `test_fib(fct, nb=30)` qui prend comme argument la fonction à tester et le nombre d'itérations à lui appliquer et qui renvoie la liste de numéros de terme et les temps associés.
Par exemple, `test_fib(fct=fib, nb=4)` renvoie `([0, 1, 2, 3, 4],[0.12, 0.13, 0.14, 0.15])`. Vous pouvez ensuite tracer les graphes associés à l'aide des fonctions données en début de TD.
**Solution :**
```python
def test_fib(fct=fib_rec, nb=30):
ind = []
tps = []
for i in range(nb):
ind.append(i)
t0 = time.time_ns()
fct(i)
tps.append(time.time_ns() - t0)
return ind, tps
```
## Deuxième Partie : Performance des structures de donnees
### Préliminaires
#### Objectif
On veut maintenant comparer quatre structures de données différentes (**listes, ensembles, dictionnaires** et **arbres binaires de recherche**). Pour pouvoir les comparer, notre méthode consistera à **comptabiliser le temps passé à trouver tous les mots d'un premier fichier texte présents dans un second**.
Le premier fichier sera le texte court à trouver dans le second, les mots du vocabulaire anglais (`dico_gb.txt`). On stocke le premier dans **une liste** et le second dans la structure de données que l'on souhaite tester.
**Trois fichiers** sont donnés:
- `dico_gb.txt` le dictionnaire de mots anglais
- `simple_grail.txt` le texte réduit à tester
- `grail.txt` le texte complet à tester
#### Fonctions utiles
- **Lecture de fichier :**
```python
with open(filename) as f:
lines = [line.strip() for line in f]
# Équivalent à :
# for line in f:
# lines.append(line.strip())
```
- **Expression régulière de détection de mot :**
```python
import re
test_str = "Bonjour je m'appelle toto"
# Détection des séparateurs de mots
sepwords = re.compile("[^a-zA-Z']+")
sepwords.split(test_str)
>>> ['Bonjour', 'je', "m'appelle", 'toto']
```
- **Différentes structures :**
- **`Set`**
```python
set_dict = set(list_dict)
```
- **`AFLTree`**
```python
avl_dict = FastAVLTree()
for word in list_dict:
avl_dict.insert(word, None)
```
- **`RBTree`**
```python
rb_dict = FastRBTree()
for word in list_dict:
rb_dict.insert(word, None)
```
### Déroulement
1. Écrire une fonction `lecture_dico(nom, n)` qui lit le fichier donné et stocke les n premiers mots dans une liste. *Note: il y a un mot par ligne donc pas besoin d'utiliser la regex !*
<!--
**Solution :**
```python
def lecture_dico(nom, n):
with open(nom) as f:
voc_file = [line.strip() for line in f]
return voc_file[:n]
```
-->
2. Écrire une fonction `lecture_texte(nom)` qui lit le fichier, sépare le texte mot à mot et stocke ces mots dans une liste.
<!--
**Solution :**
```python
def lecture_texte(nom):
sepwords = re.compile("[^a-zA-Z']+")
ref = []
with open(nom) as f:
for line in f:
ref += sepwords.split(line.strip()):
return ref
```
-->
3. Écrire une fonction `decompte(dico, texte)` qui compte le nombre de mot du texte trouvé dans le dictionnaire donné.
<!--
**Solution :**
```python
def decompte(dico, texte):
mots_trouves = 0
for mot in texte:
if mot in dico:
# Décommenter le print pour voir les mots trouvés
# print('Mot ' + str(mot_texte) + ' trouvé !')
mots_trouves += 1
return mots_trouves
```
-->
4. Essayer le décompte avec les structures de `set`, `FastAVLTree` et `FastRBTree`.
<!--
**Solution :**
```python
# Ensemble
set_dict = set(list_dict)
# Arbre binaire
avl_dict = FastAVLTree()
for word in list_dict:
avl_dict.insert(word, None)
# Arbre rouge noir
rb_dict = FastRBTree()
for word in list_dict:
rb_dict.insert(word, None)
```
-->
5. Afficher les résultats pour une taille de vocabulaire de 100, 300, 1000, 3000, 10000, 30000, 100000, et tous les mots (-1). Vous pouvez afficher un graphique avec en abscisse les différentes tailles et les temps associés en ordonnée.
<!--
**Solution :**
```python
taille_voc = [100, 300, 1000, 3000, 10000, 30000, 100000, -1]
mesures_temps = []
for taille in taille_voc:
t0 = time.time_ns() # ou time.clock()
# FONCTION DE DECOMPTE
t1 = time.time_ns() # ou time.clock()
mesures_temps.append(t1-t0)
plt.xlabel('Taille du vocabulaire anglais testé (mots)')
plt.ylabel('Temps mesuré (ns)')
plt.grid()
plt.plot(taille_voc, mesures_temps)
plt.show()
``` -->
6. Écrire une fonction `decompte_cnt(fichier_voc, fichier_txt, n)` qui utilise un compteur de type `collections.Counter` pour déterminer les 10 mots les plus fréquents ainsi que la fréquence de chacun.
<!--
**Solution :**
```python
def decompte_cnt(fichier_voc, fichier_texte, n):
mots_trouves = 0
cnt = Counter()
voc = lecture_dico(fichier_voc, n)
texte = lecture_texte(fichier_texte)
for mot in texte:
if mot in voc:
cnt[mot] += 1
return cnt.most_commons(10)
```
-->
## Troisième Partie : Fonction de Takeuchi
Écrire la fonction de Takeuchi `tak(x, y, z)` utilisant un dictionnaire pour stocker les résultats.
<!--
**Solution :**
```python
def tak(x, y, z, opt=True):
"""Fonction de Tekeuchi.
Si opt est vrai, utilise un dictionnaire pour mémoriser les résultats.
"""
# Dictionnaire en variable globale
# Il est également possible de le passer en paramètre.
global dic_tak
if not opt or (x, y, z) not in dic_tak:
if y < x:
dic_tak[(x, y, z)] = tak(
tak(x-1, y, z, opt),
tak(y-1, z, x, opt),
tak(z-1, x, y, opt), opt
)
else:
dic_tak[(x, y, z)] = y
return dic_tak[(x, y, z)]
if __name__ == '__main__':
nmax = 42
t0 = time.time()
dic_tak = dict()
for i in range(nmax):
for j in range(nmax):
for k in range(nmax):
print(i, j, k, tak(i, j, k, opt=True))
print(time.time() - t0)
```
-->
###### tags: `python`
Sign in with Wallet
Connect another wallet