SaladTomatOnion Le blog qui mange trois fruits et légumes

16Août/160

Vérifier qu’une liste est une sous-liste d’une autre en python

Voici une petite recette "force brute" pour vérifier qu'une liste est une sous-liste d'une autre. Je n'utilise pas les fonctions d'intersection des sets, car je considère mes listes avec leur ordre, et la possibilité de doublons.

Je prends donc une fenêtre glissante de la longueur de ma sous-liste potentielle, et je superpose la sous-liste au contenu de la fenêtre courante pour vérifier l'égalité. Pour ce faire, je hache ma plus grande liste en morceaux en commençant à chaque itération une case plus loin, tout simplement, et tout brutalement.

Voici le code:

def is_sublist(sublist, superlist):
    '''
    Checks whether 'sublist' is a sublist of 'superlist'.
    Both arguments must be typed list or tuple.
    '''
    if not isinstance(sublist, (list, tuple)) or not isinstance(sublist, (list,tuple)):
        raise TypeError("Both 'sublist' and 'superlist' must be lists or tuples.")
    # Return early if candidate sublist is longer than superlist
    if len(sublist) > len(superlist):
        return False
    else:
        for chunk in (superlist[i:i+len(sublist)] for i in range(0, len(superlist)-len(sublist)+1)): 
            if chunk == sublist:
                return True
        return False

On se rend compte que dans le pire cas (pas de correspondance ou la correspondance est à la fin), je vais avoir à parcourir ma sur-liste entièrement, voire plus que ça, selon l'implémentation du slicing (parcours jusqu'à l'index de départ, puis parcours jusqu'à l'index de fin de la tranche). Il faudrait que je vérifie la dite implémentation en CPython pour en avoir le cœur net.

Ceci dit, pour les autres cas que le pire, notons que j'ai utilisé un générateur (superlist[i:…] for i in …) et non une liste (avec des parenthèses et non des crochets), de façon à ne retourner les tranches qu'au moment où l'on en a besoin. La même ligne avec des crochets [] constituerait la liste entière avant d'itérer, alors que là je crée mes tranches au fur et à mesure que j'avance.

Je n'ai pas encore réfléchi à une méthode plus optimale, mais vu que je souhaite rester dans le cas général (non ordonné, avec des doublons possibles, etc.), j'ai l'impression qu'on ne pourra pas faire moins complexe. Si vous avez une idée, n'hésitez pas à laisser un commentaire.

18Déc/140

Une utilisation étonnante du mot-clé « or » en python

Aujourd'hui, on écrit du code compact. Savez-vous qu'il est possible d'utiliser le mot clé python or pour une affectation de valeur conditionnelle simple et élégante?

Lorsque l'on souhaite affecter conditionnellement des valeurs, on aura tendance à utiliser des structures if. Ici on va s'intéresser au cas où la valeur reçue est None, qu'on souhaite dans ce cas remplacer par une valeur par défaut autre.

val = get_some_value()
if val is None:
   val = 'default'
some_function(val)

Mais cela pourrait s'écrire bien plus simplement de la façon suivante:

val = get_some_value()
some_function(val or 'default')

Par quel miracle? Simplement, lorsqu'on utilise l'opération booléene or, python évalue la fonction __nonzero__ (ou bien __bool__ en Python 3) de l'object "de gauche". Si cette évaluation retourne False, l'objet de "droite" est choisi.

Il se trouve que None, "", 0, [] ou encore {} par exemple sont tous évalués à False.

Pour complément, lorsque qu'un objet est précédé de if, son évaluation booléenne est aussi exécutée.
Cela permet entre autres d'écrire:

my_list = get_list()
if my_list:
    # ... do things

au lieu de:

my_list = get_list()
if my_list is not None and len(my_list) > 0:
    # ...

Élégant, non? Il m'arrive souvent d'implémenter cette fonction __nonzero__ dans mes classes, lorsque ça a du sens. Par exemple, une classe représentant un fichier pourrait être équivalent à True si le fichier existe.

16Déc/143

Mesurer le temps d’exécution de code en python

Aujourd'hui, on chronomètre. J'imagine que, comme pour moi, c'est un besoin pour beaucoup que de savoir combien de temps tel ou tel bout de code prend à se dérouler. Je vous propose de voir comment j'ai fait.


25Avr/130

Grouper des objets selon un certain critère en python

Ajourd'hui, on fait des catégories. J'ai eu besoin d'établir des listes d'objets selon un certain critère, et retrouver mes listes par la valeur du critère. Par exemple, dans une liste d'objet, grouper les fruits, les animaux, et les machines-outils.

9Août/120

Faire du FTP à travers un proxy en python

Aujourd'hui, on transfère des fichiers par un protocole bien nommé! J'ai voulu utiliser la bibliothèque python ftplib pour joindre un serveur externe à mon travail, et voici comment j'ai fait.

Afficher les boutons de partage
Masquer les boutons de partage