Je vous propose de résoudre ce petit problème (pas bien dur) :
Nous devons trouver les dix plus grands nombres dans un iterable sans faire appel à la fonction sort() ou sorted().
En pratique, cet algo peut se révéler très utile, par exemple dans le cas ou il y a énormément de valeurs à filtrer (fichier de log par exemple), car ce ne sera pas forcément évident de tout stocker en mémoire pour trier (on parle de complexité mémoire)...
Donc pour simuler ce contexte, je vous propose d'utiliser un générateur, comme ceci :
from random import randint
# génère n entiers compris entre a et b
def gen(n, a, b):
for i in range(n):
yield randint(a, b)
# ou bien, pour ceux qui préfèrent les 'one-liner'
gen = lambda n, a, b: (randint(a,b) for i in range(n))
Ensuite, nous allons créer une fonction dix_maxi(), et l'appeler comme ceci :
dix_maxi(gen(n, start, stop))
Cette fonction doit nous renvoyer une liste (ou ce que vous voulez) contenant les dix plus grands nombres générés. Les nombres retournés ne doivent pas forcément être ordonnés, faites ce que vous voulez de ce coté là.
Dans un second temps, vous devez essayer de rendre votre fonction générique, afin de pouvoir renvoyer les N éléments maximums. Essayez de faire en sorte que votre fonction soit un minimum performante même avec de grandes valeurs de N.
Astuce :
certains modules de la lib standard peuvent vous aider (je ne dis pas lesquels, ce serait trop facile)
PS : prière de mettre les réponses en secret, pour que tout le monde puisse réfléchir.
[edit] :Ajout de la possibilité de faire une fonction générique, ainsi qu'un petit mot sur la complexité.
Je l'ai fais en POO, ça m'aide dans mon organisation.
Pour les puristes, j'aurais pu hériter de list et utiliser super(), mais je voulais garder quelque-chose d'accessible pour les débutants en POO.
from random import randint
class Conteneur(object):
def __init__(self, ma_liste):
self.c = []
self.liste = ma_liste
self.compteur = 0
def retirer(self):
maxi = max(self.liste)
index = self.liste.index(maxi)
pop = self.liste.pop(index)
return pop
def ajouter(self):
value = self.retirer()
if value not in self.c:
self.c.append(value)
self.compteur += 1
def __repr__(self):
return repr(self.c)
def main(a, b, n_randint, n_maxi):
liste = [randint(a, b) for i in range(n_randint)]
c = Conteneur(liste)
while c.compteur != n_maxi:
c.ajouter()
print(c)
main(1, 500, 30, 10)
Pour les puristes
from random import randint
class Conteneur(list):
def __init__(self, ma_liste):
super(Conteneur, self).__init__(self)
self.liste = ma_liste
self.compteur = 0
def retirer(self):
maxi = max(self.liste)
index = self.liste.index(maxi)
pop = self.liste.pop(index)
return pop
def ajouter(self):
value = self.retirer()
if value not in self:
self.append(value)
self.compteur += 1
def __str__(self):
return repr(self)
def main(a, b, n_randint, n_maxi):
liste = [randint(a, b) for i in range(n_randint)]
c = Conteneur(liste)
while c.compteur != n_maxi:
c.ajouter()
print(c)
main(1, 500, 30, 10)
Je ne sais pas pourquoi tu l'as fait en POO, ça alourdit le code, mais enfin libre à toi.
Une petite explication sur ton algo à l'attention des lecteurs ne serait pas de refus .
3 points ont retenus mon attention : si je comprends bien, tu parcours la liste 10 fois et tu extrais le maximum. Donc en fait, tu dois parcourir 10 fois la liste.
1. Maintenant, imagine que tu doive récupérer les 1000 plus grandes valeurs d'une liste de 1000000 d'éléments. A ce moment là, ton approche ne sera plus du tout adaptée.
2. Deuxième problème: j'ai donné l'exemple d'un fichier de log et de contraintes mémoire. Il est bien connu que l’accès au disque est particulièrement couteux en termes de temps. Donc le fait de devoir relire à chaque fois toutes les données va encore enfoncer les performances.
3. Tu profites d'avoir tes données dans une liste pour appliquer ta methode en supprimant à chaque fois l'élément trouvé. Imagine toi que cette liste soit en lecture seule : à ce moment, ton approche n'est plus valable.
C'est vrai que ce n'est pas inclus dans les contraintes explicites de l'exo, mais il serait intéressant de prendre cela en compte. Je te suggère d'utiliser le générateur que j'ai proposé ci-dessus, ça te poussera sûrement à coder un algo différent .
def maximums(liste, n=10):
liste = iter(liste)
bar = [next(liste) for _ in range(n)]
# on prend les dix premiers elements comme liste de maximums.
while True:
indice, minimum = min(enumerate(bar), key=lambda a:a[1])
# on prend ensuite le plus petit element de la liste des maximums
try:
i = next(liste)
except StopIteration:
break
if i> minimum:
bar[indice] = i
# et on le compare avec l'element courant de la liste.
return bar
Et désolé pour les noms, j'avais pas beaucoup d'inspiration.
Bonjour, merci pour l'exercice, voici ma solution j'ai été obligé de créer une liste (liste1) je n'ai pas su faire autrement:
from random import randint
def dix_maxi(iterable):
l1,l2 = list(),list()
[l1.append(x) for x in iterable]
maxi = max(l1)
for _ in range(10):
for x in l1:
if x == maxi:
if not x in l2:
l2.append(x)
l1.remove(x)
maxi = max(l1)
l2.reverse()
return l2
gen = lambda n,a,b: (randint(a,b) for i in range(n))
print(dix_maxi(gen(20,10,100)))
Edit : excellente la solution Josmiley, j'ai honte maintenant.
En plus j'ai fais n'importe quoi je vais recommencer.
Voilà la mienne nettement plus efficace que la 1ère
from random import randint
gen = lambda n, a, b: (randint(a,b) for i in range(n))
def maxi(liste):
liste = set(liste)
for i in range(10):
if liste:
m = max(liste)
liste.remove(m)
yield m
print [i for i in maxi(gen(10000,1,1000000))]
WoW ! Déjà plein de réponses, à ce que je vois. Ça fait plaisir !
@ quelqun_dautre :
C'est vraiment très bien, comme tu as fait. Tu prends en compte mes remarques 2. et 3. ci-dessus.
Maintenant, ton code est toujours en O(nk) (k = taille de la liste, n = nombre d'éléments à extraire), on peut faire mieux avec une astuce.
Au passage, c'est intéressant de noter les contorsions que tu es obligé de faire pour récupérer l'index de max sans traverser 2 fois la liste (avec index()). Cela montre une certaine limitation du langage, me semble il.
@ josmiley :
Très bon code, clair et concis. J'ai testé le premier code, et je suis très impressionné par les performances, alors que ton algo me semble aussi en O(nk).
Maintenant, si on cherche par exemple les 500 plus grands nombres, les performances s'effondrent un peu.
Petite correction (premier code) : tu déclare n=10, mais tu utilise la constante 10 à la place de n dans le code.
@ fred1599 :
Tres bonne idée, que d'utiliser un set(). Au niveau complexité, c'est une excellente solution, à laquelle je n'avais pas pensé.
Le seul cas ou ce ne sera pas adapté est le cas d'une contrainte mémoire, par exemple si on lit séquentiellement un fichier de plusieurs To., le set() risque de saturer la mémoire.
EDIT :Non, en fait c'est une fausse bonne idée, car tu vas supprimer les doublons, comme signalé plus bas par PsycoPy. La solution serait d'utiliser un dictionnaire, ou un Counter(), ou autre...
Il existe une technique pour améliorer l'approche de quelqun_dautre et josmiley. Réfléchissez bien...
Bon j'ai utilisé sort(), mais pas pour trier la séquence dans laquelle on cherche les maximums. En fait c'est la liste des maximums que je trie. L'argument pour ne pas utiliser sort() est que la séquence d'intérêt peut être très grande, et on aurait un problème de complexité mémoire. Quand on veut extraire n éléments, il me semble raisonnable d'utiliser sort() sur une liste de n éléments, voire 2n éléments (c'est ce que fait mon algo).
Certains considèrerons peut être que c'est de la triche, mais je pense rester dans l'esprit du problème original.
Du coup, comme complexité (à vérifier...), si on cherche n éléments maximums dans une séquence de longueur k :
- mémoire : 2n
- temporelle : 2k(1+log(2n))
def extract_best( tmp, best, n ) :
best.extend(tmp)
best.sort()
return best[-n:]
def n_maxi( seq, n = 10 ) :
best = []
tmp = []
for i in seq :
tmp.append(i)
if len(tmp) == n :
best = extract_best(tmp, best, n)
tmp = []
best = extract_best(tmp, best, n)
return best
print n_maxi(gen(1000000,-1000000, 1000000), 1000)
Certains considèrerons peut être que c'est de la triche, mais je pense rester dans l'esprit du problème original.
Non, c'est très bien je trouve. Si on s'en tient à l'énoncé stricto-sensu, on pourrait par exemple recoder sort()
Sinon, ton approche est vraiment intéressante. On peut simplifier, mais la tienne est nettement plus performante (beaucoup moins d'appels à sort) :
def n_maxi( seq, n = 10 ) :
best = []
for i in seq :
best.append(i)
if len(best) > n:
best = sorted(best)[1:]
return best
En fait, on peut réécrire ton approche comme ceci, il me semble (on peut très facilement jouer sur la complexité mémoire, cf. ligne 5) :
def n_maxi( seq, n = 10 ) :
best = []
for i in seq :
best.append(i)
if len(best) == 2 * n:
best = sorted(best)[-n:]
return sorted(best)[-n:]
Pour la complexité temporelle, je crois que c'est moins que ça. Je dirais un truc comme (un horreur simplifiée par Maxima) : <math>\(\frac{{k}^{2}\,ln\left( 2\,n\,ln\left( 2\,n\right) \right) }{2\,n}\)</math>.
A confirmer par un matheux, parce que c'est pas tout à fait mon truc...
EDIT :
Citation : PsycoPy
[edit] le défaut c'est que ça supprime les doublons.
Ah oui, merci, j'avais pas fait gaffe effectivement.
Pour la complexité temporelle, je crois que c'est moins que ça. Je dirais un truc comme (un horreur simplifiée par Maxima) : <math>\(\frac{{k}^{2}\,ln\left( 2\,n\,ln\left( 2\,n\right) \right) }{2\,n}\)</math>.
Je ne pense pas que ton expression soit correcte (pourquoi k est il au carré?), et en fait la complexité de mon algo (pas ta version modifiée qui diminue un peu la complexité temporelle) serait plutôt <math>\(k(1+2(1+\log(2n)))\)</math>, mais je ne suis pas vraiment sur...
Quoi qu'il en soit la méthode est rapide et se comporte bien si on augmente k et/ou n.
@fred1599 : ma méthode peut renvoyer des doublons dans le résultat final. L'énoncé initial ne précise pas qu'on ne doit pas en renvoyer, et dans certaines applications il peut être utile d'avoir ces doublons. Après il doit être possible de les éliminer, mais ça pose des problèmes dans des cas particuliers, par exemple si la liste initiale contient k fois le même nombre...
Je viens de découvrir que python fournissait un tas, je partais pour en coder un.
Je n'ai pas fait de tests, mais ça me semble un peu lent.
from random import randint
import heapq
N = 1000
MAX = 10000
def gen(n, a, b):
for i in range(n):
yield randint(a, b)
def dix_maxi(g):
hp, res = [], []
for value in g:
heapq.heappush(hp, -value)
for _ in range(10):
res.append(-heapq.heappop(hp))
return res
print dix_maxi(gen(N, 0, MAX))
edit: en fait, non ça semble très correct niveau temps, testé avec cette fonction
def n_maxi(g, n = 10):
hp, res = [], []
for value in g:
heapq.heappush(hp, -value)
for _ in range(n):
res.append(-heapq.heappop(hp))
return res
Les perfs sont convenables même avec de grandes valeurs de N.
Moi aussi, c'est ma préférée pour l'instant (avec la mienne).
Citation : quark
Je ne pense pas que ton expression soit correcte (pourquoi k est il au carré?), et en fait la complexité de mon algo (pas ta version modifiée qui diminue un peu la complexité temporelle) serait plutôt <math>\(k(1+2(1+\log(2n)))\)</math>, mais je ne suis pas vraiment sur...
Oui, j'ai un peu gaffé. Maintenant, je trouve : <math>\(2\,k\,ln\left( 2\,n\right) +k\)</math> avec mon 2e algo (légèrement différent du tien).
Citation : quark
Quoi qu'il en soit la méthode est rapide et se comporte bien si on augmente k et/ou n.
Tout à fait.
@ GurneyH :
Aïe, si proche...
Ce que tu fais, c'est l’équivalent d'un semi-heapsort (1e partie + extraction des N premières valeurs). L'ennui, c'est que la complexité mémoire n'est pas terrible, comme mentionné maintes fois plus haut.
Mon code :
Avant de proposer ma solution, je vais expliquer ma démarche :
Certaines personnes ont essayé - et à juste titre - d'utiliser une liste de N éléments pour enregistrer les N éléments les plus grands au cours de l'énumération de tous les éléments de l'iterable (une seule passe). La difficulté majeure est qu'a chaque élément, on doit vérifier s'il est supérieur au minimum de notre liste, ce qui donne une complexité temporelle en O(NM) (N pour le nombre d'éléments à retourner, M pour la taille de la liste).
Si on disposait d'une structure "auto-triée", on pourrait alors se contenter de comparer chaque valeur avec le premier élément de la liste, et ainsi passer en O(M). Bien sûr, l'insertion dans une telle structure a aussi un coût qu'il faut évaluer.
En fait, nul besoin d'avoir une structure totalement "auto-triée", il suffit que le premier élément soit toujours la plus petite valeur. Autrement dit, un tas peut parfaitement faire l'affaire . [en principe, un set du C++ aussi pourrait faire l'affaire, mais je crois qu'un set ne respecte pas systématiquement l'ordre en python, détrompez moi si je dis une bêtise]
L'opération d'insertion dans un tas a une complexité de O(log(N)), donc on se retrouve au final avec une complexité de O(M*log(N)).
Mon code :
from heapq import *
def n_premiers(generator, n=10):
result = []
for elt in iter(generator):
if len(result) < n:
heappush(result, elt)
elif elt > result[0]:
heapreplace(result, elt)
return [heappop(result) for i in range(10)]
Vous pouvez vérifier que les performances ne se dégradent pas vraiment même avec de grosses valeurs de N.
Pour moi la solution ne me semble pas si évidente (bon j'ai pas un grand niveau en python mais la il est plutôt question d'algo).
D'abord faire le test sur la longueur de result à chaque tour de boucle pourrait être optimisé.
Ensuite et surtout l'algo ne fonctionne pas me semble t'il.
On compare toujours l'élément en cours avec le premier de la liste, mais je ne vois pas ce qui garanti que c'est lui le plus petit de cette liste ?
A ok, j'avais pas compris le que heapq n'était pas une simple pile, dsl.
Le cas le plus défavorable est donc celui d'une liste triée par ordre croissant.
[edit]En fait faut voir puisque l'insertion sur le tas sera a priori plus favorable, mais avec la suppression du minimum en O(log(n)) également...[/edit]
Voici le benchmark promis. Je n'ai laissé que les algos qui passent la validation.
Amusez-vous à changer les paramètres val_min, val_max, it_size et n
# -*- coding:utf-8 -*-
from __future__ import print_function
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# quelqun_dautre :
def quelqun_dautre_nmax(liste, n=10):
liste = iter(liste)
bar = [ next(liste) for _ in range(n) ]
while True:
indice, minimum = min(enumerate(bar), key=lambda a:a[1])
try:
i = next(liste)
except StopIteration:
break
if i> minimum:
bar[indice] = i
return bar
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# quark :
def quark_extract_best( tmp, best, n ) :
best.extend(tmp)
best.sort()
return best[-n:]
def quark_nmax( seq, n = 10 ) :
best = []
tmp = []
for i in seq :
tmp.append(i)
if len(tmp) == n :
best = quark_extract_best(tmp, best, n)
tmp = []
best = quark_extract_best(tmp, best, n)
return best
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# josmiley :
def josmiley_nmax(iterable, n=10):
it = iterable[:]
return [ it.pop(it.index(max(it))) for i in range(n) if len(it) ]
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# GurneyH :
import heapq
def GurneyH_nmax(g, n):
hp, res = [], []
for value in g:
heapq.heappush(hp, -value)
for _ in range(n):
res.append(-heapq.heappop(hp))
return res
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# yoch :
import heapq
def yoch_nmax(generator, n=10):
result = []
for elt in iter(generator):
if len(result) < n:
heapq.heappush(result, elt)
elif elt > result[0]:
heapq.heapreplace(result, elt)
return [ heapq.heappop(result) for i in range(len(result)) ]
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# -*-*-*-*-*-*-*-*-*-*-*-*-*- Benchmark -*-*-*-*-*-*-*-*-*-*-*-*-*-*-
# -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
if __name__ == "__main__":
from random import randint
from timeit import Timer
gen = lambda a, b, n: [ randint(a, b) for _ in range(n) ]
val_min = 1 # Valeur minimal contenu dans l'itérable.
val_max = 10000 # Valeur maximal contenu dans l'itérable.
it_size = 5000 # Taille de l'itérable.
n = 500 # Nombre de valeurs à extraire de l'itérable.
repeat = 100 # see help(Timer.timeit)
iterable = list(gen(val_min, val_max, it_size))
players = [ # Proprio des algos (ça sonne bien en plus...
"quelqun_dautre",
"quark",
"josmiley",
"GurneyH",
"yoch"
]
# La réponse attendu :
resp = iterable[:]
resp.sort()
resp = resp[-n:]
# Validation des algos :
discalified = []
for i, name in enumerate(players[:]):
if resp != sorted(list(eval(name + "_nmax(iterable[:], n)"))):
print("L'algo de", name, "est incorrect !")
discalified.append(name)
else:
print("L'algo de", name, "est correct.")
print("\nBenchmark")
setup = "from __main__ import heapq, {}_nmax, iterable, n"
stmt = "_ = list({}_nmax(iterable[:], n))"
ls = []
for name in players:
if name in discalified:
continue # on ne teste pas les algos erronés
t = Timer(stmt.format(name), setup.format(name))
print(name, end=" : ")
t = t.timeit(repeat)
print(t, " seconde", 's' if t > 1 else '', sep='')
ls.append((t, name))
ls.sort()
print("\nPodium")
for t, name in ls:
print("{} : {} seconde{}".format(
name.center(15), t,
's' if t > 1 else ''))
#EOF#
En fait, nul besoin d'avoir une structure totalement "auto-triée", il suffit que le premier élément soit toujours la plus petite valeur. Autrement dit, un tas peut parfaitement faire l'affaire
Héhé, c'est la solution que je voulais poster hier, mais je n'ai pas eu le temps...
C'est la méthode qu'utilise postgresql pour traiter un ORDER BY + LIMIT, et ça fonctionne très bien.
J'ai juste modifié la solution de yoch pour éviter des faire un test inutile à chaque boucle :
import heapq
def nmax(generator, n=10):
result = []
for elt in iter(generator[:n]):
heapq.heappush(result, elt)
for elt in iter(generator[n:]):
if elt > result[0]:
heapq.heapreplace(result, elt)
return result
On peut utiliser l'opérateur [] sur un générateur ? ce serait nouveau XDDDD
Ça marche dans ton exemple parce que "generator" est une liste en fait.
import heapq
from itertools import *
def nmax(generator, n=10):
it = iter( generator )
result = list(islice( it, n ))
if not result:
return result
heapq.heapify(result)
for elt in g:
if elt > result[0]:
heapq.heapreplace(result, elt)
return result
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.