s1-tp/S2/TPA/tp4.py

#!/usr/bin/python3
# -*- coding: utf-8 -*-

"""
TP AP1
Licence SESI 1ère année
Univ. Lille 1

tp4.py

TP 4 - Algorithmes de recherche

"""

__author__ = 'PREUD\'HOMME Geoffrey & BEAUSSART Jean-loup'
__date_creation__ = 'Tue, 24 Feb 2015 10:30:21 +0100'


def question(numero):
    """
    int → ∅
    Affiche la question en cours
    """
    print('\n***', 'Question', numero, '***')


def squestion(lettre):
    """
    int → ∅
    Affiche la sous-question en cours
    """
    print('\n%s)' % lettre)


question(1)  # Programmer recherches seq, seq triée, dicho


def seq(l, a, b, x):
    """
    list, int, int, a → (bool, int)
    Renvoie un tuple contenant un booléen indiquant si l'élément x est dans la liste l entre les
    bornes [a, b[, ainsi que sa position le cas échéant, -1 sinon, par méthode séquentielle.
    CU : l une liste, a et b des ints tels que 0 ≤ a < b ≤ len(l)
    """
    assert(type(l) == list), "l doit être une liste"
    assert(type(a) == type(b) == int), "a et b doivent être des ints"
    assert(0 <= a < b <= len(l)), "Il faut que 0 ≤ a < b ≤ len(l)"

    i = a

    while i < b and l[i] != x:
        i += 1
    if i < b:
        return (True, i)
    else:
        return (False, -1)


def seqTrie(l, a, b, x):
    """
    list, int, int, a → (bool, int)
    Renvoie un tuple contenant un booléen indiquant si l'élément x est dans la liste l triée entre
    les bornes [a, b[, ainsi que sa position le cas échéant, -1 sinon, par méthode séquentielle.
    CU : l une liste triée, a et b des ints tels que 0 ≤ a < b ≤ len(l)
    """
    assert(type(l) == list), "l doit être une liste triée"
    assert(type(a) == type(b) == int), "a et b doivent être des ints"
    assert(0 <= a < b <= len(l)), "Il faut que 0 ≤ a < b ≤ len(l)"

    i = a

    while i < b and l[i] < x:
        i += 1
    if i < b and l[i] == x:
        return (True, i)
    else:
        return (False, -1)


def dicho(l, a, b, x):
    """
    list, int, int, a → (bool, int)
    Renvoie un tuple contenant un booléen indiquant si l'élément x est dans la liste l triée entre
    les bornes [a, b[, ainsi que sa position le cas échéant, -1 sinon, par dichotomie.
    CU : l une liste, a et b des ints tels que 0 ≤ a < b ≤ len(l)
    """
    assert(type(l) == list), "l doit être une liste triée"
    assert(type(a) == type(b) == int), "a et b doivent être des ints"
    assert(0 <= a < b <= len(l)), "Il faut que 0 ≤ a < b ≤ len(l)"

    d = a
    f = b - 1
    while d < f:
        m = (d + f) // 2
        if l[m] < x:
            d = m + 1
        else:
            f = m
    est_dedans = x == l[d]
    return (est_dedans, d if est_dedans else -1)


def tricho(l, a, b, x):  # TODO
    """
    list, int, int, a → (bool, int)
    Renvoie un tuple contenant un booléen indiquant si l'élément x est dans la liste l triée entre
    les bornes [a, b[, ainsi que sa position le cas échéant, -1 sinon, par trichotomie.
    CU : l une liste, a et b des ints tels que 0 ≤ a < b ≤ len(l)
    """
    assert(type(l) == list), "l doit être une liste triée"
    assert(type(a) == type(b) == int), "a et b doivent être des ints"
    assert(0 <= a < b <= len(l)), "Il faut que 0 ≤ a < b ≤ len(l)"

    d = a
    f = b - 1
    while d < f:
        m1 = (d + f) // 3
        m2 = m1 * 2
        if l[m1] >= x:
            f = m1
        elif l[m2] >= x:
            d = m1 + 1
            f = m2
        else:
            d = m2 + 1
    est_dedans = x == l[d]
    return (est_dedans, d if x == l[d] else -1)

question(2)  # Utiliser LEXIQUE

from lexique import LEXIQUE

squestion('a')  # Vérifier que LEXIQUE est triée


def est_trie(l):
    """
    list → bool
    Indique si la liste l est triée dans l'ordre croissant
    """
    for i in range(len(l) - 1):
        if not l[i] < l[i + 1]:
            return False
    return True

print("Le test indiquant si LEXIQUE est trié retourne %s." % est_trie(LEXIQUE))

print("Le lexique est cependant bien trié, mais par ordre alphabétique, comprenant les accents dans\
cet ordre, ce qui n'est pas l'ordre \"naturel\" de Python, qui se base sur le codage des \
caractères")

print(
    "Création de LEXIQUE_TRIE, qui est une copie de LEXIQUE trié par l'ordre de Python")
LEXIQUE_TRIE = list(LEXIQUE)  # Crée une copie
LEXIQUE_TRIE.sort()

print("Le test indiquant si LEXIQUE_TRIE est trié retourne %s." %
      est_trie(LEXIQUE_TRIE))

squestion('b')
# Effectuer de nombreuses recherches dans LEXIQUE
# et comparer les temps d'éxécution selon les
# algorithmes utilisés

# Définition des éléments choisis pour la recherche
from random import randint, SystemRandom
from string import ascii_lowercase, ascii_uppercase


def motAleatoire(taille):
    """
    int → str
    Renvoie une mot aléatoire constitué de lettres (sans accent) minuscules et majuscules, et de
    chiffres
    """
    return ''.join(SystemRandom().choice(ascii_lowercase + ascii_uppercase)
                   for _ in range(taille))


def creerListeRecherche(l, dans, hors):
    """
    list, int, int → list
    Crée une liste de termes dont `dans` sont contenus dans `l`, et `hors` sont des mots générés
    aléatoirement.
    """
    elements = list()
    taille = len(l)
    for _ in range(dans):
        elements.append(l[randint(0, taille)])
    for _ in range(hors):
        while True:
            mot = motAleatoire(randint(2, 10))
            if mot not in l:
                break
        elements.append(mot)
    return elements

# Méthode de test des fonctions
from time import time
from sys import stdout


def mesure(methode, l, elements):
    """
    function, list, list → ∅
    Mesure le temps mis pour rechercher les éléments elements dans l en utilisant methode et affiche
    les résultats.
    """
    t = len(l)
    print("Test de la méthode %s..." % methode, end='')
    stdout.flush()
    debut = time()
    for e in elements:
        methode(l, 0, t, e)
    fin = time()
    print("\rLa méthode %s a pris %f secondes pour trouver %d éléments, soit %f secondes par \
élément." % (methode, fin - debut, len(elements), (fin - debut) / len(elements)))


if __name__ == '__main__':
    import sys
    if len(sys.argv) == 1:
        MESURE_DEFAUT = 500
        print("\nTest avec %d éléments pris exclusivement de LEXIQUE" %
              MESURE_DEFAUT)
        exclu = creerListeRecherche(LEXIQUE, MESURE_DEFAUT, 0)
        mesure(seq, LEXIQUE, exclu)
        mesure(seqTrie, LEXIQUE_TRIE, exclu)
        mesure(dicho, LEXIQUE_TRIE, exclu)

        PART_DEHORS = 0.2
        print("\nTest avec %d éléments dont %d sont dans LEXIQUE" %
              (MESURE_DEFAUT, (1 - PART_DEHORS) * MESURE_DEFAUT))
        exclu = creerListeRecherche(LEXIQUE, int(
            (1 - PART_DEHORS) * MESURE_DEFAUT), int(PART_DEHORS * MESURE_DEFAUT))
        mesure(seq, LEXIQUE, exclu)
        mesure(seqTrie, LEXIQUE_TRIE, exclu)
        mesure(dicho, LEXIQUE_TRIE, exclu)