67

Pythonでは、リストがあります：

L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]

発生回数が最も多い項目を特定したい。私はそれを解決することができますが、そうするための最速の方法が必要です。これには素晴らしいPythonicの答えがあることを私は知っています。

4

14 に答える 14

166

max()キーを使用した最も簡単な解決策について誰も言及していないことに驚いていますlist.count。

max(lst,key=lst.count)

例：

>>> lst = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
>>> max(lst,key=lst.count)
4

これは Python 3 または 2 で機能しますが、最も頻度の高い項目のみを返し、頻度も返さないことに注意してください。また、引き分けの場合(つまり、共同で最も頻繁に使用されるアイテム)、単一のアイテムのみが返されます。

使用の時間の複雑さはPM 2Ringコメントとしてmax()使用するよりも悪いですが、アプローチは迅速な実装の恩恵を受けており、このアプローチは短いリストでは最速ですが、大きなリストでは遅いことがわかります (IPython 5.3 に示されている Python 3.6 のタイミング):Counter.most_common(1)C

In [1]: from collections import Counter
   ...: 
   ...: def f1(lst):
   ...:     return max(lst, key = lst.count)
   ...: 
   ...: def f2(lst):
   ...:     return Counter(lst).most_common(1)
   ...: 
   ...: lst0 = [1,2,3,4,3]
   ...: lst1 = lst0[:] * 100
   ...: 

In [2]: %timeit -n 10 f1(lst0)
10 loops, best of 3: 3.32 us per loop

In [3]: %timeit -n 10 f2(lst0)
10 loops, best of 3: 26 us per loop

In [4]: %timeit -n 10 f1(lst1)
10 loops, best of 3: 4.04 ms per loop

In [5]: %timeit -n 10 f2(lst1)
10 loops, best of 3: 75.6 us per loop
于 2016-11-24T11:41:20.827 に答える
126 
from collections import Counter
most_common,num_most_common = Counter(L).most_common(1)[0] # 4, 6 times

古いバージョンのPython（<2.7）の場合、このレシピCounterを使用してクラスを作成できます。

于 2011-08-08T19:16:58.017 に答える
33

あなたの質問では、それを行うための最速の方法を尋ねました。特に Python で繰り返し実証されているように、直感は信頼できるガイドではありません。測定する必要があります。

以下は、いくつかの異なる実装の簡単なテストです。

import sys
from collections import Counter, defaultdict
from itertools import groupby
from operator import itemgetter
from timeit import timeit

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]

def max_occurrences_1a(seq=L):
    "dict iteritems"
    c = dict()
    for item in seq:
        c[item] = c.get(item, 0) + 1
    return max(c.iteritems(), key=itemgetter(1))

def max_occurrences_1b(seq=L):
    "dict items"
    c = dict()
    for item in seq:
        c[item] = c.get(item, 0) + 1
    return max(c.items(), key=itemgetter(1))

def max_occurrences_2(seq=L):
    "defaultdict iteritems"
    c = defaultdict(int)
    for item in seq:
        c[item] += 1
    return max(c.iteritems(), key=itemgetter(1))

def max_occurrences_3a(seq=L):
    "sort groupby generator expression"
    return max(((k, sum(1 for i in g)) for k, g in groupby(sorted(seq))), key=itemgetter(1))

def max_occurrences_3b(seq=L):
    "sort groupby list comprehension"
    return max([(k, sum(1 for i in g)) for k, g in groupby(sorted(seq))], key=itemgetter(1))

def max_occurrences_4(seq=L):
    "counter"
    return Counter(L).most_common(1)[0]

versions = [max_occurrences_1a, max_occurrences_1b, max_occurrences_2, max_occurrences_3a, max_occurrences_3b, max_occurrences_4]

print sys.version, "\n"

for vers in versions:
    print vers.__doc__, vers(), timeit(vers, number=20000)

私のマシンでの結果：

2.7.2 (v2.7.2:8527427914a2, Jun 11 2011, 15:22:34) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] 

dict iteritems (4, 6) 0.202214956284
dict items (4, 6) 0.208412885666
defaultdict iteritems (4, 6) 0.221301078796
sort groupby generator expression (4, 6) 0.383440971375
sort groupby list comprehension (4, 6) 0.402786016464
counter (4, 6) 0.564319133759

したがって、Counterソリューションは最速ではないようです。そして、この場合、少なくとも、groupbyより高速です。defaultdict良いですが、その利便性のために少しお金を払います。dictと一緒に通常のを使用する方がわずかに高速getです。

リストがはるかに大きい場合はどうなりますか? 上記のテストに追加L *= 10000して、繰り返し回数を 200 に減らします。

dict iteritems (4, 60000) 10.3451900482
dict items (4, 60000) 10.2988479137
defaultdict iteritems (4, 60000) 5.52838587761
sort groupby generator expression (4, 60000) 11.9538850784
sort groupby list comprehension (4, 60000) 12.1327362061
counter (4, 60000) 14.7495789528

これdefaultdictで明らかに勝者です。したがって、おそらく「get」メソッドのコストと inplace add の損失が加算されます (生成されたコードの調査は演習として残します)。

しかし、変更されたテスト データでは、一意のアイテム値の数はおそらくそれほど変化せずdict、defaultdict他の実装よりも有利です。では、より大きなリストを使用して、一意の項目の数を大幅に増やしたらどうなるでしょうか? L の初期化を次のように置き換えます。

LL = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
L = []
for i in xrange(1,10001):
    L.extend(l * i for l in LL)

dict iteritems (2520, 13) 17.9935798645
dict items (2520, 13) 21.8974409103
defaultdict iteritems (2520, 13) 16.8289561272
sort groupby generator expression (2520, 13) 33.853593111
sort groupby list comprehension (2520, 13) 36.1303369999
counter (2520, 13) 22.626899004

そのため、現在Counterはソリューションよりも明らかに高速ですが、およびのバージョンgroupbyよりはまだ遅いです。iteritemsdictdefaultdict

これらの例のポイントは、最適なソリューションを生成することではありません。要点は、多くの場合、最適な一般解が1 つ存在しないということです。さらに、パフォーマンス基準は他にもあります。メモリ要件はソリューション間で大幅に異なり、入力のサイズが大きくなるにつれて、メモリ要件がアルゴリズム選択の最重要要因になる可能性があります。

結論: それはすべて依存しており、測定する必要があります。

于 2011-08-08T21:41:41.070 に答える
17

Pythonバージョン2.5以降で動作するdefaultdictソリューションは次のとおりです。

from collections import defaultdict

L = [1,2,45,55,5,4,4,4,4,4,4,5456,56,6,7,67]
d = defaultdict(int)
for i in L:
    d[i] += 1
result = max(d.iteritems(), key=lambda x: x[1])
print result
# (4, 6)
# The number 4 occurs 6 times

L = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 7, 7, 7, 7, 7, 56, 6, 7, 67] その場合、6つの4と6つの7があることに注意してください。ただし、結果は(4, 6) 6つの4になります。

于 2011-08-08T19:20:41.533 に答える
2

おそらくmost_common（）メソッド

于 2011-08-08T19:20:15.990 に答える
1

Python 3.5.2 を使用して、この関数を使用してgroupbyfromモジュールで最良の結果を得ました。itertools

from itertools import groupby

a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]

def occurrence():
    occurrence, num_times = 0, 0
    for key, values in groupby(a, lambda x : x):
        val = len(list(values))
        if val >= occurrence:
            occurrence, num_times =  key, val
    return occurrence, num_times

occurrence, num_times = occurrence()
print("%d occurred %d times which is the highest number of times" % (occurrence, num_times))

出力：

4 occurred 6 times which is the highest number of times

timeitfromtimeitモジュールでテストします。

このスクリプトを次のテストに使用しましたnumber= 20000。

from itertools import groupby

def occurrence():
    a = [1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
    occurrence, num_times = 0, 0
    for key, values in groupby(a, lambda x : x):
        val = len(list(values))
        if val >= occurrence:
            occurrence, num_times =  key, val
    return occurrence, num_times

if __name__ == '__main__':
    from timeit import timeit
    print(timeit("occurrence()", setup = "from __main__ import occurrence",  number = 20000))

出力 (最高のもの):

0.1893607140000313
于 2016-11-25T21:26:48.823 に答える
1

計算を高速化するためにソリューションで numpy を使用している場合は、これを使用します。

import numpy as np
x = np.array([2,5,77,77,77,77,77,77,77,9,0,3,3,3,3,3])
y = np.bincount(x,minlength = max(x))
y = np.argmax(y)   
print(y)  #outputs 77
于 2021-01-04T14:26:31.950 に答える
0

見栄えがよく、短いリストの場合は高速な別のソリューションを投入したいと思います。

def mc(seq=L):
    "max/count"
    max_element = max(seq, key=seq.count)
    return (max_element, seq.count(max_element))

Ned Deily が提供するコードを使用してこれをベンチマークできます。これにより、最小のテスト ケースでこれらの結果が得られます。

3.5.2 (default, Nov  7 2016, 11:31:36) 
[GCC 6.2.1 20160830] 

dict iteritems (4, 6) 0.2069783889998289
dict items (4, 6) 0.20462976200065896
defaultdict iteritems (4, 6) 0.2095775119996688
sort groupby generator expression (4, 6) 0.4473949929997616
sort groupby list comprehension (4, 6) 0.4367636879997008
counter (4, 6) 0.3618192010007988
max/count (4, 6) 0.20328268999946886

ただし、これは非効率的であり、大きなリストでは非常に遅くなることに注意してください!

于 2016-12-06T22:52:50.453 に答える
0

私の（単純な）コード（Pythonを3か月勉強した）：

def more_frequent_item(lst):
    new_lst = []
    times = 0
    for item in lst:
        count_num = lst.count(item)
        new_lst.append(count_num)
        times = max(new_lst)
    key = max(lst, key=lst.count)
    print("In the list: ")
    print(lst)
    print("The most frequent item is " + str(key) + ". Appears " + str(times) + " times in this list.")


more_frequent_item([1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67])

出力は次のようになります。

In the list: 
[1, 2, 45, 55, 5, 4, 4, 4, 4, 4, 4, 5456, 56, 6, 7, 67]
The most frequent item is 4. Appears 6 times in this list.
于 2019-06-16T22:41:26.253 に答える