Algorithmie: comment trouver la 2eme valeur la plus élevée d'une liste

 Lors des entretiens d'embauche d'un développeur, il est possible de rencontrer cette question: 

 Comment  trouver le la 2eme valeur la plus élevée d'une liste ? .

Bien qu'anodine, cette question ouvre vers de nombreuses déclinaisons et soulève des nouvelles questions.

Est ce que la liste est finie ?, de taille compatible avec la mémoire du serveur ? etc..

Première réponse qui vient spontanément: trier la liste et prendre le 2eme élément.

Démonstration en Python

Commençons par générer une liste aléatoire de 1000000 éléments de 1 à 50.

 

import random
randomlist = []
for i in range(0,1000000):
    n = random.randint(1,50)
    randomlist.append(n)

Puis récupérons le deuxième élément après le tri.

 

%%time
listetriee = sorted(randomlist,reverse =1)
print(listetriee[1])

50
Wall time: 210 ms

Erreur, on devrait retourner vraisemblablement la valeur 49 et non pas 50.

En examinant le début de la liste triée:

print(listetriee[:20])

[50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50]

On n'a pas traité le cas des valeurs identiques... Pour rendre unique les éléments d'une liste, le plus simple est de passer par un 'set'.

 

%%time
unique = set(randomlist)
print('taille de la liste:', len(unique))
listetriee =sorted(unique, reverse = 1)
print(listetriee[1])

taille de la liste: 50
49
Wall time: 48 ms

La taille finale de la liste fait 50 (ce qui est normal) Le temps d exécution est plus petit en raison de cette diminution de la taille. Le résultat est à présent correct.

Cette méthode ne fonctionnerait pas avec une liste issue d'un flux où d'un fichier de plusieurs Go. Elle ne pourrait pas tenir en mémoire centrale.

Il faut dissocier la recherche des deux éléments les plus élevés et l'alimentation au fils de l'eau.

Pour la recherche du 2eme élément, le tri de toute la collection est inutile: on ne désire que le premier et le deuxième élément. La connaissance du premier élément ne sert qu'à ordonner le deuxième (celui qui vient juste après le premier).

%%time
unmax = 0
deuxmax = 0
for i in randomlist:
    if i > unmax:
        deuxmax = unmax
        unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
            
print(deuxmax)        

49
Wall time: 73.5 ms

Ici, on va parcourir la liste sans la trier, juste sélectionner les deux plus fortes valeurs.

Le temps d'exécution donnée par %%time dans jupyter est plus important que le tri sur la liste sans doublon mais plus rapide que le tri complet de la liste.

A présent on peut s'attaquer au problème de l'alimentation à la volée de ce filtre, à partir par exemple de la lecture d'un fichier.

Nous allons tout d abord fabriquer un fichier de nombre à partir d'une compréhension de liste.

maliste = [ random.randint(1,50) for i in range(10000000)]
with open('grosfichier.txt', 'a') as the_file:
    for i in maliste:
        the_file.write(f"{i}\n")
        

Puis on va lire le fichier et le filtrer à la volée.

%%time
unmax = 0
deuxmax = 0
with open('grosfichier.txt', 'r')  as file:
    for ligne in file:
        i = int(ligne[:-1])
        if i > unmax:
            deuxmax = unmax
            unmax = i
    else:
        if i > deuxmax and i < unmax:
            deuxmax =i
print(deuxmax)


49
Wall time: 3.65 s
        

Et voila, traitement sera plus long du fait de la lecture du fichier mais le filtre sera capable de traiter plusieurs giga de données sans risque de saturer la mémoire.

Good hacking ! with http://hilite.me/ pour la mise en forme du code