Solution du problème Compact¶

Vous trouverez ici la solution pour l'exercice suivant:

Exercice de base¶

Comment enlever des items successifs egaux dans une liste?

Approche naive¶

On crée une liste pour le retour, on met le premier element de la liste en entrée, on itere sur la liste et on ajoute un item que lorsqu'il est different du dernier element de la liste de retour.

def compact(items):
    result = [items[0]]
    for item in items:
        if item != result[-1]:
            result.append(item)
    return result

L'élément -1 d'une liste est le dernier de la liste, -2 l'avant dernier, etc.

Tout va bien, non? Et bien non, on a fait une grosse suposition, qu'il y a au moins un item dans la liste. S'il n'y en a pas, alors notre solution ne fonctionnera pas.

Protègeons la donc un peu contre ce problème:

def compact(items):
    try:
        result = items[0]
    except IndexError:
        return []
    for item in items:
        if item != result[-1]:
            result.append(item)
    return result

Et voila qui passe tous les tests de base!

Bonus 1¶

Il faut maintenant que la fonction prenne n'importe quel type d'iterable.

Pour cela il va falloir utiliser in iterateur pour cela. Par contre, nous allons pouvoir dire adieu à l'acces ou premier élément en utilisant un index.

Un iterateur est un objet qui permet d'itérer sur un iterable. c'est ce qui est utilisé dans les boucles for par exemple. Un iterateur ne permet essentielement qu'une chose: obtenir le prochain element d'un iterable en utilisant la fonction next().

Un iterateur permet d'iterer sur des listes, des chaines de charactere, et meme sur un autre iterateur. Ce tour de passe passe est rendu possible par le fait qu'un iterateur est son propre iterateur. Ainsi quel que soit l'objet passé en parametre de la fonction, si on en prend un iterateur, alors on pourra faire notre filtre.

Conservons la même logique:

def compact(items):
    iterator = iter(items)
    result = list()
    try:
        result.append(next(iterator))
    except StopIteration:
        return result
    for item in iterator:
        if item != result[-1]:
            result.append(item)
    return result

Bonus 2¶

Il faut maintenant que notre fonction retourne elle même un iterable et non plus une liste simple.

Tout d'abbord un petit mot sur l'utilité de cette requête. Imaginons que la l'iterable qu'on nous passe en parametre est issu d'une base de données avec quelques gigas de data. Si on nous donnait les données sous forme de liste, alors nous aurions plusieurs gigas de memoire utilisés tout le long du processus.

Si de plus nous stockons le résultat sous forme de liste que nous retournerons après traitement, alors nous avons simplement multiplié par deux l'empreinte mémoire de notre application, et potentiellement, si nous utilisons trop de mémoire, notre application a pris du plomb dans l'aile sur les performances, voir même nous avons un crash si nous depassons la memoire du systeme.

Si on nous passe un iterable, cela permet de limiter la memoire occupée a simplement un seul item a la fois. Mais nous stockons toujours une liste, et potentiellement des gigas de données pour pas grand chose.

Si par contre nous faisons en sorte de ne pas retourner une liste, mais un iterable, alors nous n'aurons donc plus besoin que de quelques octets de memoire, et cela même pour traiter des tera de data...

Ceci étant éclairci, allons-y pour rendre notre fonction iterable. Pour cela nous allons utiliser le mot clef yield. Celui-ci fait qu'une fonction devient un générateur. Dès que l'on rencontre le mot clef yield la fonction se met sur pause et retourne la valeur après le yield.

Les deux codes suivants se comportent de façon identique:

(x**3 for x in range(5))

def my_function():
    for i in range(5):
        yield i**3

Et pour notre exercice;

def compact(items):
    iterator = iter(items)
    previous = None
    try:
        previous = next(iterator)
        yield previous
    except StopIteration:
        return
    for item in iterator:
        if item != previous:
            previous = item
            yield item
    return