Wie finde ich alle Positionen des Maximalwertes in einer Liste?

152

Ich habe eine Liste:

a = [32, 37, 28, 30, 37, 25, 27, 24, 35, 55, 23, 31, 55, 21, 40, 18, 50,
             35, 41, 49, 37, 19, 40, 41, 31]

Das maximale Element ist 55 (zwei Elemente an Position 9 und 12).

Ich muss herausfinden, an welcher Position (en) sich der Maximalwert befindet. Bitte helfen Sie.

Bob
quelle

Antworten:

210
>>> m = max(a)
>>> [i for i, j in enumerate(a) if j == m]
[9, 12]
SilentGhost
quelle
4
Schöne kurze Antwort, wenn es Ihnen nichts ausmacht, mehrere Durchgänge durch die Liste zu machen - was wahrscheinlich ist.
Martineau
Mit der Ausnahme, dass die große 0 dafür 2n ist, wird die Liste 2x durchlaufen, einmal, um das Maximum zu bestimmen, und ein anderes Mal, um die Positionen des Maximums zu finden. Eine for-Schleife, die das aktuelle Maximum und seine Position verfolgt, ist möglicherweise für sehr lange Listen effizienter.
Radtek
1
@radtek big O ist nur n. führende Koeffizienten werden in großen O
michaelsnowden
1
Theoretisch sind O (N) und O (2N) gleich, aber praktisch hat O (N) definitiv eine kürzere Laufzeit, insbesondere wenn N gegen unendlich geht.
Radtek
313
a.index(max(a))

zeigt Ihnen den Index der ersten Instanz des größten bewerteten Elements der Liste an a.

nmichaels
quelle
8
Dadurch erhalten Sie jedoch nur die erste Instanz und er hat nach allen Indizes gefragt, in denen der größte Wert gefunden wird. Sie müssten dies mit Slice wiederholen, um die jeweils verbleibende Liste abzurufen und die Ausnahme zu behandeln, wenn sie nicht mehr gefunden wird.
Jaydel
10
Ich habe erwähnt, dass es nur die erste Instanz geben würde. Wenn Sie alle möchten, ist die Lösung von SilentGhost viel hübscher und weniger fehleranfällig.
Nmichaels
7
Zumindest als ich dazu kam, fragt die Frage ausdrücklich nach einer Liste für mehrere Maxima ...
Emmagras
2
Technisch gesehen könnten Sie dies verwenden, um die erste Instanz des Elements mit dem größten Wert abzurufen und es dann auf eine lächerlich große negative Zahl zu setzen und dann das Element mit dem nächstgrößeren Wert zu finden, aber das wäre zu komplex.
Neil Chowdhury
@nmichaels Gibt es eine beste Möglichkeit, alle Positionen mit maximalem Wert in einer Liste als die akzeptierte Antwort zu erhalten?
Shaik Moeed
18

Die gewählte Antwort (und die meisten anderen) erfordern mindestens zwei Durchgänge durch die Liste.
Hier ist eine One-Pass-Lösung, die für längere Listen die bessere Wahl sein könnte.

Bearbeitet: Um die beiden von @John Machin aufgezeigten Mängel zu beheben. Für (2) habe ich versucht, die Tests basierend auf der geschätzten Wahrscheinlichkeit des Auftretens jeder Bedingung und den Schlussfolgerungen der Vorgänger zu optimieren. Es war ein wenig schwierig , die richtigen Initialisierungswerte für herauszufinden , max_valund max_indicesdie für alle möglichen Fälle gearbeitet, vor allem , wenn der max der erste Wert in der Liste zufällig - aber ich glaube , dass es jetzt der Fall ist.

def maxelements(seq):
    ''' Return list of position(s) of largest element '''
    max_indices = []
    if seq:
        max_val = seq[0]
        for i,val in ((i,val) for i,val in enumerate(seq) if val >= max_val):
            if val == max_val:
                max_indices.append(i)
            else:
                max_val = val
                max_indices = [i]

    return max_indices
Martineau
quelle
4
(1) Die Behandlung leerer Listen bedarf der Aufmerksamkeit. Sollte wie angegeben zurückkehren []("Rückgabeliste"). Code sollte einfach sein if not seq: return []. (2) Das Testschema in der Schleife ist nicht optimal: Im Durchschnitt in Zufallslisten ist die Bedingung val < maxvalam häufigsten, aber der obige Code benötigt 2 Tests anstelle von einem.
John Machin
+1 zu @John Machins Kommentar, weil er die Inkonsistenz mit der Dokumentzeichenfolge aufgefangen hat und mich nicht davonkommen ließ, suboptimalen Code zu veröffentlichen. Um ehrlich zu sein, da eine Antwort bereits angenommen wurde, verlor ich ein wenig die Motivation, weiter an meiner Antwort zu arbeiten, da ich davon ausging, dass kaum jemand sie weiter betrachten würde - und sie ist so viel länger als die aller anderen.
Martineau
1
@martineau: "akzeptierte" Antworten sind nicht unbedingt "akzeptabel". Ich lese im Allgemeinen alle Antworten. Einschließlich Ihrer Revision. Was jetzt 3 Tests in dem seltenen Fall von ==statt 2 macht - Ihr elifZustand wird immer wahr sein.
John Machin
@ John Machin: Ich habe mich wirklich inspirieren lassen und es noch weiter überarbeitet. Jetzt sind es nur noch minimale zusätzliche Tests und ein paar andere Verbesserungen. Vielen Dank für Ihre Kommentare und konstruktive Kritik. Ich habe das immer Wahre elifselbst gefangen , FWIW. ;-)
Martineau
@ John Machin: Hmmm, Ihre Timing-Ergebnisse scheinen meinen eigenen zu widersprechen, daher werde ich das, was ich in meiner Antwort zum Timing gesagt habe, entfernen, damit ich untersuchen kann, was weiter vor sich geht. Danke für die Warnung. Eigentlich denke ich, dass ein "echter" Timing-Test zufällige Listenwerte verwenden müsste.
Martineau
10

Ich habe mir Folgendes ausgedacht und es funktioniert, wie Sie sehen können max, minund andere Funktionen über Listen wie diese:

Betrachten Sie also bitte die nächste Beispielliste, um die Position des Maximums in der Liste herauszufinden a:

>>> a = [3,2,1, 4,5]

Den Generator benutzen enumerate und ein Casting machen

>>> list(enumerate(a))
[(0, 3), (1, 2), (2, 1), (3, 4), (4, 5)]

An dieser Stelle können wir die Position von max mit extrahieren

>>> max(enumerate(a), key=(lambda x: x[1]))
(4, 5)

Das Obige sagt uns, das Maximum ist in Position 4 und sein Wert ist 5.

Wie Sie sehen, können Sie im keyArgument das Maximum für jedes iterierbare Objekt ermitteln, indem Sie ein geeignetes Lambda definieren.

Ich hoffe, dass es dazu beiträgt.

PD: Wie @PaulOyster in einem Kommentar feststellte. Mit Python 3.xdem minund maxerlauben Sie ein neues Schlüsselwort default, das die Auslöseausnahme vermeidet, ValueErrorwenn das Argument eine leere Liste ist.max(enumerate(list), key=(lambda x:x[1]), default = -1)

Jonaprieto
quelle
2
Dies ist eine bessere Lösung, da es sich um einen einzelnen Durchgang handelt. Ein paar Kommentare: 1. Keine Notwendigkeit, die Aufzählung aufzulisten (), 2. Lambda besser in Klammern zu setzen, 3. min () und max () haben jetzt einen Standardparameter (der bei leerer Eingabe zurückgegeben wird), können also verwenden Es (z. B. Standard = -1), um eine ValueError-Ausnahme zu vermeiden, und 4. Bitte wechseln Sie zu max (), da dies die ursprüngliche Frage war.
Paul Oyster
ca. 3 Artikel, ja, es funktioniert nur mit Python 3.x. Ich werde das erwähnen. Und alles andere behoben. ;)
Jonaprieto
2
Dies würde die Position eines der Elemente mit dem höchsten Wert (das erste) nur finden, wenn es mehr als einmal in der Liste vorkommt - beantwortet also nicht die gestellte Frage.
Martineau
8

Ich kann die von @martineau zitierte Leistung von @ SilentGhost nicht reproduzieren. Hier ist meine Anstrengung mit Vergleichen:

=== maxelements.py ===

a = [32, 37, 28, 30, 37, 25, 27, 24, 35, 55, 23, 31, 55, 21, 40, 18, 50,
             35, 41, 49, 37, 19, 40, 41, 31]
b = range(10000)
c = range(10000 - 1, -1, -1)
d = b + c

def maxelements_s(seq): # @SilentGhost
    ''' Return list of position(s) of largest element '''
    m = max(seq)
    return [i for i, j in enumerate(seq) if j == m]

def maxelements_m(seq): # @martineau
    ''' Return list of position(s) of largest element '''
    max_indices = []
    if len(seq):
        max_val = seq[0]
        for i, val in ((i, val) for i, val in enumerate(seq) if val >= max_val):
            if val == max_val:
                max_indices.append(i)
            else:
                max_val = val
                max_indices = [i]
    return max_indices

def maxelements_j(seq): # @John Machin
    ''' Return list of position(s) of largest element '''
    if not seq: return []
    max_val = seq[0] if seq[0] >= seq[-1] else seq[-1]
    max_indices = []
    for i, val in enumerate(seq):
        if val < max_val: continue
        if val == max_val:
            max_indices.append(i)
        else:
            max_val = val
            max_indices = [i]
    return max_indices

Ergebnisse eines verprügelten alten Laptops mit Python 2.7 unter Windows XP SP3:

>\python27\python -mtimeit -s"import maxelements as me" "me.maxelements_s(me.a)"
100000 loops, best of 3: 6.88 usec per loop

>\python27\python -mtimeit -s"import maxelements as me" "me.maxelements_m(me.a)"
100000 loops, best of 3: 11.1 usec per loop

>\python27\python -mtimeit -s"import maxelements as me" "me.maxelements_j(me.a)"
100000 loops, best of 3: 8.51 usec per loop

>\python27\python -mtimeit -s"import maxelements as me;a100=me.a*100" "me.maxelements_s(a100)"
1000 loops, best of 3: 535 usec per loop

>\python27\python -mtimeit -s"import maxelements as me;a100=me.a*100" "me.maxelements_m(a100)"
1000 loops, best of 3: 558 usec per loop

>\python27\python -mtimeit -s"import maxelements as me;a100=me.a*100" "me.maxelements_j(a100)"
1000 loops, best of 3: 489 usec per loop
John Machin
quelle
7
a = [32, 37, 28, 30, 37, 25, 27, 24, 35, 
         55, 23, 31, 55, 21, 40, 18, 50,
         35, 41, 49, 37, 19, 40, 41, 31]

import pandas as pd

pd.Series(a).idxmax()

9

So mache ich es normalerweise.

Arijit Laha
quelle
6

Sie können auch das numpy-Paket verwenden:

import numpy as np
A = np.array(a)
maximum_indices = np.where(A==max(a))

Dies gibt ein numpy-Array aller Indizes zurück, die den Maximalwert enthalten

Wenn Sie dies in eine Liste umwandeln möchten:

maximum_indices_list = maximum_indices.tolist()
user3569257
quelle
5
>>> max(enumerate([1,2,3,32,1,5,7,9]),key=lambda x: x[1])
>>> (3, 32)
Hari Roshan
quelle
Das ist falsch. Versuchen Sie, die maximale Anzahl in die Mitte der Liste zu setzen.
Goncalopp
1
Das ist falsch. Die Frage lautet "Finde alle Positionen des Maximalwerts".
Kapil
5

Auch eine Lösung, die nur das erste Erscheinungsbild ergibt , kann erreicht werden durch numpy:

>>> import numpy as np
>>> a_np = np.array(a)
>>> np.argmax(a_np)
9
Grün
quelle
3

@shash hat dies an anderer Stelle beantwortet

Ein pythonischer Weg, um den Index des maximalen Listenelements zu finden, wäre

position = max(enumerate(a), key=lambda x: x[1])[0]

Welches macht man vorbei . Es ist jedoch langsamer als die Lösung von @Silent_Ghost und vor allem von @nmichaels:

for i in s m j n; do echo $i;  python -mtimeit -s"import maxelements as me" "me.maxelements_${i}(me.a)"; done
s
100000 loops, best of 3: 3.13 usec per loop
m
100000 loops, best of 3: 4.99 usec per loop
j
100000 loops, best of 3: 3.71 usec per loop
n
1000000 loops, best of 3: 1.31 usec per loop
serv-inc
quelle
2

Hier ist der Maximalwert und die Indizes, unter denen er angezeigt wird:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> a = [32, 37, 28, 30, 37, 25, 27, 24, 35, 55, 23, 31, 55, 21, 40, 18, 50, 35, 41, 49, 37, 19, 40, 41, 31]
>>> for i, x in enumerate(a):
...     d[x].append(i)
... 
>>> k = max(d.keys())
>>> print k, d[k]
55 [9, 12]

Später: zur Zufriedenheit von @SilentGhost

>>> from itertools import takewhile
>>> import heapq
>>> 
>>> def popper(heap):
...     while heap:
...         yield heapq.heappop(heap)
... 
>>> a = [32, 37, 28, 30, 37, 25, 27, 24, 35, 55, 23, 31, 55, 21, 40, 18, 50, 35, 41, 49, 37, 19, 40, 41, 31]
>>> h = [(-x, i) for i, x in enumerate(a)]
>>> heapq.heapify(h)
>>> 
>>> largest = heapq.heappop(h)
>>> indexes = [largest[1]] + [x[1] for x in takewhile(lambda large: large[0] == largest[0], popper(h))]
>>> print -largest[0], indexes
55 [9, 12]
hughdbrown
quelle
Sie wissen, wie ineffizient das ist?
SilentGhost
1
Rationalisierungen: (1) "Vorzeitige Optimierung ist die ... usw." (2) Es spielt wahrscheinlich keine Rolle. (3) Es ist immer noch eine gute Lösung. Vielleicht werde ich es neu codieren, um es zu verwenden heapq- das Maximum dort zu finden, wäre trivial.
Hughdbrown
Ich würde gerne Ihre heapqLösung sehen, aber ich bezweifle, dass sie funktionieren würde.
SilentGhost
2

Ähnliche Idee mit einem Listenverständnis, aber ohne Aufzählung

m = max(a)
[i for i in range(len(a)) if a[i] == m]
Salvador Dali
quelle
Ich bin nicht der Downvoter, aber beachten Sie, dass dies nicht wirklich gut aussieht und nicht gut funktioniert: Das Durchlaufen der Indizes anstelle der Liste ist in Python sehr umständlich. Sie versuchen, dies zu vermeiden. Außerdem ist es aufgrund des a[i]Aufrufs sicherlich langsamer als die Lösung mit Aufzählung .
Yo '
1

Nur eine Zeile:

idx = max(range(len(a)), key = lambda i: a[i])
Divkakwani
quelle
Schön, aber es werden nicht ALLE Indizes zurückgegeben, nur der erste.
iggy
1

Wenn Sie die Indizes der größten nZahlen in einer Liste mit dem Namen erhalten möchten data, können Sie Pandas verwenden sort_values:

pd.Series(data).sort_values(ascending=False).index[0:n]
dannyg
quelle
0
import operator

def max_positions(iterable, key=None, reverse=False):
  if key is None:
    def key(x):
      return x
  if reverse:
    better = operator.lt
  else:
    better = operator.gt

  it = enumerate(iterable)
  for pos, item in it:
    break
  else:
    raise ValueError("max_positions: empty iterable")
    # note this is the same exception type raised by max([])
  cur_max = key(item)
  cur_pos = [pos]

  for pos, item in it:
    k = key(item)
    if better(k, cur_max):
      cur_max = k
      cur_pos = [pos]
    elif k == cur_max:
      cur_pos.append(pos)

  return cur_max, cur_pos

def min_positions(iterable, key=None, reverse=False):
  return max_positions(iterable, key, not reverse)

>>> L = range(10) * 2
>>> L
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> max_positions(L)
(9, [9, 19])
>>> min_positions(L)
(0, [0, 10])
>>> max_positions(L, key=lambda x: x // 2, reverse=True)
(0, [0, 1, 10, 11])

quelle
0

Dieser Code ist nicht so ausgefeilt wie die zuvor veröffentlichten Antworten, funktioniert aber:

m = max(a)
n = 0    # frequency of max (a)
for number in a :
    if number == m :
        n = n + 1
ilist = [None] * n  # a list containing index values of maximum number in list a.
ilistindex = 0
aindex = 0  # required index value.    
for number in a :
    if number == m :
        ilist[ilistindex] = aindex
        ilistindex = ilistindex + 1
    aindex = aindex + 1

print ilist

Die Liste im obigen Code würde alle Positionen der maximalen Anzahl in der Liste enthalten.

Sukrit Gupta
quelle
0

Sie können dies auf verschiedene Arten tun.

Der alte konventionelle Weg ist,

maxIndexList = list() #this list will store indices of maximum values
maximumValue = max(a) #get maximum value of the list
length = len(a)       #calculate length of the array

for i in range(length): #loop through 0 to length-1 (because, 0 based indexing)
    if a[i]==maximumValue: #if any value of list a is equal to maximum value then store its index to maxIndexList
        maxIndexList.append(i)

print(maxIndexList) #finally print the list

Eine andere Möglichkeit, ohne die Länge der Liste zu berechnen und den Maximalwert für eine Variable zu speichern,

maxIndexList = list()
index = 0 #variable to store index
for i in a: #iterate through the list (actually iterating through the value of list, not index )
    if i==max(a): #max(a) returns a maximum value of list.
        maxIndexList.append(index) #store the index of maximum value
index = index+1 #increment the index

print(maxIndexList)

Wir können es auf pythonische und kluge Weise tun! Verwenden des Listenverständnisses nur in einer Zeile,

maxIndexList = [i for i,j in enumerate(a) if j==max(a)] #here,i=index and j = value of that index

Alle meine Codes sind in Python 3.

Taohidul Islam
quelle