Discussion :

[wiztricks]

Je ne comprends ce que fait math.inf

C'est que vous n'avez pas compris l'algo.
On fait quoi? On balaie n fois la liste pour trouver les indices des n premiers minima.
A l'étape 0, on récupère l'indice du minimum....
Maintenant étape 1, trouvez le minimum suivant sans utiliser math.inf (et essayer de comprendre l'intérêt de l'utiliser).

- W

[Pyramidev]

Je ne comprends ce que fait math.inf

math.inf correspond à +l'infini. Si on retire la ligne l[index_min] = math.inf sans changer le reste du code, alors la fonction va retourner k fois le même indice, celui du minimum, au lieu de retourner les indices des k minima.

Remarque 1 : Utiliser math.inf n'est pas la seule solution possible. Par exemple, on pourrait aussi retirer l[index_min] de la liste avant de chercher le minimum à l'itération suivante.

Remarque 2 : jurassic pork a cité la fonction standard heapq.nsmallest qui utilise encore un autre algorithme, plus performant, mais aussi beaucoup plus compliqué et dont la lecture du code demande d'être à l'aise avec Python : https://github.com/python/cpython/bl.../heapq.py#L463
Mais, en début d'apprentissage, on peut se contenter de coder des algos plus simples.

[Beginner.]

Salut,

J'ai essayé de faire cet exercice mais c'était avant de lire l'algo proposé par Pyramidev (qui semble meilleur que ce que j'ai fait...) :

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def min_k(k, lst):
    indice_mins = [None] * k
    for j in range(k):
        mini = math.inf
        for i, elem in enumerate(lst):
            if i not in indice_mins:
                if elem < mini:
                    mini = elem
                    indice_mins[j] = i
    return indice_mins

Remarque 1 : Utiliser math.inf n'est pas la seule solution possible. Par exemple, on pourrait aussi retirer l[index_min] de la liste avant de chercher le minimum à l'itération suivante.

Je ne suis pas sûr d'avoir compris : si on retire l[index_min] de la liste l alors certains des éléments restants n'auront plus le même indice, non ? Du coup on trouvera les minimums mais on n'aura pas les bons indices correspondants à ces minimums, non ?

Voici le code corrigé:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def k_min(k,l):
    res = []
    for i in range(k):
        index_min = 0
        for j in range(1,len(l)):
             if l[j] < l[index_min]:
                     index_min = j
        res.append(index_min)
        l[index_min] =math.inf
    return res

Ce code semble meilleur que celui que j'ai posté ci-dessus...

Je me demande si une affection du genre res[i] = index_min ne serait pas plus rapide qu'un res.append(index_min) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def k_min1(k, l):
    res = [None] * k
    for i in range(k):
        index_min = 0
        for j in range(1, len(l)):
            if l[j] < l[index_min]:
                index_min = j
        res[i] = index_min
        l[index_min] = math.inf
    return res

Qu'en pensez-vous ?

Sinon, moi j'écrirai çà comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> L = [5,9,10,2,6,8]
>>> sorted(range(len(L)), key=lambda i: L[i])[:3]
[3, 0, 4]

C'est bien vu, il fallait y penser...
Comme quoi on peut faire des choses efficaces en Python...

PS : Du coup je me suis demandé si on pouvait faire la même chose en JS et j'ai trouvé plusieurs solutions, les plus proches me semble-t-il sont celles-ci :

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let l = [5, 9, 10, 2, 6, 8]
let result = [...Array(l.length).keys()]
    .sort((a, b) => (l[a] - l[b]))
    .slice(0, 3)

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
let l = [5, 9, 10, 2, 6, 8]
let result = l.map((elem, i) => i)
    .sort((a, b) => (l[a] - l[b]))
    .slice(0, 3)

La fonction range n'existe pas en JS du moins à ma connaissance mais on peut l'écrire bien sûr...

[Pyramidev]

Je ne suis pas sûr d'avoir compris : si on retire l[index_min] de la liste l alors certains des éléments restants n'auront plus le même indice, non ? Du coup on trouvera les minimums mais on n'aura pas les bons indices correspondants à ces minimums, non ?

Ah oui, mince. Au moment où j'avais écrit "retirer l[index_min] de la liste", j'avais oublié qu'on retournait les indices des minima et pas les minima eux-même.

Je me demande si une affection du genre res[i] = index_min ne serait pas plus rapide qu'un res.append(index_min)

Je ne sais pas. Mais, si on cherche la vitesse, il faut se tourner vers heapq.nsmallest.

[Sve@r]

Bonjour

Je ne comprends ce que fait math.inf

La fonction doit trouver les 3 indices les plus petits. Quand elle a trouvé le premier, si on ne change rien, lorsqu'elle cherchera le second plus petit elle retombera alors sur le premier (toujours présent dans le tableau et toujours plus petit que les autres).
Donc une fois l'élément trouvé on le change et on lui donne une valeur particulière lui permettant de ne pas être récupéré une seconde fois. Moi j'aurais utilisé None (ce qui fonctionne) mais uniquement parce que je ne connaissais pas "math.inf" qui fonctionne encore mieux.

[Beginner.]

Je ne sais pas. Mais, si on cherche la vitesse, il faut se tourner vers heapq.nsmallest.

Ok merci.

[f-leb]

Salut à tous, et tous mes vœux pour 2023

Très bon exercice à ajouter à nos pages !

Sinon, moi j'écrirai çà comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
>>> L = [5,9,10,2,6,8]
>>> sorted(range(len(L)), key=lambda i: L[i])[:3]
[3, 0, 4]

Sans doute la solution la plus courte, mais pas la plus efficace si on suppose que k est très petit devant la taille de la liste L. Si on a une liste de 100_000 éléments et qu'on veut seulement les indices des 3 plus petites valeurs, on va trier 99_997 pour rien

Un algo possible pourrait consister à ne parcourir qu'une fois la liste L, et on insère (comme dans un tri par insertion) éventuellement l'élément dans la liste des k plus petits éléments :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
L = [5, 9, 10, 2, 6, 8]
print(f"résultat : {min(3, L)}")

résultat (les tuples sont de la forme (indice de position, valeur de l'élément) ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Etape 0 : [(0, 5), (None, inf), (None, inf)]
Etape 1 : [(0, 5), (1, 9), (None, inf)]
Etape 2 : [(0, 5), (1, 9), (2, 10)]
Etape 3 : [(3, 2), (0, 5), (1, 9)]
Etape 4 : [(3, 2), (0, 5), (4, 6)]
Etape 5 : [(3, 2), (0, 5), (4, 6)]
résultat : [3, 0, 4]

Bref, beaucoup de cas et de solutions à discuter

[Sve@r]

Un algo possible pourrait consister à ne parcourir qu'une fois la liste L, et on insère (comme dans un tri par insertion) éventuellement l'élément dans la liste des k plus petits éléments :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
L = [5, 9, 10, 2, 6, 8]
print(f"résultat : {min(3, L)}")

résultat (les tuples sont de la forme (indice de position, valeur de l'élément) ) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Etape 0 : [(0, 5), (None, inf), (None, inf)]
Etape 1 : [(0, 5), (1, 9), (None, inf)]
Etape 2 : [(0, 5), (1, 9), (2, 10)]
Etape 3 : [(3, 2), (0, 5), (1, 9)]
Etape 4 : [(3, 2), (0, 5), (4, 6)]
Etape 5 : [(3, 2), (0, 5), (4, 6)]
résultat : [3, 0, 4]

Entre l'étape 2 et l'étape 3, le couple (3, 2) semble s'insérer au début en décalant tout le reste.
Mais ce n'est qu'une impression car si la liste est L = [5, 10, 9, 2, 6, 8], les étapes deviennent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Etape 0 : [(0, 5), (None, inf), (None, inf)]
Etape 1 : [(0, 5), (1, 10), (None, inf)]
Etape 2 : [(0, 5), (1, 10), (2, 9)]
Etape 3 : [(3, 2), (0, 5), (2, 9)]
Etape 4 : [(3, 2), (0, 5), (4, 6)]
Etape 5 : [(3, 2), (0, 5), (4, 6)]
résultat : [3, 0, 4]

Tout ça pour dire que l'algo n'est pas si simple que ça. Ok on ne traite qu'une fois la liste mais chaque insertion devra traiter l'ensemble de la liste résultat pour savoir où insérer tout nouvel élément et on tombe alors dans l'effet inverse si k devient grand par rapport à N.
Il n'y a alors pas de "meilleure façon" car toutes les méthodes se verront opposer leurs inconvénients respectifs.
Dans ce cas, je conseillerais de "faire confiance à Python" en le laissant gérer au mieux. Après-tout, le tri est très probablement un qsort et trier 99_997 éléments de trop ne devrait pas être super pénalisant (surtout que ce besoin d'avoir les k plus petits ne me semble pas non plus super caractéristique de l'ensemble des algos que j'ai eu à faire).

Mais ça aurait été sympa si la fonction native min() (resp. max()) avait possédé un paramètre "n" indiquant qu'on veut les n plus petits (resp. plus grands) éléments...

[f-leb]

[...] car si la liste est L = [5, 10, 9, 2, 6, 8], les étapes deviennent

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Etape 0 : [(0, 5), (None, inf), (None, inf)]
Etape 1 : [(0, 5), (1, 10), (None, inf)]
Etape 2 : [(0, 5), (1, 10), (2, 9)] [(0, 5), (2, 9), (1, 10)]
Etape 3 : [(3, 2), (0, 5), (2, 9)]
Etape 4 : [(3, 2), (0, 5), (4, 6)]
Etape 5 : [(3, 2), (0, 5), (4, 6)]
résultat : [3, 0, 4]

[...] Ok on ne traite qu'une fois la liste mais chaque insertion devra traiter l'ensemble de la liste résultat pour savoir où insérer tout nouvel élément et on tombe alors dans l'effet inverse si k devient grand par rapport à N.

Toutafé ! Et si je ne me trompe pas, l'algo avec k<<N est en O(kN) dans le pire des cas.