Як я магу атрымаць мінімальны і максімальны элемент спісу ў Python

Калі ёсць спіс, як:

l = [1,2,3,4,5]

і я хачу, каб у канцы

min = 1   
max = 5

БЕЗ мін (л) і макс (л) .

1
ёсць сапраўдная прычына невыкарыстання мін і макс ??
дададзена аўтар abhishekgarg, крыніца
Вы можаце сказаць, чаму вы не хочаце выкарыстоўваць мін (л) / макс (л) ? таму што, калі я адкажу на ваша пытанне тут, я дам вам алгарытмічная падыход даволі блізка да таго, мін() і MAX() ужо робіць.
дададзена аўтар zmo, крыніца

8 адказы

Калі вы спрабуеце пазбегнуць з дапамогай двух завес, спадзеючыся адзін цыкл будзе хутчэй, вам трэба перагледзець. Выклік два O (N) функцыі па-ранейшаму дае вам алгарытм O (N), усе вы робіце падвойная пастаяннай кошт за ітэрацыю. Адзін цыкл Python параўнанняў не можа зрабіць лепш, чым O (N) альбо (калі вашы дадзеныя ўжо адсартаваныя), і інтэрпрэтацыя байт-коды для кожнай ітэрацыі мае значныя пастаянныя выдаткі таксама. Які падыход мае больш высокую пастаянную кошт можа быць вызначана толькі па часе вашыя прабегі.

Для гэтага ў адным цыкле, ітэрацыя па спісе і праверыць кожны элемент супраць мінімуму і максімуму знайшоў да гэтага часу. <�Код> паплавок ( «інф») і паплавок ( «- інф») (бясконцасць і мінус бясконцасць) з'яўляюцца добрымі адпраўнымі кропкамі для спрашчэння логікі:

minimum = float('inf')
maximum = float('-inf')
for item in l:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

У якасці альтэрнатывы, пачаць з першым элементам і толькі завесамі над астатнім. Уключыце спіс у Iterable першы, захоўваць першы элемент у якасці выніку да даты, а затым цыкл над астатнімі:

iterl = iter(l)
minimum = maximum = next(iterl)
for item in iterl:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item

Не выкарыстоўваць сартаванне. Рэалізацыя Сартаваць Цім Python з'яўляецца O (N часопіс N) алгарытм, які можа быць як чакаецца, будзе больш павольна, чым падыход прамой уверх O (N).

Тэрміны параўнання з вялікім, у выпадковым парадку спісу:

>>> from random import shuffle
>>> l = list(range(1000))
>>> shuffle(l)
>>> from timeit import timeit
>>> def straight_min_max(l):
...     return min(l), max(l)
... 
>>> def sorted_min_max(l):
...     s = sorted(l)
...     return s[0], s[-1]
... 
>>> def looping(l):
...     l = iter(l)
...     min = max = next(l)
...     for i in l:
...         if i < min: min = i
...         if i > max: max = i
...     return min, max
... 
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10000)
0.5266690254211426
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10000)
2.162343978881836
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10000)
1.1799919605255127

Такім чынам, нават для спісаў 1000 элементаў, то мін() і макс() функцыі хутка. Сартаванне павольная тут. Сартавальная версія можа быць хутчэй, калі ўлічыць на месцы сартавання, але тады вам трэба згенераваць новы спіс для кожнага прымеркаванага запуску, а таксама.

Пераход на мільён пунктаў (і толькі 10 тэстаў у прымеркаванай перспектыве), мы бачым:

>>> l = list(range(1000000))
>>> shuffle(l)
>>> timeit('f(l)', 'from __main__ import straight_min_max as f, l', number=10)
1.6176080703735352
>>> timeit('f(l)', 'from __main__ import sorted_min_max as f, l', number=10)
6.310506105422974
>>> timeit('f(l)', 'from __main__ import looping as f, l', number=10)
1.7502741813659668

І апошняе, але не ў апошнюю чаргу, выкарыстоўваючы мільён элементаў і l.sort() замест адсартаваны() :

>>> def sort_min_max(l):
...     l.sort()
...     return l[0], l[-1]
... 
>>> timeit('f(l[:])', 'from __main__ import straight_min_max as f, l', number=10)
1.8858389854431152
>>> timeit('f(l[:])', 'from __main__ import sort_min_max as f, l', number=10)
8.408858060836792
>>> timeit('f(l[:])', 'from __main__ import looping as f, l', number=10)
2.003532886505127

Звярніце ўвагу на L [:] ; мы даем кожны тэст запусціць копію спісу.

Выснова: нават для вялікіх спісаў, вы лепш выкарыстоўваць мін() і макс() функцыі ў любым выпадку, гэта цяжка перасягнуць нізкія за-ітэрацыі кошту добрая пятля С. Але калі вы павінны адмовіцца ад гэтых функцый, прамая пятля з'яўляецца наступным лепшым варыянтам.

7
дададзена
У гэтай сітуацыі я б выкарыстоўваць ітэрацыю = ITER (л); мінімум = максімум = наступны (ітэрацыя) "шаблон". Гэта мае дадатковае перавага, што яна працуе з любой паслядоўнасцю, у той час як л [0] працуе толькі з індэксавацца паслядоўнасцямі.
дададзена аўтар Bakuriu, крыніца
Не, перапаўненне стэка для адказаў на пытанні. OP ніколі не прасіў намёкаў і мы тут не ў палітыцы паліцыі ў выкананні хатніх заданняў. Калі б я быў прафесарам, я будзе </я> задаць вострыя пытанні пра код у маёй абароне, калі ён быў адпраўлены ў якасці хатняга задання адказу, каб убачыць, калі студэнт разумее, што ён робіць <�я> дакладна .
дададзена аўтар Martijn Pieters, крыніца
@Bakuriu: +++ З памылкі кафеіну, паўтор ад пачатку +++. Вядома, лепшая ідэя, дадаў.
дададзена аўтар Martijn Pieters, крыніца
@jamylak: Можа быць, няма; гэта проста карабаціць з маім пачуццём патоку кода ..
дададзена аўтар Martijn Pieters, крыніца
@AjitZero: Я толькі што абнавіў адказ; выкліку спіс() на існуючы спіс досыць танна у рэшце рэшт.
дададзена аўтар Martijn Pieters, крыніца
спытаеце сябе, ці сапраўды гэта варта таго, каб прапусціць гэты адзін элемент;) Я бачу, як у C было б проста пачаць з індэксам 1 , але, магчыма, не так шмат тут
дададзена аўтар jamylak, крыніца
@MartijnPieters да я зрабіў бы тое ж самае
дададзена аўтар jamylak, крыніца
нармальна, як вы хочаце. Я не тролль пра гэта тут, як гэта ўжо было зроблена на мета , дзе гэта прыводзіць да маёй кропцы. Але, як вы даеце дзве розныя акуратныя спосабы яго рэалізацыі, калі ОП не чамусьці навучыцца, будучыя чытачы пытанні будуць, так што забудзьцеся аб маім каментары. :-)
дададзена аўтар zmo, крыніца
Вы павінны былі лепш далі яму падказкі замест таго, каб даць яму адказ, StackOverflow ня для выканання заданняў для студэнтаў! : -S (хоць ваша ідэя выкарыстання паплаўка інф вельмі акуратны ;-))
дададзена аўтар zmo, крыніца
Для Python 3, выкарыстоўвайце L = спіс (дыяпазон (1000)) замест таго, каб проста (дыяпазон (1000)) Гэта зэканоміць вам вынік пошуку
дададзена аўтар AjitZero, крыніца
@MartijnPieters, вельмі прыемна. Я думаю, што гэта ставіць гукавы вывад да гэтай дыскусіі.
дададзена аўтар Mink, крыніца

Хатняе заданне пытанні з жудаснымі абмежаваннямі патрабуюць накрутку адказаў

>>> l = [1,2,3,4,5]
>>> sorted(l)[::len(l)-1]
[1, 5]
1
дададзена

добра, бо гэта заданне, я не дам вам ніякага кода, вы павінны зразумець гэта самастойна. Але ў прынцыпе, вы цыкл па спісе, стварыць дзве зменныя Imin і IMAX , напрыклад, і для кожнага значэння параўнання Imin і Imax да гэтага значэння і прызначыць новую зменную iBuf ў тым, што адзін.

1
дададзена
Гэтыя імёны здаецца занадта ява-иш або любы іншы мову выкарыстоўваюць вярблюджыя + папярэднічаючы тып, які я лічу, гэта цалкам непрыгожа і ўводзіць у памылцы ў гэтым прыкладзе (дзе функцыя будзе працаваць з любым тыпам, які падтрымлівае параўнанне).
дададзена аўтар Bakuriu, крыніца
Я кажу ў агульным алгарытме, а не канкрэтныя пітона, і я я для значэння індэкс , а не цэлыя лікі . Я ні як вярблюджыя ў пітона, дарэчы.
дададзена аўтар zmo, крыніца

Перабор ўсіх элементаў у спісе з для цыклу. Ўсталяваць зменную, якая захоўвае максімальную/мін значэнне элемента кулачка ў спісе, каб пачаць з. У адваротным выпадку, вы маглі б у канчатковым выніку з недапушчальнымі значэннямі.

max_v=l[0]
for i in l:
    if i>max_v:
        max_v=i

min_v=l[0]
for i in l:
    if l
1
дададзена
Чаму двайны цыкл? Вы можаце пазбегнуць зацыклення тут двойчы.
дададзена аўтар Martijn Pieters, крыніца
@DXsmiley Я не згодны
дададзена аўтар jamylak, крыніца
Праўда, але я думаю, што гэта ясна з адукацыйнай пункту гледжання.
дададзена аўтар DXsmiley, крыніца

Для знаходжання макс:

print reduce(lambda x,y: x if x>y else y, map(int,raw_input().split()))

Для знаходжання мін:

print reduce(lambda x,y: x if x
1
дададзена
>>> L = [1,2,3,4,5]
>>> reduce(lambda x, y: x if x>> reduce(lambda x, y: x if x>y else y, L)
5

іншы спосаб

>>> it = iter(L)
>>> mn = mx = next(it)
>>> for i in it:
...  if imx:mx=i
... 
>>> mn
1
>>> mx
5
0
дададзена

Калі патрабуецца толькі адзін прабягаем па спісе, вы можаце выкарыстоўваць </паменшыць код> а (не так) творчы шлях. Дапаможная функцыя можа быць зменшана як лямбда, але я не раблю гэта дзеля чытальнасці:

>>> def f(solutions, item):
...     return (item if item < solutions[0] else solutions[0],
...             item if item > solutions[1] else solutions[1])
... 

>>> L = [i for i in range(5)]
>>> functools.reduce(f, L, (L[0],L[0]))
(0, 4)
0
дададзена

Самы хуткі падыход, які я магу думаць пра тое, каб адсартаваць зыходны спіс, а затым выбраць першыя і апошнія элементы. Гэта дазваляе пазбегнуць зацыклення некалькі разоў, але гэта не разбурыць першапачатковую структуру спісу. Гэтую праблему можна вырашыць шляхам простага капіявання спісу і сартавання толькі скапіяваны спіс. Мне было цікава, калі гэта было больш павольна, чым толькі з дапамогай макс() і мін() з гэтым хуткім прыкладам сцэнаром:

import time

l = [1,2,4,5,3]

print "Run 1"
t1 = time.time()
print "Min =", min(l)
print "Max =", max(l)
print "time =", time.time() - t1
print ""
print "l =", l
print ""


l = [1,2,4,5,3]
l1 = list(l)

print "Run 2"
t1 = time.time()
l1.sort()
print "Min =", l1[0]
print "Max =", l1[-1]
print "time =", time.time() - t1
print ""
print "l =", l
print "l1 =", l1
print ""


l = [1,2,4,5,3]

print "Run 3"
minimum = float('inf')
maximum = float('-inf')
for item in l:
    if item < minimum:
        minimum = item
    if item > maximum:
        maximum = item
print "Min =", minimum
print "Max =", maximum
print "time =", time.time() - t1
print ""
print "l =", l

Дзіўна, што другі падыход хутчэй прыкладна 10мс на маім кампутары. Не ўпэўнены, наколькі эфектыўна гэта будзе вельмі вялікі спіс, але гэты падыход хутчэй, па меншай меры, у прыкладзе спісу вы паказалі.

Я дадаў просты алгарытм цыклу @Martijn Пітэрс на мой сцэнар сінхранізацыі. (. У якасці часе будзе адзіны важны параметр варта даследаваць ў гэтым пытанні) Мае вынікі:

Run 1: 0.0199999809265s
Run 2: 0.00999999046326s
Run 3: 0.0299999713898s

Edit: Уключэнне модуля timeit для сінхранізацыі.

import timeit
from random import shuffle

l = range(10000)
shuffle(l)

def Run_1():
    #print "Min =", min(l)
    #print "Max =", max(l)
    return min(l), max(l)

def Run_2():
    l1 = list(l)
    l1.sort()
    #print "Min =", l1[0]
    #print "Max =", l1[-1]
    return l1[0], l1[-1]


def Run_3():
    minimum = float('inf')
    maximum = float('-inf')
    for item in l:
        if item < minimum:
            minimum = item
        if item > maximum:
            maximum = item
    #print "Min =", minimum
    #print "Max =", maximum
    return minimum, maximum


if __name__ == '__main__':
    num_runs = 10000
    print "Run 1"
    run1 = timeit.Timer(Run_1)
    time_run1 = run1.repeat(3, num_runs)
    print ""
    print "Run 2"
    run2 = timeit.Timer(Run_2)
    time_run2 = run2.repeat(3,num_runs)
    print ""
    print "Run 3"
    run3 = timeit.Timer(Run_3)
    time_run3 = run3.repeat(3,num_runs)
    print ""

    print "Run 1"
    for each_time in time_run1:
        print "time =", each_time
    print ""
    print "Run 2"
    for each_time in time_run2:
        print "time =", each_time
    print ""
    print "Run 3"
    for each_time in time_run3:
        print "time =", each_time
    print ""

Мае вынікі:

Run 1
time = 3.42100585452
time = 3.39309908229
time = 3.47903182233

Run 2
time = 26.5261287922
time = 26.2023346397
time = 26.7324208568

Run 3
time = 3.29800945144
time = 3.25067545773
time = 3.29783778232

Алгарытм сартавання вельмі павольна для вялікіх масіваў.

0
дададзена
І апошняя кропка дадзеных: выкарыстоўвайце правільна рандомізірованное спіс для праверкі сартавання() супраць прамой завесы або як на мін() і макс() </код > тэлефануйце; Алгарытм сартавання (TimSort) аптымізаваны для часткова адсартаваных даных; ваша ўваходная выбарка ў асноўным сартуецца (толькі 3 недарэчная).
дададзена аўтар Martijn Pieters, крыніца
І просты цыкл ўяўляе сабой Аб (п) складанасць, сартаванне ўяўляе сабой Аб (п § п); гэта можа быць, што пастаянныя выдаткі пітона для цыкл вышэй, чым код З пастаянных выдаткаў для сартавання, таму кароткі спіс можа быць хутчэй пры сартаванні, але і для <�я> вялікія </я > спісы, пятля выйграе, улічваючы дастаткова вялікі спіс.
дададзена аўтар Martijn Pieters, крыніца
Вы павінны выкарыстоўваць timeit модуля для ліквідацыі дысперсіі (працэсарныя, падпампоўкі і г.д.); ён будзе таксама выбраць правільны таймер для вашай платформы (найбольш дакладны варыянт).
дададзена аўтар Martijn Pieters, крыніца