Algoritme (Python): vind het kleinste getal groter dan k

Ik heb een vraag vanuit het oogpunt van het algoritme. Ik heb een lijst met nummers (drijvers)

1.22,3.2, 4.9,12.3.....and so on

En ik wil het kleinste aantal groter vinden dan (laten we zeggen) 4 .. Dus het antwoord is 4.9 Maar afgezien van de voor de hand liggende oplossing .. (iterating thru list and keeping a track of smallest number greater than k) Wat is de "pythonic way" om dit te doen. Bedankt

7

4 antwoord

min(x for x in my_list if x > 4)
15
toegevoegd
@Amber: Nou, wat zou je anders moeten doen? :)
toegevoegd de auteur Sven Marnach, de bron
Toegegeven, dit doet precies wat je in het OP hebt aangegeven ("itereer door de lijst met het kleinste getal groter dan k") - het is slechts een compacte manier om het te schrijven.
toegevoegd de auteur Amber, de bron
@SvenMarnach - Ik zei niet dat er iets mis was met je antwoord (er is letterlijk niets beters dat je zou kunnen doen); ik wijs de vrager erop dat dit gewoon syntactische suiker is, niet iets dat op magische wijze efficiënter is dan iteratie.
toegevoegd de auteur Amber, de bron
Ik had net dezelfde vraag. Het lezen van het geaccepteerde antwoord drukte me nogal de kop in - wie wil ergens anders graven - en toen zag ik dit. Syntactische suiker of niet, het is nog steeds zoet.
toegevoegd de auteur Noich, de bron

Binair zoeken zou een standaardmanier zijn om hiermee om te gaan, maar alleen als de lijst is gesorteerd, zoals in het vorige antwoord werd opgemerkt.

See Python binary search-like function to find first number in sorted list greater than a specific value

and In Python, how do you find the index of the first value greater than a threshold in a sorted list?

for discussion of a module that does this for you: http://docs.python.org/library/bisect.html

8
toegevoegd
+1 voor de bissectiefunctie
toegevoegd de auteur joaquin, de bron

Dit is een perfect scenario voor filter .

>>> L = [1.22, 3.2, 4.9, 12.3]
>>> k = 4
>>> a = min(filter(lambda x: x > k, L))
>>> print(a)
4.9

Je zou ook list comprehensions kunnen gebruiken:

>>> L = [1.22, 3.2, 4.9, 12.3]
>>> k = 4
>>> a = min([element for element in L if element > k])
>>> print(a)
4.9

Hoewel het lijstbegrip in de eerste weergave minder rechtlijnig lijkt, is dit de aanbevolen manier om het te doen. Volgens sommige Python-ontwikkelaars zou filter niet moeten worden gebruikt.

Een generator-expressie is nog beter omdat deze de lijst niet maakt in geheugen:

>>> L = [1.22, 3.2, 4.9, 12.3]
>>> k = 4
>>> a = min(element for element in L if element > k)
>>> print(a)
4.9
5
toegevoegd

Ik heb geen idee van Python, maar vanuit een algoritmisch oogpunt kan ik misschien iets toevoegen. In uw voorbeeld wordt uw lijst monotoon verhoogd (gesorteerd). Als dat altijd geldt voor uw lijst, is een kleine optimalisatie mogelijk het stoppen met itereren zodra u een getal groter dan 4 hebt bereikt.

Als uw lijst altijd een lager aantal heeft dan 4, is dit een goede optimalisatie, maar als het aantal items voor en na het doelnummer willekeurig is, is deze verbetering niet betrouwbaar.

In dat geval wilt u misschien de lijst doorzoeken door deze te partitioneren. Test of het middelste element groter is dan 4. Als het groter is, gooi de bovenste helft weg, gooi anders de onderste helft weg. Doe hetzelfde op de nieuwe lijst met halve lengte. U moet rekening houden met even en oneven getallen en met het geval wanneer u slechts 1 of 2 items over heeft in het lijstsegment. Voor een grote lijst zou dit het aantal testen aanzienlijk moeten verminderen.

2
toegevoegd