Recherche d'un élément dans une liste

Exercice 2 du TP 1

Python a l'avantage de proposer une syntaxe homogène entre des types de donnés variés. Nous nous intéressons aux séquences telles que

les list, comme L = [4, 21, 8, 9]
les tuple, comme L = (4, 21, 8, 9) – semblables aux list mais non modifiables,
les str, comme L = "blablabla"
les dict, comme L = {"a":12, "b":32}

Ces données sont

indexable – subscriptable – on peut écrire par exemple L[1],
et ils sont itérables, on peut écrire for item in L:
remarque : dans le cas d'un dict, ce sont les clés qui sont parcourues.

On suppose que l'on a une séquence, par exemple ici une liste L, et un objet a.

On veut savoir si a est élément de la séquence.

Python dispose d'un mot clé pour cela, a in L qui vaut True si a est bien élément de L et False sinon. Mais nous ne l'utilisons pas ici. Nous avons trois bonnes raisons à cela :

on apprend en s'entraînant sur des choses simples,
il y a de nombreux cas où l'utilisation de in sera impossible
par exemple si on veut savoir si on peut trouver a in L tel que f(a) == A, le mot clé in n'est d'aucun secours.
il peut sembler, quand on écrit a in L que l'exécution est très rapide puisque cela se fait en une ligne. Cette écriture masque le fait que Python a besoin de parcourir L pour donner la réponse. En détaillant la recherche, en nous abstenant d'utiliser ce in, nous mettons cette recherche en évidence.

De plus, en Python, les boucles for utilisent forcément in avec un sens proche. Vous pouvez bien sûr utiliser ce in.

Notre fonction sera est_element. Elle prend deux paramètres, dans cet ordre, une liste L et un objet a.

Question 1

Implémenter la fonction est_element en Python.

Aide : vous pouvez, à l'aide d'une boucle, parcourir les éléments de L jusqu'à trouver la valeur recherchée. Si la recherche aboutit, on peut renvoyer True. Si on arrive au bouts des éléments de L sans avoir trouvé la valeur, on peut renvoyer False. Il s'agit d'une recherche séquentielle.

Tester la fonction avec quelques exemples, qui explorent de manière pertinente tous les cas qui peuvent se présenter :

cas où la donnée recherchée est absente,
cas où elle est présente une fois,
cas où la donnée est présente plusieurs fois,
cas où L est vide.

Vous devez vérifier qu'aucun de ces cas ne provoque une erreur, qu'à chaque fois le programme arrive bien au bout et que la réponse est celle attendue.

Question 2

Pour un algorithme s'appliquant à une donnée de taille n – ici, n est la longueur de la liste : n = len(L), autrement dit le nombre d'éléments de L – on veut évaluer le nombre d’opérations élémentaires pertinentes.

On pourra compter le nombre d'exécution de la comparaison « == ».

On étudie le comportement asymptotique de ce nombre.

On appelle cela la complexité de l’algorithme.

Pour une liste de longueur n, quel est le nombre minimal d’instructions pertinentes exécutées dans la fonction est_element ? Préciser pour quelle genre de liste on obtient ce résultat.
On parle de complexité dans le meilleur des cas et ici on dit qu’elle est constante – coût constant.
Pour une liste de longueur n, quel est le nombre maximal d’instructions pertinentes exécutées ?
On a là la complexité dans le pire des cas.
Justifier la qualificatif de linéaire – coût linéaire.

Pourquoi asymptotique ?

Par exemple, supposez que vous trouviez que le nombre est $3n^2 + 17n + 36$. À quoi bon ce nombre ? À quoi nous sert-il ? On hésite parfois, on se demande si on ne devrait pas compter telle instruction supplémentaire ce qui donnerait $+ 37$ au lien de $+ 36$…

Eh bien cela n'a pas d'importance, car ce qui nous intéresse dans $3n^2 + 17n + 36$ c'est le terme dominant quand $n \to +\infty$, c'est à dire $3n^2$. Et même, on ne s'intéresse qu'au $n^2$ et pas au coefficient. Pourquoi ?

On est surtout intéressé par le temps mis par la machine à exécuter le programme, un temps en secondes. Mais on ne sait pas exactement combien la machine met de temps pour exécuter telle ou telle instruction. Certaines sont certainement plus lentes que d'autres. Donc la quantité $3n^2 + 17n + 36$ ne peut être mieux qu'une estimation.
On ne s'intéresse pas au cas $n$ petit car avec les machines actuelles, 1000 ou 10000 instructions sont exécutées très très rapidement. Ce n'est pas un enjeu. L'enjeu se situe dans les cas avec des millions d'instructions. Avec $n$ aussi grand, seul le terme $3\,n^2$ a de l'importance.
On veut savoir ce qui se passera si la taille du problème augmente. Si le tableau est 2x plus grand, est-ce que l'exécution prendra 2x plus de temps ? 4x ? Pour cela, le facteur 3 dans $3\,n^2$ ne change rien, seul le $n^2$ est important.

Question 3

Écrire une fonction qui prend en argument une chaîne de caractères et un caractère 'c' et vérifie la présence ou pas du caractère dans la chaîne de caractères (et la tester).

Question 4

Adapter, modifier, la fonction de la première question en demandant

si a est présent, renvoyer l'indice de la première occurrence de a dans L
sinon, renvoyer False

Question 4 bis

Adapter, modifier, la première question en demandant

si a est présent, renvoyer la liste des indices de toutes les occurrences de a dans L
sinon, renvoyer False

Différence entre est_element et in ? Un dernier mot sur le in, intégré à Python. Notre fonction est_element fait exactement la même chose et bien sûr. Maintenant que nous avons passé du temps à l'écrire, est-il indifférent d'utiliser a in L plutôt que est_element(L, a) ?

Eh bien non, a in L sera beaucoup plus rapide. La qualité de notre programmation n'est pas en cause. in utilise le même mécanisme. Mais Python est un langage peu performant en termes de vitesse d'exécution. On l'aime car il est facile à programmer, pas pour sa vitesse. Quand on a besoin de vitesse et d'efficacité, on peut se tourner vers des langages plus difficiles comme le C.

Alors pourquoi in va plus vite que notre est_element ? n'est-il pas en Python lui aussi ? Pas tout à fait. Les commandes de Python font appel à du code écrit en C, donc plus rapide. De ce fait, une fonction intégrée sera toujours plus rapide que son équivalent écrit en pur Python.

C'est d'ailleurs une force de Python : prenons l'exemple des data-scientists qui analysent d'énormes bases de données et utilisent Python. Pourquoi le font-ils alors que Python est lent ? En vérité ils utilisent surtout Python comme programme principal, très facile et rapide à écrire, et qui lance des commandes trouvées dans des bibliothèques toutes faites – on trouve des bibliothèques toutes faites pour énormément de choses en Python, comme scikit-learn, pandas, numpy, sympy, … – qui utilisent par exemple le C et sont donc très rapides. Ainsi a-t-on le meilleur des deux mondes : Simplicité de programmation de Python, efficacité de C.