Un problème de tri

Python Entraide
1

Bonjour,
Je suis débutant en Python et j’aimerais un conseil sur le problème suivant.
J’ai un tableau T de taille n de valeurs numériques et je voudrais connaître les indices des p (p<n) valeurs les plus faibles de ce tableau.
Merci d’avance,
lm

2

Salut,

En combinant correctement les fonctions natives de Python, tu devrais pouvoir facilement extraire ce que tu veux.
J’ai principalement deux solutions qui me viennent en tête :

  • La première consisterait à utiliser enumerate et sorted pour trier les éléments tout en conservant les indices auxquels ils correspondent. Puis d’utiliser des intensions pour ne conserver que les informations qui t’intéressent.
    [i for x, i in sorted((x, i) for i, x in enumerate(T))]
  • La deuxième serait d’utiliser sorted sur les index de ta liste, avec un argument key pour trier ces index selon les valeurs associées dans la liste
    sorted(range(len(T)), key=lambda i: T[i])
3

Bonjour Laurent,

C’est quoi comme tableau? une list de valeurs? Un pandas.DataFrame ?

Quelle taille de liste a peu pres (dix? mille? un million ?)

-Graham

4

Merci ! Tout est arrangé grâce à la réponse précédente.
Python a paradoxalement tellement de possibilités natives qu’il est difficile de s’y retrouver.
L.

5

Voici une autre solution possible :

>>> import heapq
>>> def indices_valeurs_plus_faibles(T, p):
...     return heapq.nsmallest(p, range(len(T)), key=lambda i: T[i])
... 
>>> 
>>> L = [4, 5, 3, 0, 9, 8, 1, 2, 7, 6]
>>> indices_valeurs_plus_faibles(L, 3)
[3, 6, 7]

Inconvénient : si c’est un prof de programmation qui vous le demande, il ne trouvera sans doute pas très correct d’utiliser une fonction prédéfinie qui fait exactement ce que vous voulez.

Avantage : les personnes qui ont programmé le module heapq sont très fortes en algorithmique et ont réfléchi beaucoup à la manière d’implémenter cela efficacement. Pensez au problème de trouver les trois plus petits éléments d’une liste de cent millions d’éléments. Avec sorted(), vous triez toute la liste entière et ses cent millions d’éléments. heapq.nsmallest ne s’embêtera pas à cela.

La documentation de heapq.nsmallest est par ici :

Les explications sur le paramètre key, qui est le même que pour sorted :

Pour faire simple, lambda i: T[i] est la même chose que

def f(i):
    return T[i]

sauf que la fonction f est anonyme avec lambda, on peut s’en servir directement au sein d’une expression. Plus d’infos ici :

Et si vous aimez l’algorithmique (donc mieux vaut s’en passer si vous êtes grand débutant en programmation, mais si vous avez un bagage scientifique, cela peut vous intéresser), le code source, qui explique l’algorithme retenu, sa complexité et ses performances en pratique :

3 « J'aime »
6

Merci pour cette réponse qui me sera utile, et aussi à bien d’autres.
L.