Solution du problème Tail¶

Vous trouverez ici la solution pour l'exercice suivant:

Exercice de base¶

Il va falloir trouver un moyen de retourner les N derniers éléments d'une séquence seq.

On peut faire cela en python avec du slicing: seq[-N:], cela retourne la sous séquence composée des N derniers élements de seq.

Voici donc une première solution au problème de base:

def tail(seq, n):
    return seq[-n:]

Cela ne marche pas pour tous les cas, parce que le type de retour sera le même type que seq. Il faut donc toujours le configurer en liste.

def tail(seq, n):
    return list(seq[-n:])

Nouvelle déconvenue, ça ne fonctionne pas si N est égale à zero, et pour cause: seq[-0:] retourne l'intégralité de la séquence, Il faut donc la protéger ainsi:

def tail(seq, n):
    if n == 0:
        return list()
    return list(seq[-n:])

Bonus 1¶

Faire en sorte que si N est négatif, on retourne une liste vide. En reprennant le code précédent, rien de plus simple:

def tail(seq, n):
    if n <= 0:
        return list()
    return list(seq[-n:])

Ce bonus était plus que facile, voyons le second...

Bonus 2¶

Nous devons faire en sorte de pouvoir accepter n'importe quel type, pas seulement les séquence mais aussi les itérateur.

Problème ça ne marche pas. Et oui, le slicing, ne foncitonne pas avec les itérateurs, car ils ne sont pas indexables.

On pourrait convertir l'iterateur en entrée en liste afin de pouvoir faire fonctionner le code précédent:

def tail(seq, n):
    if n <= 0:
        return list()
    return list(list(seq)[-n:])

NB: d'un point de vue performance, on est au niveau de la demie seconde sur mon netbook; mais si l'iterateur était trop gros, on aurait tout chargé en memoire et aurait obtenu un crash...

Une autre approche: créer une liste résultat et conserver les N derniers éléments lus en enlevant les premiers lorsqu'on ajoute un nouvel élément en fin.

def tail(seq, n):
    result = list()
    if n <= 0:
        return result
    for item in seq:
        result.append(item)
        if len(result) > n:
            result.pop(0)
    return result

NB: d'un point de vue mémoire, plus de soucis, mais les performances en prennet un coup: 5s sur mon netbook...

Ça marche, mais cela semble non efficace, et ça l'est! Effectivement les listes ne sont pas optimisées pour faire beaucoup d'ajouts en queue et de retraits en fin.

Pour palier ce problème, nous pouvons utiliser une structure optimisée pour: deque (Double Ended QUEue). Elle se trouve (comme beaucoups) dans le module collections livré de base avec Python.

Son role: permetre des ajouts et suppressions d'éléments en tête et en fin de queue avec une complexité en O(1) au lieu de O(n) pour une liste simple. La deque possède une taille maximale que l'on peut stipuler, au dela de laquelle, tout ajout entraine une suppression de l'autre coté de la queue. Si on ne stipule pas de taille, la taille est documentée comme arbitraire.

Pour cet exercice, stipuler une taille à N nous donne le comportement voulu sans effort... Il ne nous reste plus qu'a ajouter les elements de l'iterateur au fur et a mesure dans la deque. A la fin de l'iterateur, il suffira simplement de retourner la deque convertie en liste.

from collections import deque
def tail(seq, n):
    if n <= 0:
        return []
    result = deque(maxlen=n)
    for item in seq:
        result.append(item)
    return list(result)

NB: les performances sont bien meilleurs avec 1.5s...

Le constructeur d'une deque permet même de prendre un itérateur en parametre pour se pré-remplire, ce qui simplifie encore la solution:

from collections import deque
def tail(seq, n):
    if n <= 0:
        return []
    return list(deque(seq, maxlen=n))

En ce qui concerne les performances, là on est au niveau de la premiere solution 0.5s et on est bon d'un point de vue mémoire.

Bonus 3¶

Pourquoi cela ne vaut-il pas la peine d'en faire un generateur?

D'abord, pourquoi on fait des générateurs? Essentielement pour 2 raisons:

empreinte mémoire limitée au maximum
résultat au fil de l'eau

Est-ce utile ici:

mémoire: on a de toute façons stocké les N derniers éléments de l'iterable en mémoire: interet 0
resultat continue: et bien on est obligés d'aller au bout de l'iterateur avant de donner la reponse: interet 0

Et voila!