Comment obtenir tous les éléments minimum en fonction de son premier élément de la liste de l'intérieur dans une liste imbriquée?

Question

En termes simples! il y a cette liste LST = [[12,1],[23,2],[16,3],[12,4],[14,5]] de dire et je veux obtenir tous les éléments minimaux de cette liste en fonction de son premier élément de la liste de l'intérieur. Donc, pour l'exemple ci-dessus, la réponse serait [12,1] et [12,4]. Est-il un moyen typique en python de le faire? En vous remerciant à l'avance.

Answer 1

Une solution simple passe compacte nécessite le tri de la liste - qui est techniquement O(N log N) pour une liste de N long, mais le genre de Python est si bon, et tant de séquences « juste arriver » d'avoir un peu d'ordre noyés dans la masse (qui timsort exploite intelligemment pour aller plus vite), que les solutions à base de tri-ont parfois étonnamment bonne performance dans le monde réel.

Voici une solution nécessitant 2,6 ou mieux:

import itertools
import operator
f = operator.itemgetter(0)

def minima(lol):
  return list(next(itertools.groupby(sorted(lol, key=f), key=f))[1])

Pour comprendre cette approche, la recherche « de l'intérieur, vers l'extérieur » aide.

f, à savoir, operator.itemgetter(0), est une fonction clé qui choisit le premier point de son argument à des fins de commande -. Le but même de operator.itemgetter est facilement et construire ces fonctions de manière compacte

sorted(lol, key=f) retourne donc une copie de la liste triée-de-listes lol, commandé en augmentant premier élément. Si vous omettez le key=f la copie sera triée ordonné lexicographique, est aussi en ordre croissant premier élément, mais qui agit seulement comme la « clé primaire » - éléments avec le même premier sous -article à son tour, sont triés par ordre parmi eux par les valeurs de leur deuxième sous-éléments, et ainsi de suite - alors que avec l'key=f vous êtes assuré de préserver l'ordre d'origine parmi les articles avec le même premier sous-point. Vous ne spécifiez pas quel comportement vous avez besoin (et dans votre exemple, les deux comportements arrive à produire le même résultat, donc nous ne pouvons distinguer de cet exemple) qui est la raison pour laquelle je détaille soigneusement les possibilités pour que vous puissiez choisir.

itertools.groupby(sorted(lol, key=f), key=f) effectue le « groupement » tâche qui est au cœur de l'opération: il donne groupes de la séquence (dans ce cas, la séquence sorted fournit) sur la base des critères de classement de key. Autrement dit, un groupe avec tous les éléments adjacents produisant la même valeur entre eux lorsque vous appelez f avec l'élément comme argument, puis un groupe avec tout élément adjacent produisant une valeur différente du premier groupe (mais même entre eux), etc. suite. groupby respecter l'ordre de la séquence prend comme argument, ce qui est la raison pour laquelle nous avons dû trier les lol premier (et ce comportement de groupby rend très utile dans de nombreux cas où l'ordre de la séquence ne soit).

Chaque résultat yielded par groupby est une paire k, g: un k de clé qui est le résultat de f(i) sur chaque élément dans le groupe, un g itérateur qui donne chaque élément dans le groupe en séquence.

Le next intégré (le seul bit dans cette solution qui nécessite Python 2.6) donne un itérateur produit son prochain point - en particulier, le premier élément lorsqu'il est appelé sur une nouvelle, nouvellement iterator fait (et, chaque générateur de Bien sûr un itérateur, comme résultat de groupby). Dans les versions antérieures Python, il devrait être groupby(...).next() (puisque next était seulement une méthode de itérateurs, pas intégré), qui est dépréciée depuis 2.6.

Ainsi, le résumé, le résultat de notre next(...) est exactement la paire k, g où k est le minimum (c.-à-première après le tri) valeur pour le premier sous-élément et g est un itérateur pour les éléments du groupe.

Alors, avec ce que nous [1] simplement choisir le iterator, nous avons donc un itérateur qui donne seulement les sous-éléments que nous voulons.

Puisque nous voulons une liste, pas un iterator (selon vos spécifications), l'appel list(...) externe vient compléter le travail.

est tout cela en vaut la peine, sage-performance? Pas sur la liste de petit exemple que vous donnez - minima est en fait plus lent que le code dans la réponse de @ Kenny (dont la première, la solution « deux passes » est plus rapide). Je just pense qu'il convient de garder les idées à l'esprit pour le suivant problème de traitement de séquence que vous pouvez rencontrer, où les détails des entrées typiques peuvent être très différentes (des listes plus longues, plus rare minima, d'ordre partiel dans l'entrée, etc. , etc., -).

Answer 2

Deux passe:

minval = min(LST)[0]
return [x for x in LST if x[0] == minval]

Une passe:

def all_minima(iterable, key=None):
  if key is None: key = id
  hasminvalue = False
  minvalue = None
  minlist = []
  for entry in iterable:
     value = key(entry)
     if not hasminvalue or value < minvalue:
        minvalue = value
        hasminvalue = True
        minlist = [entry]
     elif value == minvalue:
        minlist.append(entry)
  return minlist

from operator import itemgetter
return all_minima(LST, key=itemgetter(0))

Answer 3

m = min(LST, key=operator.itemgetter(0))[0]
print [x for x in LST if x[0] == m]

Answer 4

minval = min(x[0] for x in LST)
result = [x for x in LST if x[0]==minval]