[解決済み】リストの中で最も一般的な要素を見つけよう

質問

Pythonのリストで最も一般的な要素を見つけるための効率的な方法は何ですか？

リストの項目はハッシュ化できないので、辞書は使えません。 また、ドローの場合は、最も低いインデックスを持つアイテムが返される必要があります。例

>>> most_common(['duck', 'duck', 'goose'])
'duck'
>>> most_common(['goose', 'duck', 'duck', 'goose'])
'goose'

解決方法は？

これだけ多くの解決策が提案されているのに、（ハッシュ化できないが比較可能な要素について）私が明白だと考えているものが誰も提案していないのは驚きです -- [ ]です。 itertools.groupby ][1]. itertools は、高速で再利用可能な機能を提供し、トリッキーなロジックを十分にテストされた標準ライブラリコンポーネントに委譲することができます。 たとえば、次のように考えてみましょう。

import itertools
import operator

def most_common(L):
  # get an iterable of (item, iterable) pairs
  SL = sorted((x, i) for i, x in enumerate(L))
  # print 'SL:', SL
  groups = itertools.groupby(SL, key=operator.itemgetter(0))
  # auxiliary function to get "quality" for an item
  def _auxfun(g):
    item, iterable = g
    count = 0
    min_index = len(L)
    for _, where in iterable:
      count += 1
      min_index = min(min_index, where)
    # print 'item %r, count %r, minind %r' % (item, count, min_index)
    return count, -min_index
  # pick the highest-count/earliest item
  return max(groups, key=_auxfun)[0]

もちろん、もっと簡潔に書くこともできるのですが、最大限わかりやすくすることを目指しています。 2つの print 文は、コメントアウトしないことで、機械の動作をよりよく見ることができます。 と は、コメントアウトされていない状態で印刷されます。

print most_common(['goose', 'duck', 'duck', 'goose'])

を出します。

SL: [('duck', 1), ('duck', 2), ('goose', 0), ('goose', 3)]
item 'duck', count 2, minind 1
item 'goose', count 2, minind 0
goose

ご覧の通りです。 SL はペアのリストで、各ペアは項目の後に元のリストでの項目のインデックスが続きます（quot;most common" と同じ最高カウントの項目が > 1 であれば、結果は最も早く発生したものでなければならないというキー条件を実装するためです）。

groupby は項目のみでグループ化されます (via operator.itemgetter ). 補助関数は、グループ化ごとに max を受け取り、内部的に解凍します。 (item, iterable) ここで、反復可能の項目も2項目タプルである。 (item, original index) [の項目は SL ]].

次に、補助関数はループを使って、グループのイテレート可能なエントリーのカウントの両方を決定します。 と 元のインデックスの最小値を返し、それらを組み合わせた "品質キー" として返します。 max 操作は、元のリストでより早く発生した項目を "better" と見なすようになる。

を心配すれば、このコードはもっとシンプルになるはずです。 少し 時間的、空間的に大きなOの問題、例えば......を少なくする。

def most_common(L):
  groups = itertools.groupby(sorted(L))
  def _auxfun((item, iterable)):
    return len(list(iterable)), -L.index(item)
  return max(groups, key=_auxfun)[0]

しかし、残念なことに、O(N)の補助空間(グループの反復記号をリストに変換するため)とO(Nの2乗)の時間がかかります。 L.index を使用します。） プログラミングにおいて早すぎる最適化は諸悪の根源ですが、O(N log N)のアプローチが可能なのにわざわざO(N乗)のアプローチを選ぶのはスケーラビリティに反し過ぎます！-)

最後に、わかりやすさとパフォーマンスよりも、oneliner"を好む人のために、名前を適当につぶした1-linerバージョンもおまけで用意しました:-).

from itertools import groupby as g
def most_common_oneliner(L):
  return max(g(sorted(L)), key=lambda(x, v):(len(list(v)),-L.index(x)))[0]