SaladTomatOnion Le blog qui mange trois fruits et légumes

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.