Voici une petite recette \u00ab\u00a0force brute\u00a0\u00bb pour v\u00e9rifier qu’une liste est une sous-liste d’une autre. Je n’utilise pas les fonctions d’intersection des sets, car je consid\u00e8re mes listes avec leur ordre, et la possibilit\u00e9 de doublons.<\/p>\n
Je prends donc une fen\u00eatre glissante de la longueur de ma sous-liste potentielle, et je superpose la sous-liste au contenu de la fen\u00eatre courante pour v\u00e9rifier l’\u00e9galit\u00e9. Pour ce faire, je hache ma plus grande liste en morceaux en commen\u00e7ant \u00e0 chaque it\u00e9ration une case plus loin, tout simplement, et tout brutalement.<\/p>\n
Voici le code:<\/p>\n
\r\ndef is_sublist(sublist, superlist):\r\n '''\r\n Checks whether 'sublist' is a sublist of 'superlist'.\r\n Both arguments must be typed list or tuple.\r\n '''\r\n if not isinstance(sublist, (list, tuple)) or not isinstance(sublist, (list,tuple)):\r\n raise TypeError(\"Both 'sublist' and 'superlist' must be lists or tuples.\")\r\n # Return early if candidate sublist is longer than superlist\r\n if len(sublist) > len(superlist):\r\n return False\r\n else:\r\n for chunk in (superlist[i:i+len(sublist)] for i in range(0, len(superlist)-len(sublist)+1)): \r\n if chunk == sublist:\r\n return True\r\n return False\r\n<\/pre>\nOn se rend compte que dans le pire cas (pas de correspondance ou la correspondance est \u00e0 la fin), je vais avoir \u00e0 parcourir ma sur-liste enti\u00e8rement, voire plus que \u00e7a, selon l’impl\u00e9mentation du slicing (parcours jusqu’\u00e0 l’index de d\u00e9part, puis parcours jusqu’\u00e0 l’index de fin de la tranche). Il faudrait que je v\u00e9rifie la dite impl\u00e9mentation en CPython pour en avoir le c\u0153ur net.<\/p>\n
Ceci dit, pour les autres cas que le pire, notons que j’ai utilis\u00e9 un g\u00e9n\u00e9rateur
(superlist[i:\u2026] for i in \u2026)<\/code> et non une liste (avec des parenth\u00e8ses et non des crochets), de fa\u00e7on \u00e0 ne retourner les tranches qu’au moment o\u00f9 l’on en a besoin. La m\u00eame ligne avec des crochets [] constituerait la liste enti\u00e8re avant d’it\u00e9rer, alors que l\u00e0 je cr\u00e9e mes tranches au fur et \u00e0 mesure que j’avance.<\/p>\nJe n’ai pas encore r\u00e9fl\u00e9chi \u00e0 une m\u00e9thode plus optimale, mais vu que je souhaite rester dans le cas g\u00e9n\u00e9ral (non ordonn\u00e9, avec des doublons possibles, etc.), j’ai l’impression qu’on ne pourra pas faire moins complexe. Si vous avez une id\u00e9e, n’h\u00e9sitez pas \u00e0 laisser un commentaire.<\/p>\n","protected":false},"excerpt":{"rendered":"
Voici une petite recette \u00ab\u00a0force brute\u00a0\u00bb pour v\u00e9rifier qu’une liste est une sous-liste d’une autre. Je n’utilise pas les fonctions d’intersection des sets, car je consid\u00e8re mes listes avec leur ordre, et la possibilit\u00e9...<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":"","jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[4],"tags":[56,21,254,38,306,305],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/posts\/1236"}],"collection":[{"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/comments?post=1236"}],"version-history":[{"count":10,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/posts\/1236\/revisions"}],"predecessor-version":[{"id":1247,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/posts\/1236\/revisions\/1247"}],"wp:attachment":[{"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/media?parent=1236"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/categories?post=1236"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/saladtomatonion.com\/blog\/wp-json\/wp\/v2\/tags?post=1236"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}