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)
%%time listetriee = sorted(randomlist,reverse =1) print(listetriee[1]) 50 Wall time: 210 ms
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]
%%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
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
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
Good hacking ! with http://hilite.me/ pour la mise en forme du code
2 commentaires:
Bonjour,
Si vous cherchez à mieux comprendre du Machine Learning, nous vous invitons sur www.datasciencemarketing.blogspot.com! Nous sommes 4 étudiants passionnés par la Data et nous expliquons ce concept de façon facile à comprendre!
Merci!
Enregistrer un commentaire