Trouver l'indice de la valeur min ou max en Python

J'ai une structure de la forme:

>>> items
[([[0, 1], [2, 20]], 'zz', ''), ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]

Le premier élément de chaque n-uplet est une liste de plages, et je veux faire un générateur qui me donne les plages dans l'ordre croissant basé sur l'indice de départ.

Depuis la plage-les listes sont déjà triés en fonction de leur indice de départ de cette opération est simple: c'est juste un classement de fusion. Je suis l'espoir de le faire avec une bonne efficacité de calcul, donc je pense qu'une bonne façon de faire implicitement le suivi de l'état de mon fusion est tout simplement de la pop le front de la liste de tuple qui a le plus petit indice de départ dans sa gamme de la liste.

Je peux utiliser min() pour obtenir [0, 1] qui est le premier que je veux, mais comment puis-je obtenir l'index de celui-ci?

J'ai ceci:

[ min (items[i][0]) for i in range(len(items)) ]

qui me donne le premier élément de chaque liste, que je peux ensuite min() au cours d'une certaine façon, mais il échoue une fois que la liste est vide, et aussi il n'est pas clair comment faire pour obtenir l'index à utiliser pop() avec sans regarder en arrière dans la liste.

Pour résumer: vous Souhaitez construire générateur qui renvoie pour moi:

([0,1], 'zz', '')
([1,3], 'a', 'b')
([2,20], 'zz', '')
([5,29], 'a', 'b')
([50,500], 'a', 'b')

Ou même de manière plus efficace, j'ai seulement besoin de ces données:

[0, 1, 0, 1, 1]

(les indices des tuples, je veux profiter de l'avant de l'élément de l')

J'ai écrit un mergeiter fonction pour une réponse précédente; j'ajoute des indices avec enumerate().
Étant assez vert avec Python, j'ai eu quelques difficultés grokking que mergeiter fonction de la vôtre au premier abord. Mais, après avoir examiné ces autres réponses, de toute évidence, c'est le bon type d'approche. Et pourtant c'est la seule qui n'est pas affiché comme une réponse...

InformationsquelleAutor Steven Lu | 2013-06-05

python

4

Cela fonctionne:
```
by_index = ([sub_index, list_index] for list_index, list_item in
             enumerate(items) for sub_index in list_item[0])
[item[1] for item in sorted(by_index)]
```
Donne:
```
[0, 1, 0, 1, 1]
```
En détail. Le générateur:
```
by_index = ([sub_index, list_index] for list_index, list_item in
             enumerate(items) for sub_index in list_item[0])
list(by_index)    
[[[0, 1], 0], [[2, 20], 0], [[1, 3], 1], [[5, 29], 1], [[50, 500], 1]]
```
Donc, la seule chose nécessaire est de tri et d'obtenir seul le choix de l'indice:
```
[item[1] for item in sorted(by_index)]
```
- Je pense que le tri est totalement inutile ici, même si c'est probablement ne va pas faire le moteur d'exécution d'horribles ou quoi que ce soit. Seulement un min opération est nécessaire
- Python tri est très efficace (en.wikipedia.org/wiki/Timsort). Fusion de tri est également utilisé. Si je vous comprends bien, vous voudriez appliquer min à tous les indices. Prendre la plus petite et la répétition jusqu'à ce que la liste est consommé? Je lance un test quelques qui a indiqué que le tri est plus rapide pour les grandes listes et si les articles sont déjà dans un certain ordre.
- Hm. vous avez peut-être raison. Après tout, plus d'une min de fonctionnement.
- Mise à jour de ma solution après j'ai vu le vôtre et de mieux comprendre ce que vous êtes après. Maintenant, il est à seulement deux lignes. Essayez de temps à l'encontre de votre solution pour les grands ensembles de données.
- Oh j'aime ça! Ce code ressemble à mon intuition est le plus approprié pour l'optimisation par une machine virtuelle. Je ne doute pas qu'il sera plus performant. Merci
- C'est mieux que ma réponse parce qu'il ne souffre pas de min tenter d'index dans les vides des listes. Probablement une amélioration de l'ordre de O(n log n) par rapport à la mienne qui est en O(n^2). Pourrait être améliorée en évitant l'utilisation de enumerate.
InformationsquelleAutor Mike Müller
46
```
 from operator import itemgetter
 index, element = max(enumerate(items), key=itemgetter(1))
```
Retour de l'indice du plus grand élément dans items et l'élément lui-même.
- Grand, supposons que je veux forer vers le bas de certains plus (comme, par exemple, je veux trier par certaines partie de la première indexé), je dois utiliser une lambda pour qui? Et s'il vous plaît envisager de mes "trucs inutiles" comme raison pour laquelle je veux faire tout cela si sacrément compliqué 🙂
- Je vais répondre à ma question dans le dernier commentaire, je pense que la manière de creuser plus profond est avec un lambda.
- max(enumerate(items), key=lambda x: x[1]), pour vous sauver d'une importation.
InformationsquelleAutor MatthieuBizien
31

Cette méthode trouve l'index de l'élément maximum de tout objet iterable et ne nécessite aucune externes importations:
```
def argmax(iterable):
    return max(enumerate(iterable), key=lambda x: x[1])[0]
```
- Seuls les non-solution de boucle qui peuvent vous donner les max et argmax en un seul balayage!
- voici une approche, basée sur l'inversion de la n-uplet lexicographique de commande - max(enumerate(l), key=lambda t: list(reversed(t))). Contrairement à l'original, quand max s'affiche plusieurs fois, ce serait vous donner le dernier indice (qui est le plus utile dans quelques cas)
InformationsquelleAutor 1''
11

De l'index max d'une liste:
```
def argmax(lst):
  return lst.index(max(lst))
```
Si il y a doublon max valeurs lst, ce sera le retour de l'indice de la première valeur maximale trouvée.
- Il permettra également d'effectuer une itération de la liste deux fois, afin de ne pas le faire.
InformationsquelleAutor stupidsven
2

Encore une autre façon d'obtenir le argmax est:
```
def argmax(lst):
    return max(range(len(lst)), key=lst.__getitem__)
```
InformationsquelleAutor yoniLavi
1

c'est donc un réel moyen rapide et facile pour obtenir cette version efficace vous êtes à la recherche pour:
```
a = []
count = 0
for i in items:
    for x in i[0]:
        #place a list with the index next to it in list a for sorting
        a.append((x,count))
#continually grabs the smallest list and returns the index it was in
sort = [a.pop(a.index(min(a)))[1] for i in range(len(a))]
```
Ici en est-il de vos articles pour montrer que cela fonctionne:
```
>>> items = [([[0, 1], [2, 20]], 'zz', ''), ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]
>>> a = []
>>> count = 0
>>> for i in items:
...     for x in i[0]:
...             a.append((x,count))
...     count += 1
... 
>>> sort = [a.pop(a.index(min(a)))[1] for i in range(len(a))]
>>> sort
[0, 1, 0, 1, 1]
```
- j'essayais d'éviter la récidive de recherches qui est ce que a.index(min(a)) n'. l'indice est une recherche...
- Oh, d'accord. Que la compréhension de liste est un moyen rapide de trieuse pour presque n'importe quel tableau! une liste, une liste de listes...il fonctionne en fait sur rien, j'ai juste besoin d'ajouter de la [1]. Bien qu'il est difficile pour envelopper ma tête autour de la façon dont vous prévoyez sur le tri des choses, si vous ne voulez pas de les regarder...
- Et bien oui, il est difficile pour envelopper ma tête autour de lui, c'est pour ça que j'ai posté le problème, il doit bien y avoir un moyen de le faire bien. Pour faire le calcul efficace nous avons juste obtenu le suivi de l'état du chemin que nous avons déplacé vers le bas de chaque sous-tableau. Qui peut être fait par eux sautant je pense, mais je ne sais pas comment mettre tout cela ensemble.
- basé sur votre explication, je pense que mon code lui convient très bien. Parce que ce que mon code n', si vous lisez les commentaires, c'est les pistes de la liste était dans lequel tuple! la raison pour laquelle il est a.index est parce que vous devez le faire afin d'utiliser a.pop. Suis-je malentendu vous?
- Ouais, mais il a besoin d'elle pour savoir qui de n-uplet de points a le moins de valeur que le premier indice de son premier élément (ceux étant les listes de deux). donc, ça peut aller de la pop. Alors, la prochaine fois il va le répéter. Il n'a pas besoin d'appeler index avec les listes-de-deux.
- pop prend un entier (l'index) pour le placement de ce que vous voulez à la pop. Donc, sans l'aide de a.index, vous obtiendrez l'erreur suivante: TypeError: an integer is required
- Bien. Ouais. Je ne pense pas que cela a du sens d'être du bâtiment qui a liste dans l'ordre de la pop des trucs hors de lui. Il n'y a pas de point de trouver le max sur l'ensemble de la série. Il devrait être de trouver le max entre l'élément suivant sur chaque tuple. Voir mon auto-réponse de la direction que je suis à la recherche de prendre en. J'espère que ça le rend plus clair.
InformationsquelleAutor Ryan Saxe

Il est facile si vous n'essayez pas d'utiliser le fait que la plage interne listes sont triées

sorted(sum([ [(rng,) + i[1:] for rng in i[0]] for i in items ], []), lambda i: i[0][0])

Il semble que vous voulez une fonction qui retourne l'indice de la plus petite valeur si

def min_idx(l, key=lambda x: x):
    min_i, min_key = None, float('inf')
    for i, v in enumerate(l):
        key_v = key(v)
        if key_v < min_key:
            mini_i = i
            min_key = key_v
    return min_i

def merge_items(items):
    res = []
    while True:
        i = min_idx(items, key=lambda i: i[0][0][0])
        item = items[i]
        res.append((item[0][0],) + item[1:])
    return res

InformationsquelleAutor Phil Reinhold

Je ne suis pas sûr de ce qui s'est passé mais je pense que tout le monde est un peu hors de la marque. Je vais le blâme sur qui font un mauvais travail en expliquant le problème, je vais essayer de résoudre. De toute façon, voici combien j'ai pris de l':

items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)

Cela me prend la plupart du chemin, mais de ce qu'il reste à traiter est le traitement de la situation où une seule liste a été épuisé. Une fois que c'est pris en charge il doit être facile pour en faire un générateur comme je peux juste le mettre dans une boucle et le rendement à l'intérieur, et aussi, espérons-le, sans trop de travail de plus elle peut être adaptée à l'exécution efficace de tri-fusion sur les générateurs.

>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[0, 1]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[1, 3]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
[2, 20]
>>> items[min(range(len(items)), key = lambda x: items[x][0][0])][0].pop(0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in <lambda>
IndexError: list index out of range

Mise à jour:

Montage du sous-ensemble propre de encore valides-éléments de min est sur le billet.

def next_value_in_sections(sections):                 
    while 1:                                          
        idxs = []                                     
        for i, x in enumerate(sections):              
            if x[0]:                                  
                idxs.append(i)                        
        print idxs                                    
        if not idxs:                                  
            break                                     
        j = min(idxs, key=lambda x: sections[x][0][0])
        yield (sections[j][0].pop(0), j)              

items = [([[0, 1], [2, 20]], 'zz', ''),               
         ([[1, 3], [5, 29], [50, 500]], 'a', 'b')]    
x = next_value_in_sections(items)                     
for i in x:                                           
    print i

Exécutée:

$ python test.py  
[0, 1]
([0, 1], 0)
[0, 1]
([1, 3], 1)
[0, 1]
([2, 20], 0)
[1]
([5, 29], 1)
[1]
([50, 500], 1)
[]

Je vais noter cela peut encore être améliorée, la idxs liste est reconstruit à chaque itération. Il n'a pas besoin d'être, mais cela n'améliore pas la asymptotique lié... bien sûr, on peut se demander si nous nous soucions vraiment de la performance, si l'utilisation de la lambda est une bonne idée, bien que je ne vois vraiment pas un moyen de contourner cela sans prendre part min, qui est simplement une descente dans la folie.

cela peut être un peu d'un épuisant, mais pourquoi ne pas le mettre dans un try et except et alors que vous venez de découvrir dont la liste est vide dans le except et vous avez alors le reste!
Ouais apportant des exceptions pour ce sent trop lourde, étant donné que je suis à même d'éviter le tri et l'assemblage de plus de listes car je considère que ceux-être inutile. Il ne ressemble exceptions peuvent bien evem si j'ai l'intention de garder ce compatible avec les générateurs d'entrée listes. Donc c'est agréable. Je crois que j'ai une solution pour elle si. Modifier la réponse une fois que je l'ai tester

InformationsquelleAutor Steven Lu

Vous devez vous connecter pour publier un commentaire.