3

簡単に言えば！このリストがLST = [[12,1],[23,2],[16,3],[12,4],[14,5]]あり、内部リストの最初の要素に従って、このリストのすべての最小要素を取得したいと思います。したがって、上記の例の場合、答えはとに[12,1]なり[12,4]ます。これを行うPythonの典型的な方法はありますか？よろしくお願いします。

4

4 に答える 4

5

2つのパス：

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

ワンパス：

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))
于 2010-08-21T10:09:04.047 に答える
3

コンパクトなシングルパスソリューションでは、リストを並べ替える必要があります。これは、技術的O(N log N)にはN長いリストの場合ですが、Pythonの並べ替えは非常に優れており、非常に多くのシーケンスに「たまたま」いくつかの順序が埋め込まれています（これはtimsort巧妙に活用して高速化します） 、ソートベースのソリューションは、現実の世界で驚くほど優れたパフォーマンスを発揮することがあります。

2.6以上を必要とするソリューションは次のとおりです。

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

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

このアプローチを理解するには、「内側から外側に向かって」見ることが役立ちます。

fつまり、operator.itemgetter(0)は、順序付けの目的で引数の最初の項目を選択するキー関数です。その目的は、そのoperator.itemgetterような関数を簡単かつコンパクトに構築することです。

sorted(lol, key=f)したがって、リストのリストのソートされたコピーを、lol最初の項目の昇順で返します。ソートされたコピーを省略するとkey=f、辞書式順序になるため、最初のアイテムの昇順にもなりますが、これは「主キー」としてのみ機能します。同じ最初のサブアイテムを持つアイテムは、順番にソートされます。 2番目のサブアイテムの値などによってそれらを指定します。ただし、同じ最初のサブアイテムを持つアイテム間の元の順序を保持することが保証されます。key=f必要な動作を指定しないでください（この例では、2つの動作が同じ結果を生成するため、その例と区別できません）。そのため、両方の可能性を慎重に詳しく説明して、選択できるようにします。

itertools.groupby(sorted(lol, key=f), key=f)操作の中心である「グループ化」タスクを実行します。順序付け基準に基づいて、シーケンス（この場合はシーケンスが提供します）からグループを生成します。つまり、アイテムを引数として呼び出すと、隣接するすべてのアイテムが同じ値を生成するグループ、次に、隣接するすべてのアイテムが最初のグループとは異なる値を生成する（ただし、それらの間で同じ）グループというようになります。 。 引数として取るシーケンスの順序を尊重します。そのため、最初にソートする必要がありました（この動作により、シーケンスの順序が重要になる多くの場合に非常に役立ちます）。sortedkeyfgroupbylolgroupby

yieldによって生成される各結果groupbyはペアです。グループ内の各アイテムの結果でk, gあるキー、グループ内の各アイテムを順番に生成するイテレータです。kf(i)g

イテレータが与えられたnext組み込み（このソリューションでPython 2.6を必要とする唯一のビット）は、次のアイテムを生成します。特に、新しく作成されたイテレータで呼び出されたときの最初のアイテムです（もちろん、すべてのジェネレータはイテレータです）。 、groupbyの結果と同様）。以前のPythonバージョンでは、groupby(...).next()（next組み込みではなく、イテレータのメソッドにすぎなかったため）必要でしたが、2.6以降は非推奨になっています。

したがって、要約すると、私たちの結果next(...)は正確にペアになりますk, g。ここkで、は最初のサブアイテムの最小値（つまり、並べ替え後の最初の値）でありg、グループのアイテムのイテレーターです。

つまり、[1]イテレータだけを選択するので、必要なサブアイテムだけを生成するイテレータがあります。

イテレータではなくリストが必要なので（仕様による）、最も外側のlist(...)呼び出しでジョブが完了します。

これはすべて、パフォーマンスの面で価値がありますか？あなたが与える小さな例のリストにはありません-minima実際には@Kennyの答えのどちらのコードよりも遅いです（最初の「2パス」ソリューションはより高速です）。典型的な入力の詳細がまったく異なる可能性がある次のシーケンス処理の問題（長いリスト、まれな最小値、入力の半順序、＆c、＆c;-)のアイデアを覚えておく価値があると思います。

于 2010-08-21T15:59:20.163 に答える
2 
m = min(LST, key=operator.itemgetter(0))[0]
print [x for x in LST if x[0] == m]
于 2010-08-21T10:02:15.890 に答える
-1 
minval = min(x[0] for x in LST)
result = [x for x in LST if x[0]==minval]
于 2010-08-21T10:06:56.297 に答える