Mendapatkan indeks item maks atau min yang dikembalikan menggunakan maks () / min () pada daftar

466

Saya menggunakan Python maxdan minfungsi pada daftar untuk algoritma minimax, dan saya perlu indeks dari nilai yang dikembalikan oleh max()atau min(). Dengan kata lain, saya perlu tahu langkah mana yang menghasilkan nilai maks (pada giliran pemain pertama) atau min (pemain kedua).

for i in range(9):
    newBoard = currentBoard.newBoardWithMove([i / 3, i % 3], player)

    if newBoard:
        temp = minMax(newBoard, depth + 1, not isMinLevel)  
        values.append(temp)

if isMinLevel:
    return min(values)
else:
    return max(values)

Saya harus dapat mengembalikan indeks aktual nilai min atau maks, bukan hanya nilai.

Kevin Griffin
sumber
32
Builtin divmodada untuk mencegah harus [i / 3, i % 3]banyak bicara .
Mike Graham

Jawaban:

416
ifMinLevel:
    return values.index (min (nilai))
lain:
    return values.index (maks (nilai))
terlalu banyak php
sumber
38
@KevinGriffin, Perhatikan bahwa ini hanya membuat Anda satu dari beberapa kemungkinan minimum / maksimum. Ini mungkin bukan yang Anda inginkan, misalnya jika memungkinkan untuk meningkatkan keuntungan Anda dengan dua cara yang sama, tetapi salah satunya lebih menyakitkan pemain lain. Saya tidak tahu apakah ini kasus yang perlu Anda pertimbangkan.
Mike Graham
89
@ Kashyap Ini sebenarnya O (N), bukan O (N ^ 2). Dalam kasus min, min pertama (nilai) dievaluasi, yaitu O (N), lalu values.index () disebut, yang juga O (N). O (N) + O (N) = O (N). Argumen untuk mengindeks hanya dievaluasi satu kali. Ini setara dengan:tmp = min(values); return values.index(tmp)
Tom Karzes
@ terlalu banyak php apa yang harus dilakukan ketika ada pengulangan elemen.?
Shashi Tunga
@ShashiTunga [list] .index () mengembalikan hanya kemunculan pertama sesuatu, tidak dijamin eksklusif, nilai minimum mungkin tidak unik dalam daftar
Scott Anderson
473

Katakan bahwa Anda memiliki daftar values = [3,6,1,5], dan perlu indeks elemen terkecil, yaitu index_min = 2dalam hal ini.

Hindari solusi dengan itemgetter()disajikan dalam jawaban lain, dan gunakan sebaliknya

index_min = min(range(len(values)), key=values.__getitem__)

karena tidak perlu import operatoratau tidak digunakan enumerate, dan selalu lebih cepat (patokan di bawah) daripada menggunakan solusi itemgetter().

Jika Anda berurusan dengan array numpy atau mampu numpysebagai ketergantungan, pertimbangkan juga untuk menggunakannya

import numpy as np
index_min = np.argmin(values)

Ini akan lebih cepat daripada solusi pertama bahkan jika Anda menerapkannya ke daftar Python murni jika:

  • ini lebih besar dari beberapa elemen (sekitar 2 ** 4 elemen pada mesin saya)
  • Anda dapat membeli salinan memori dari daftar murni ke numpyarray

seperti yang ditunjukkan oleh tolok ukur ini: masukkan deskripsi gambar di sini

Saya telah menjalankan benchmark pada mesin saya dengan python 2.7 untuk dua solusi di atas (biru: python murni, solusi pertama) (merah, solusi numpy) dan untuk solusi standar berdasarkan itemgetter()(hitam, solusi referensi). Patokan yang sama dengan python 3.5 menunjukkan bahwa metode membandingkan persis sama dari kasus python 2.7 yang disajikan di atas

gg349
sumber
+1 yang sangat kuat. Saya suka pembandingan solusi yang diusulkan dan aturan praktis yang telah Anda rangkum. Seperti yang saya sarankan dalam jawaban lain di bawah ini, dapatkah Anda memberikan (atau menautkan ke) kode pengujian Anda sehingga orang lain dapat mereproduksi hasil Anda? Mesin dan perpustakaan berubah seiring waktu, dan itu akan memungkinkan membandingkan dengan solusi lain.
Rakurai
3
Saya pikir mungkin ada salah ketik: xrange. Bukankah seharusnya rentang?
Lindsay Fowler
6
@LindsayFowler xrange()sekarang sudah tidak digunakan lagi, Anda dapat menggunakanrange()
davide
np.argmin tidak berfungsi untuk mengapung. hanya saran pertama yang bekerja pada int dan mengapung.
jimh
Saya pikir Anda salah, cobalah import numpy as np; x = [2.3, -1.4]; np.argmin(x). Anda akan melihat bahwa itu juga argminberfungsi pada float
gg349
332

Anda dapat menemukan indeks min / maks dan nilai pada saat yang sama jika Anda menghitung item dalam daftar, tetapi melakukan min / maks pada nilai-nilai asli daftar. Seperti itu:

import operator
min_index, min_value = min(enumerate(values), key=operator.itemgetter(1))
max_index, max_value = max(enumerate(values), key=operator.itemgetter(1))

Dengan cara ini daftar hanya akan dilintasi satu kali untuk min (atau maks).

Matt Anderson
sumber
110
Atau gunakan lambda:key=lambda p: p[1]
scry
116

Jika Anda ingin menemukan indeks max dalam daftar angka (yang tampaknya seperti kasus Anda), maka saya sarankan Anda menggunakan numpy:

import numpy as np
ind = np.argmax(mylist)
dr.haz
sumber
Dalam kasus beberapa kejadian nilai maksimum, indeks yang sesuai dengan kejadian pertama dikembalikan.
Cohensius
41

Mungkin solusi yang lebih sederhana adalah mengubah array nilai menjadi array nilai, pasangan indeks, dan mengambil maks / min dari itu. Ini akan memberikan indeks terbesar / terkecil yang memiliki max / min (yaitu pasangan dibandingkan dengan terlebih dahulu membandingkan elemen pertama, dan kemudian membandingkan elemen kedua jika yang pertama adalah sama). Perhatikan bahwa tidak perlu untuk benar-benar membuat array, karena min / max memungkinkan generator sebagai input.

values = [3,4,5]
(m,i) = max((v,i) for i,v in enumerate(values))
print (m,i) #(5, 2)
Ant6n
sumber
30
list=[1.1412, 4.3453, 5.8709, 0.1314]
list.index(min(list))

Akan memberi Anda indeks minimum pertama.

Andy
sumber
18

Saya pikir hal terbaik untuk dilakukan adalah mengonversi daftar menjadi a numpy arraydan menggunakan fungsi ini:

a = np.array(list)
idx = np.argmax(a)
Akshaya Natarajan
sumber
14

Saya juga tertarik dengan ini dan membandingkan beberapa solusi yang disarankan menggunakan perfplot (proyek kesayangan saya).

Ternyata argmin numpy itu ,

numpy.argmin(x)

adalah metode tercepat untuk daftar yang cukup besar, bahkan dengan konversi implisit dari input listke a numpy.array.

masukkan deskripsi gambar di sini


Kode untuk menghasilkan plot:

import numpy
import operator
import perfplot


def min_enumerate(a):
    return min(enumerate(a), key=lambda x: x[1])[0]


def min_enumerate_itemgetter(a):
    min_index, min_value = min(enumerate(a), key=operator.itemgetter(1))
    return min_index


def getitem(a):
    return min(range(len(a)), key=a.__getitem__)


def np_argmin(a):
    return numpy.argmin(a)


perfplot.show(
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[
        min_enumerate,
        min_enumerate_itemgetter,
        getitem,
        np_argmin,
        ],
    n_range=[2**k for k in range(15)],
    logx=True,
    logy=True,
    )
Nico Schlömer
sumber
Perhatikan bahwa kesimpulan yang sama sudah diposting di atas dalam jawaban saya, lebih dari 2 tahun yang lalu, dengan lebih banyak informasi tentang kapan dan mengapa argmin dapat digunakan atau tidak. Pertimbangkan untuk menghapus jawaban, yang juga tidak memberi manfaat pada apa yang sudah diusulkan pada halaman yang sama. Pertimbangkan juga untuk meninjau jawaban Anda yang lain pada SO untuk perilaku yang serupa: Anda tampaknya tidak mengutip jawaban sebenarnya yang memberikan solusi terbaik dalam analisis kinerja Anda. Ini agak buruk, terutama untuk seseorang dengan rep> 10K yang sudah cukup lama untuk mengenal lebih baik.
gg349
@ gg349, poin yang sangat bagus, tetapi ia memang menyediakan kode sumber untuk menghasilkan hasilnya, membuatnya mudah direproduksi dan disesuaikan dengan membandingkan solusi lain. Saya setuju bahwa dia mungkin mempertimbangkan untuk menghapus jawaban ini sebagai duplikat, tetapi mungkin Anda dapat menambah nilai pada jawaban Anda dengan memasukkan atau menautkan ke kode yang Anda gunakan?
Rakurai
8

Gunakan array numpy dan fungsi argmax ()

 a=np.array([1,2,3])
 b=np.argmax(a)
 print(b) #2
John Misquita
sumber
8

Setelah Anda mendapatkan nilai maksimum, coba ini:

max_val = max(list)
index_max = list.index(max_val)

Jauh lebih sederhana daripada banyak opsi.

alpha_989
sumber
6

Saya pikir jawaban di atas menyelesaikan masalah Anda, tetapi saya pikir saya akan membagikan metode yang memberi Anda minimum dan semua indeks minimum muncul.

minval = min(mylist)
ind = [i for i, v in enumerate(mylist) if v == minval]

Ini melewati daftar dua kali tetapi masih cukup cepat. Namun itu sedikit lebih lambat daripada menemukan indeks pertemuan pertama minimum. Jadi, jika Anda hanya membutuhkan satu dari minimum, gunakan solusi Matt Anderson , jika Anda membutuhkan semuanya, gunakan ini.

Burak Bağdatlı
sumber
1
Saya suka ini karena menggunakan basis Python, dan saya menemukan daftar pemahaman lebih mudah dipahami daripada itemgetter, lambda dll (dan cukup fleksibel untuk menyelesaikan berbagai tugas, seperti ini ....)
James
mentah. Saya lebih memilih ini.
Dev_Man
6

Gunakan fungsi modul numpy numpy.where

import numpy as n
x = n.array((3,3,4,7,4,56,65,1))

Untuk indeks nilai minimum:

idx = n.where(x==x.min())[0]

Untuk indeks nilai maksimum:

idx = n.where(x==x.max())[0]

Bahkan, fungsi ini jauh lebih kuat. Anda dapat mengajukan semua jenis operasi boolean Untuk indeks nilai antara 3 dan 60:

idx = n.where((x>3)&(x<60))[0]
idx
array([2, 3, 4, 5])
x[idx]
array([ 4,  7,  4, 56])
Ishan Tomar
sumber
indeks dalam python dimulai pada 0. indeks dikembalikan akan menjadi 6 (untuk 65), sedangkan kode Anda mengembalikan 7 (pertanyaan OP adalah "Mendapatkan indeks ...")
tagoma
Dalam perintah, saya telah meminta indeks nilai minimum (di sini: 1) yang indeks IS 7. 65 adalah nilai maksimum elemen dalam array. Jika Anda mengetik: n.where (x == x.max ()) [0] Anda akan mendapatkan indeks maks. nilai yang 65 di sini. Indeksnya akan keluar menjadi 6
Ishan Tomar
penggunaan numpy: mungkin dilarang di aplikasi ini. Tetapi jika Anda akan menggunakan numpy, Anda lebih baik hanya menggunakan argmin()daripada apa yang Anda lakukan di sini.
RBF06
Terima kasih @ RBF06 saya akan memeriksanya.
Ishan Tomar
5

Ini sangat mungkin menggunakan built-in enumerate()dan max()fungsi serta keyargumen opsional max()fungsi dan ekspresi lambda sederhana:

theList = [1, 5, 10]
maxIndex, maxValue = max(enumerate(theList), key=lambda v: v[1])
# => (2, 10)

Dalam dokumen untuk max()itu dikatakan bahwa keyargumen mengharapkan fungsi seperti dalam list.sort()fungsi. Lihat juga Cara Menyortir .

Ini berfungsi sama untuk min(). Btw mengembalikan nilai max / min pertama.

Simon Hänisch
sumber
Terlambat tetapi jawaban terbaik (jika Anda tidak membutuhkan kecepatan).
mmj
5

Katakanlah Anda memiliki daftar seperti:

a = [9,8,7]

Dua metode berikut adalah cara yang cukup ringkas untuk mendapatkan tuple dengan elemen minimum dan indeksnya. Keduanya membutuhkan waktu yang sama untuk diproses. Saya lebih suka metode zip, tapi itu selera saya.

metode zip

element, index = min(list(zip(a, range(len(a)))))

min(list(zip(a, range(len(a)))))
(7, 2)

timeit min(list(zip(a, range(len(a)))))
1.36 µs ± 107 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

menghitung metode

index, element = min(list(enumerate(a)), key=lambda x:x[1])

min(list(enumerate(a)), key=lambda x:x[1])
(2, 7)

timeit min(list(enumerate(a)), key=lambda x:x[1])
1.45 µs ± 78.1 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
Pablo MPA
sumber
4

Selama Anda tahu cara menggunakan lambda dan argumen "kunci", solusi sederhana adalah:

max_index = max( range( len(my_list) ), key = lambda index : my_list[ index ] )
Veiga
sumber
Sangat bersih! Dan tidak seperti jawaban yang diterima, ini benar O (n), kan? Saya tahu bahwa O (2n) dianggap O (n), tetapi untuk yang sangat besar nitu bisa terasa lebih lambat.
kevlarr
4

Sederhana seperti itu :

stuff = [2, 4, 8, 15, 11]

index = stuff.index(max(stuff))
dctremblay
sumber
3

Mengapa repot-repot menambahkan indeks terlebih dahulu dan kemudian membalikkannya? Enumerate () function hanyalah kasus khusus dari penggunaan fungsi zip (). Mari kita gunakan dengan cara yang tepat:

my_indexed_list = zip(my_list, range(len(my_list)))

min_value, min_index = min(my_indexed_list)
max_value, max_index = max(my_indexed_list)
sofis
sumber
2

Hanya tambahan kecil dari apa yang telah dikatakan. values.index(min(values))tampaknya mengembalikan indeks min terkecil. Berikut ini mendapatkan indeks terbesar:

    values.reverse()
    (values.index(min(values)) + len(values) - 1) % len(values)
    values.reverse()

Baris terakhir dapat ditinggalkan jika efek samping dari pembalikan di tempat tidak masalah.

Untuk mengulangi semua kejadian

    indices = []
    i = -1
    for _ in range(values.count(min(values))):
      i = values[i + 1:].index(min(values)) + i + 1
      indices.append(i)

Demi singkatnya. Mungkin ide yang lebih baik untuk melakukan cache di min(values), values.count(min)luar loop.

hiperbolis
sumber
2
reversed(…)bukannya ….reverse()lebih disukai karena tidak bermutasi dan mengembalikan generator. Dan semua kejadian juga bisaminv = min(values); indices = [i for i, v in enumerate(values) if v == minv]
HoverHell
2

Cara mudah untuk menemukan indeks dengan nilai minimal dalam daftar jika Anda tidak ingin mengimpor modul tambahan:

min_value = min(values)
indexes_with_min_value = [i for i in range(0,len(values)) if values[i] == min_value]

Kemudian pilih misalnya yang pertama:

choosen = indexes_with_min_value[0]
antoninstuppa
sumber
1

Jangan punya rep yang cukup tinggi untuk mengomentari jawaban yang ada.

Tetapi untuk https://stackoverflow.com/a/11825864/3920439 jawabannya

Ini berfungsi untuk bilangan bulat, tetapi tidak berfungsi untuk array float (setidaknya dalam python 3.6) Ini akan naik TypeError: list indices must be integers or slices, not float

ThePianoDentist
sumber
0

https://docs.python.org/3/library/functions.html#max

Jika beberapa item maksimal, fungsi mengembalikan item pertama yang ditemui. Ini konsisten dengan alat pengawet semacam stabilitas sepertisorted(iterable, key=keyfunc, reverse=True)[0]

Untuk mendapatkan lebih dari sekedar yang pertama, gunakan metode sortir.

import operator

x = [2, 5, 7, 4, 8, 2, 6, 1, 7, 1, 8, 3, 4, 9, 3, 6, 5, 0, 9, 0]

min = False
max = True

min_val_index = sorted( list(zip(x, range(len(x)))), key = operator.itemgetter(0), reverse = min )

max_val_index = sorted( list(zip(x, range(len(x)))), key = operator.itemgetter(0), reverse = max )


min_val_index[0]
>(0, 17)

max_val_index[0]
>(9, 13)

import ittertools

max_val = max_val_index[0][0]

maxes = [n for n in itertools.takewhile(lambda x: x[0] == max_val, max_val_index)]
Demz
sumber
0

Bagaimana dengan ini:

a=[1,55,2,36,35,34,98,0]
max_index=dict(zip(a,range(len(a))))[max(a)]

Itu membuat kamus dari item dalam asebagai kunci dan indeks mereka sebagai nilai, sehingga dict(zip(a,range(len(a))))[max(a)]mengembalikan nilai yang sesuai dengan kunci max(a)yang merupakan indeks maksimum dalam. Saya seorang pemula dalam python jadi saya tidak tahu tentang kompleksitas komputasi dari solusi ini.

Dr.Simplisist
sumber