Uzyskiwanie indeksu zwróconej pozycji maks. Lub min. Za pomocą max () / min () na liście

465

Używam Pythona maxi minfunkcji na listach dla algorytmu minimax i potrzebuję indeksu wartości zwróconej przez max()lub min(). Innymi słowy, muszę wiedzieć, który ruch wytworzył wartość maksymalną (podczas tury pierwszego gracza) lub wartość minimalną (drugiego gracza).

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)

Muszę być w stanie zwrócić rzeczywisty indeks wartości minimalnej lub maksymalnej, a nie tylko wartość.

Kevin Griffin
źródło
32
Wbudowane divmodistnieje, aby nie musieć [i / 3, i % 3]wiele mówić .
Mike Graham

Odpowiedzi:

416
if isMinLevel:
    zwracane wartości. indeks (min (wartości))
jeszcze:
    zwracane wartości. indeks (maks. (wartości))
za dużo php
źródło
38
@KevinGriffin, pamiętaj, że dzięki temu uzyskasz tylko jedno z kilku możliwych minimum / maksimum. To może nie być to, czego chcesz, na przykład, jeśli możesz zwiększyć swój zysk w ten sam sposób, ale jeden z nich bardziej rani drugiego gracza. Nie wiem, czy jest to przypadek, który należy rozważyć.
Mike Graham
89
@ Kashyap To właściwie O (N), a nie O (N ^ 2). W przypadku min jest obliczana pierwsza min (wartości), która jest O (N), a następnie wywoływane są wartości values.index (), które również jest O (N). O (N) + O (N) = O (N). Argument do indeksowania jest oceniany tylko raz. Odpowiada to:tmp = min(values); return values.index(tmp)
Tomowi Karzesowi
@ zbyt dużo php co zrobić, gdy występuje powtórzenie elementów.?
Shashi Tunga
@ShashiTunga [lista] .index () zwraca tylko pierwsze wystąpienie czegoś, nie ma gwarancji, że jest wyłączne, minimalna wartość może nie być unikalna na liście
Scott Anderson
471

Powiedz, że masz listę values = [3,6,1,5]i potrzebujesz indeksu najmniejszego elementu, czyli index_min = 2w tym przypadku.

Unikaj rozwiązania itemgetter()przedstawionego w innych odpowiedziach i użyj zamiast tego

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

ponieważ nie wymaga import operatorani nie używa enumerate, i zawsze jest szybszy (benchmark poniżej) niż rozwiązanie itemgetter().

Jeśli masz do czynienia z tablicami numpy lub możesz sobie pozwolić numpy na zależność, rozważ również użycie

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

Będzie to szybsze niż pierwsze rozwiązanie, nawet jeśli zastosujesz go do czystej listy Python, jeśli:

  • jest większy niż kilka elementów (około 2 ** 4 elementy na moim komputerze)
  • możesz sobie pozwolić na kopię pamięci z czystej listy do numpytablicy

jak wskazuje ten punkt odniesienia: wprowadź opis zdjęcia tutaj

Uruchomiłem test porównawczy na moim komputerze z Pythonem 2.7 dla dwóch powyższych rozwiązań (niebieski: czysty python, pierwsze rozwiązanie) (czerwony, numpy) i dla standardowego rozwiązania opartego na itemgetter()(czarny, rozwiązanie referencyjne). Ten sam test porównawczy z python 3.5 pokazał, że metody porównują dokładnie to samo z powyższym przypadkiem python 2.7

gg349
źródło
Bardzo silny +1. Uwielbiam analizę porównawczą proponowanych rozwiązań i zasady, które streściłeś. Jak zasugerowałem w innej odpowiedzi poniżej, czy możesz podać (lub link do) kod testowy, aby inni mogli powielać twoje wyniki? Maszyny i biblioteki zmieniają się z czasem i pozwoliłoby to na porównanie z innymi rozwiązaniami.
Rakurai
3
Myślę, że może być literówka: xrange. Czy nie powinien to być zasięg?
Lindsay Fowler
6
@LindsayFowler xrange()jest już nieaktualny, możesz go używaćrange()
David
np.argmin nie działa dla pływaków. tylko pierwsza sugestia działa na liczbach całkowitych i zmiennoprzecinkowych.
jimh
Myślę, że się mylisz, spróbuj import numpy as np; x = [2.3, -1.4]; np.argmin(x). Zobaczysz, że argmindziała również na pływakach
gg349
332

Możesz znaleźć indeks i wartość min / max w tym samym czasie, jeśli wyliczysz pozycje na liście, ale wykonasz min / max na oryginalnych wartościach listy. Tak jak:

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

W ten sposób lista będzie przeglądana tylko raz przez min (lub max).

Matt Anderson
źródło
110
Lub użyj lambda:key=lambda p: p[1]
scry
116

Jeśli chcesz znaleźć indeks maksymalny na liście liczb (co wydaje się twoim przypadkiem), sugeruję użycie numpy:

import numpy as np
ind = np.argmax(mylist)
dr.haz
źródło
W przypadku wielokrotnego wystąpienia wartości maksymalnych zwracane są wskaźniki odpowiadające pierwszemu wystąpieniu.
Cohensius
41

Być może prostszym rozwiązaniem byłoby przekształcenie tablicy wartości w tablicę wartości, pary indeksów i przyjęcie jej maksimum / min. Dałoby to największy / najmniejszy indeks, który ma maksimum / min (tzn. Pary są porównywane najpierw przez porównanie pierwszego elementu, a następnie porównanie drugiego elementu, jeśli pierwsze są takie same). Zauważ, że nie jest konieczne tworzenie tablicy, ponieważ min / max zezwalają na generatory jako dane wejściowe.

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

Otrzymasz pierwszy indeks minimum.

Andy
źródło
18

Myślę, że najlepiej jest przekonwertować listę na numpy arrayi użyć tej funkcji:

a = np.array(list)
idx = np.argmax(a)
Akshaya Natarajan
źródło
14

Byłem również tym zainteresowany i porównałem niektóre z sugerowanych rozwiązań za pomocą perfplot ( projektu dla zwierząt domowych).

Okazuje się, że argmin tego numpy ,

numpy.argmin(x)

jest najszybszą metodą dla wystarczająco dużych list, nawet z niejawną konwersją z danych wejściowych listna a numpy.array.

wprowadź opis zdjęcia tutaj


Kod do generowania wykresu:

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
źródło
Zauważ, że ten sam wniosek został zamieszczony już powyżej w mojej odpowiedzi, ponad 2 lata temu, z większą ilością informacji o tym, kiedy i dlaczego argmin może być użyty, czy nie. Zastanów się nad usunięciem odpowiedzi, która również nie uzasadnia tego, co zostało już zaproponowane na tej samej stronie. Rozważ również przejrzenie innych odpowiedzi w SO pod kątem podobnego zachowania: wydaje się, że nie przytaczasz rzeczywistej odpowiedzi, zapewniając najlepsze rozwiązanie w analizach wydajności. Jest to dość złe, szczególnie dla kogoś z> 10K powtórzeń, który był na tyle długo, aby wiedzieć lepiej.
gg349
@ gg349, bardzo dobre punkty, ale zapewnia kod źródłowy do generowania wyników, dzięki czemu jest łatwo powtarzalny i można go dostosować do porównania innych rozwiązań. Zgadzam się, że może rozważyć usunięcie tej odpowiedzi jako duplikatu, ale być może mógłbyś zwiększyć wartość swojej odpowiedzi, dołączając lub łącząc się z użytym kodem?
Rakurai
8

Użyj tablicy numpy i funkcji argmax ()

 a=np.array([1,2,3])
 b=np.argmax(a)
 print(b) #2
John Misquita
źródło
8

Po uzyskaniu maksymalnych wartości spróbuj wykonać następujące czynności:

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

Znacznie prostsze niż wiele opcji.

alpha_989
źródło
6

Myślę, że powyższa odpowiedź rozwiązuje twój problem, ale pomyślałem, że podzielę się metodą, która daje ci minimum i wszystkie wskaźniki, w których pojawia się minimum.

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

To mija listę dwa razy, ale wciąż jest dość szybkie. Jest jednak nieco wolniejszy niż znalezienie wskaźnika pierwszego spotkania minimum. Więc jeśli potrzebujesz tylko jednego minimum, skorzystaj z rozwiązania Matta Andersona , jeśli potrzebujesz ich wszystkich, skorzystaj z tego.

Burak Bağdatlı
źródło
1
Podoba mi się to, ponieważ używa podstawowego Pythona, a zrozumienie listy jest łatwiejsze do zrozumienia niż itemgetter, lambda itp. (I wystarczająco elastyczne, aby rozwiązywać różne zadania, takie jak to ...)
James
surowy. Wolę to.
Dev_Man
6

Użyj funkcji numpy modułu numpy.where

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

Dla indeksu wartości minimalnej:

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

Dla indeksu wartości maksymalnej:

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

W rzeczywistości ta funkcja jest znacznie potężniejsza. Możesz tworzyć wszelkiego rodzaju operacje boolowskie. Dla indeksu wartości od 3 do 60:

idx = n.where((x>3)&(x<60))[0]
idx
array([2, 3, 4, 5])
x[idx]
array([ 4,  7,  4, 56])
Ishan Tomar
źródło
indeks w pythonie zaczyna się od 0. zwróconym indeksem będzie 6 (dla 65), podczas gdy twój kod zwraca 7 (pytanie OP brzmiało „Pobieranie indeksu ...”)
tagoma
W poleceniu zapytałem o indeks wartości minimalnej (tutaj: 1), którego indeks IS 7. 65 jest maksymalną wartością elementów w tablicy. Jeśli wpiszesz: n.where (x == x.max ()) [0] otrzymasz indeks max. wartość, która wynosi tutaj 65. Jego indeks wyniesie 6
Ishan Tomar
korzystanie z numpy: prawdopodobnie zabronione w tej aplikacji. Ale jeśli zamierzasz używać numpy, lepiej jest po prostu używać argmin()zamiast tego, co tutaj zrobiłeś.
RBF06
Dzięki @ RBF06 Sprawdzę to.
Ishan Tomar
5

To jest po prostu możliwe przy użyciu wbudowanych enumerate()i max()funkcji i opcjonalnego keyargumentu max()funkcji i prostego wyrażenia lambda:

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

W dokumentacji max()napisano, że keyargument oczekuje funkcji takiej jak w list.sort()funkcji. Zobacz także Sortowanie .

Działa to samo dla min(). Btw zwraca pierwszą wartość maks./min.

Simon Hänisch
źródło
Późna, ale najlepsza odpowiedź (jeśli nie potrzebujesz prędkości).
mmj
5

Powiedz, że masz listę, taką jak:

a = [9,8,7]

Poniższe dwie metody to dość kompaktowe sposoby uzyskania krotki z minimalnym elementem i jego indeksem. Oba mają podobne czas do przetworzenia. Bardziej podoba mi się metoda zip, ale taki jest mój gust.

metoda 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)

wyliczyć metodę

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
źródło
4

Tak długo, jak wiesz, jak używać lambda i argumentu „klucz”, proste rozwiązanie to:

max_index = max( range( len(my_list) ), key = lambda index : my_list[ index ] )
Veiga
źródło
Bardzo czysto! I w przeciwieństwie do przyjętej odpowiedzi, to prawda O (n), prawda? Wiem, że O (2n) jest uważane za O (n), ale dla bardzo dużych nmoże być zauważalnie wolniejsze.
kevlarr
4

Proste :

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

index = stuff.index(max(stuff))
dctremblay
źródło
3

Po co zawracać sobie głowę dodawaniem indeksów, a następnie ich odwracaniem? Funkcja Enumerate () jest tylko specjalnym przypadkiem użycia funkcji zip (). Użyjmy go w odpowiedni sposób:

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)
sofista
źródło
2

Tylko drobny dodatek do tego, co już powiedziano. values.index(min(values))wydaje się zwracać najmniejszy indeks min. Największy indeks otrzymuje następujący:

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

Ostatni wiersz można pominąć, jeśli efekt uboczny cofnięcia w miejscu nie ma znaczenia.

Aby iterować przez wszystkie wystąpienia

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

Ze względu na zwięzłość. Prawdopodobnie lepszym pomysłem jest buforowanie min(values), values.count(min)poza pętlą.

hiperboliczny
źródło
2
reversed(…)zamiast ….reverse()jest prawdopodobnie preferowane, ponieważ i tak nie mutuje i zwraca generator. I wszystkie zdarzenia mogą być równieżminv = min(values); indices = [i for i, v in enumerate(values) if v == minv]
HoverHell
2

Prosty sposób na znalezienie indeksów o minimalnej wartości na liście, jeśli nie chcesz importować dodatkowych modułów:

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

Następnie wybierz na przykład pierwszy:

choosen = indexes_with_min_value[0]
antoninstuppa
źródło
1

Nie masz wystarczająco wysokiego przedstawiciela, aby skomentować istniejącą odpowiedź.

Ale dla https://stackoverflow.com/a/11825864/3920439 odpowiedź

Działa to dla liczb całkowitych, ale nie działa dla tablicy liczb zmiennoprzecinkowych (przynajmniej w Pythonie 3.6) TypeError: list indices must be integers or slices, not float

ThePianoDentist
źródło
0

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

Jeśli maksymalna liczba elementów jest maksymalna, funkcja zwraca pierwszy napotkany. Jest to zgodne z innymi narzędziami zabezpieczającymi stabilność sortowania, takimi jaksorted(iterable, key=keyfunc, reverse=True)[0]

Aby uzyskać więcej niż tylko pierwszą, użyj metody sortowania.

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)]
The Demz
źródło
0

A co z tym:

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

It creates a dictionary from the items in a as keys and their indexes as values, thus dict(zip(a,range(len(a))))[max(a)] returns the value that corresponds to the key max(a) which is the index of the maximum in a. I'm a beginner in python so I don't know about the computational complexity of this solution.

Dr.Simplisist
źródło