Comment déterminer efficacement si une sous-liste existe en Python ?

Détection de la présence d'une sous-liste en Python

La tâche à accomplir est de concevoir une fonction qui vérifie l'existence d'une sous-liste au sein d'une liste plus grande. Étant donné deux listes, l'une comme liste plus grande (list1) et l'autre comme sous-liste potentielle (list2), la fonction doit déterminer si list2 est effectivement une sous-liste de list1.

Implémentation de la fonction

Python fournit une fonction polyvalente nommée any() qui peut être exploitée à cette fin. L'extrait de code suivant montre comment construire une fonction qui utilise any() :

<code class="python">def sublist_exists(lst, sublst):
    n = len(sublst)
    return any((sublst == lst[i:i+n]) for i in range(len(lst)-n+1))</code>

Cette fonction analyse méticuleusement la plus grande liste (lst) en parcourant ses éléments un par un. Pour chaque élément d'index i, il extrait une sous-liste contiguë de longueur n et la compare à la sous-liste potentielle (sublst). Si une correspondance est détectée, la fonction renvoie immédiatement True, indiquant la présence de la sous-liste. Ce processus se poursuit jusqu'à ce qu'une correspondance soit trouvée ou que la liste entière soit épuisée, auquel cas la fonction renvoie False.

Considérations sur les performances

Il est important de noter que la complexité temporelle de cette fonction est O(m*n), où m est la longueur de la plus grande liste et n est la longueur de la sous-liste potentielle. Pour chaque itération, la fonction effectue une opération de comparaison de sous-listes et le nombre d'itérations est limité par la différence entre m et n plus un.

Exemple d'utilisation

Voyons illustrez l'utilisation de la fonction sublist_exists avec les exemples fournis :

<code class="python">>>> sublist_exists([1,0,1,1,1,0,0], [1,1,1])
True

>>> sublist_exists([1,0,1,0,1,0,1], [1,1,1])
False</code>

Dans le premier exemple, [1,1,1] est bien une sous-liste de la plus grande liste, donc la fonction renvoie True. Dans le deuxième exemple, [1,1,1] n'apparaît pas dans la liste plus grande, donc la fonction renvoie False.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!