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.
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.
Python, les listes, le hasard

Aujourd'hui, on fait du pseudo-aléatoire. Python est un langage de script très pratique lorsqu'on doit manipuler des listes (tableaux), ou des dictionnaires (tables de hachage). Voyons comment en très peu de code, on peut lier les listes avec le module random
.
Tri « sur place » de listes avec python
Je n'en avais jamais eu l'utilité jusqu'à présent, et ce n'est donc que récemment que j'ai découvert le tri de listes de python. Ça marche vite et bien, avec du code compact!
Pour en savoir plus et pour découvrir comment les supprimer ou les bloquer, voir : Notre politique de cookies
RSS
Les dates
L | M | M | J | V | S | D |
---|---|---|---|---|---|---|
« Sep | ||||||
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 |