次のようなリストがある場合:
l = [1,2,3,4,5]
そして私は最後に持っていたい
min = 1
max = 5
なしmin(l)とmax(l)。
質問する
9562 次
8 に答える
8
2 つのループの使用を避けようとしていて、1 つのループの方が高速であることを期待している場合は、再検討する必要があります。2 つの O(N) 関数を呼び出しても、O(N) アルゴリズムが得られます。反復ごとの定数コストを 2 倍にするだけです。比較を伴う単一の Python ループも (データが既にソートされていない限り) O(N) よりも優れた処理を行うことはできず、各反復のバイトコードの解釈にもかなりの定数コストがかかります。どちらのアプローチがより高い定数コストを持つかは、実行のタイミングによってのみ決定できます。
これを 1 回のループで行うには、リストを繰り返し処理し、これまでに見つかった最小値と最大値に対して各項目をテストします。float('inf')およびfloat('-inf')(無限大と負の無限大) は、ロジックを単純化するための適切な出発点です。
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 の Tim Sort 実装は O(N log 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 個の要素のリストであっても、min()andmax()関数が最も高速です。ここではソートが最も遅くなります。その場での並べ替えを許可すると、並べ替えバージョンの方が高速になる可能性がありますが、時間制限のある実行ごとに新しいランダム リストも生成する必要があります。
100 万個のアイテム (および時間指定実行ごとに 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
最後になりましたが、100 万個のアイテムを使用し、l.sort()代わりにsorted():
>>> 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[:]。各テスト実行にリストのコピーを提供します。
結論: 大きなリストの場合でも、min()andmax()関数を使用したほうがよいでしょう。優れた C ループの反復あたりのコストが低いことに勝るものはありません。ただし、これらの機能を放棄する必要がある場合は、ストレート ループが次に適したオプションです。
于 2013-06-05T10:59:47.907 に答える
3
最大を見つけるには：
print reduce(lambda x,y: x if x>y else y, map(int,raw_input().split()))
分を見つけるには：
print reduce(lambda x,y: x if x<y else y, map(int,raw_input().split()))
于 2016-10-29T04:20:48.350 に答える
1
これは課題であるため、コードは提供しません。自分で理解する必要があります。ただし、基本的には、リストをループして、たとえば2 つの変数iMinを作成し、それぞれの値をその値と比較して、新しい変数をその値に割り当てます。iMaxiMiniMaxiBuf
于 2013-06-05T11:03:05.113 に答える
1
for ループを使用して、リスト内のすべての要素をループします。最大/最小値を格納する変数をリストの最初の要素に設定して開始します。そうしないと、無効な値になる可能性があります。
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<min_v:
min_v=i
于 2013-06-05T11:00:53.207 に答える
1
奇妙な制限のある宿題の質問は、チートの答えを要求します
>>> l = [1,2,3,4,5]
>>> sorted(l)[::len(l)-1]
[1, 5]
于 2013-06-05T11:13:17.787 に答える
0
>>> L = [1,2,3,4,5]
>>> reduce(lambda x, y: x if x<y else y, L)
1
>>> reduce(lambda x, y: x if x>y else y, L)
5
別の方法
>>> it = iter(L)
>>> mn = mx = next(it)
>>> for i in it:
... if i<mn:mn=i
... if i>mx:mx=i
...
>>> mn
1
>>> mx
5
于 2013-06-05T11:27:21.060 に答える
0
私が考えることができる最速のアプローチは、元のリストを並べ替えてから、最初と最後の要素を選択することです。これにより、複数回のループが回避されますが、リストの元の構造が破壊されます。これは、リストをコピーして、コピーしたリストのみをソートするだけで解決できます。これが、この簡単なサンプル スクリプトで max() と min() を使用するよりも遅いかどうかに興味がありました。
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
驚いたことに、私のコンピューターでは、2 番目の方法の方が約 10 ミリ秒高速です。これが非常に大きなリストでどれほど効果的かはわかりませんが、少なくとも提供したリストの例では、このアプローチの方が高速です。
@Martijn Pieters の単純なループ アルゴリズムをタイミング スクリプトに追加しました。（タイミングは、この質問で調査する価値のある唯一の重要なパラメーターになるためです。）私の結果は次のとおりです。
Run 1: 0.0199999809265s
Run 2: 0.00999999046326s
Run 3: 0.0299999713898s
編集：タイミングのための 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
並べ替えアルゴリズムは、大きな配列では非常に遅くなります。
于 2013-06-05T11:15:41.663 に答える