LoginSignup
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@everylittle

Pythonでアイテムの個数を数えるのって結局どれが速いのよ（2）

Posted at

前回のおさらい

前回の記事で、Pythonでアイテムの個数を数える方法を2種類（＋α）ご紹介して、どれが速いか調べてみました。
これらの方法はどんな入力にも（入力される値の事前情報を仮定せずに）使えるものですが、記事にコメントをいただいたように、どんな値が来るか分かっていて、しかもその値の種類が少ないときには、もっと速くカウントすることができます。
前回、入力の題材にしていた

seq = 'ACAGCATGCA' * 10000000

は、取り得る値（文字）がA, C, G, Tの4種類しかありませんので、

  • Aの個数を数える
  • Cの個数を数える
  • Gの個数を数える
  • Tの個数を数える

という処理を行うだけでよく、Counter, defaultdictと比較して高速に動作します。そういう意味だと、実はCounter, defaultdictの比較記事としてはよくない入力例だったのかもしれません。

「少ない」って何種類まで？

それでは、具体的に値が何種類までだったら速くできるのでしょうか？
数十個までなのか、数百個までなのか、それとも数千個までなのか、くらいの見当はつけたいですね。

測定環境

前回と同じです。

  • Cygwin (Windows 10)
  • Python 2.7.14 / 3.6.4
  • CPU: Intel Core i7-7500U

リストが入力される場合

counter_list.py
import collections
import timeit

def count_counter(iterable):
    counter = collections.Counter(iterable)
    return dict(counter)

def count_defaultdict(iterable):
    counter = collections.defaultdict(int)
    for x in iterable:
        counter[x] += 1
    return dict(counter)

def count_seqcount(seq, setvalues):
    counter = dict((x, seq.count(x)) for x in setvalues)
    return counter

if __name__ == '__main__':
    for num_uniqvalues in (2**i for i in range(8)):
        seq = list(range(num_uniqvalues)) * (10000000 // num_uniqvalues)
        uniqvalues = set(seq)
        print("# unique values:", num_uniqvalues)
        print(timeit.timeit("count_counter(seq)", setup='from __main__ import count_counter, seq', number=1))
        print(timeit.timeit("count_defaultdict(seq)", setup='from __main__ import count_defaultdict, seq', number=1))
        print(timeit.timeit("count_seqcount(seq, uniqvalues)", setup='from __main__ import count_seqcount, seq, uniqvalues', number=1))

まずは、入力列を数値のリストとして、

の3種類を試しました。
入力列の長さは同じにしておいて、その中で取り得る値の種類を増やしていきます。上のコードでは

  • 0だけからなる長さ10,000,000の列
  • 0, 1が5,000,000個ずつある長さ10,000,000の列
  • 0, 1, 2, 3が2,500,000個ずつある長さ10,000,000の列
  • 0～7の整数が1,250,000個ずつある長さ10,000,000の列
  • （以下略）

というように入力列を変えていきます。
簡単のため、上のようにそれぞれの値が均等に出現するケースで考えることにしました。

（今回の場合に限っていえば、0始まりの連番を数えるタスクなので、カウンタ変数をlistベースにすればdefaultdictより速くできると思いますが。）

Python 2.7の場合

処理時間が3つ並んでいる箇所は、上から順番にCounter, defaultdict, Sequence.countのものです。

terminal
$ python2.7 counter_list.py
('# unique values:', 1)
2.5760269165
0.542164087296
0.0341150760651
('# unique values:', 2)
2.54313802719
0.530303955078
0.121192932129
('# unique values:', 4)
2.53363919258
0.527471065521
0.284231901169
('# unique values:', 8)
2.52918481827
0.528441905975
0.73012304306
('# unique values:', 16)
2.51960992813
0.52666592598
1.39528107643
('# unique values:', 32)
2.57073092461
0.527655124664
2.73206114769
('# unique values:', 64)
2.53179192543
0.527481079102
5.43943691254
('# unique values:', 128)
2.55097103119
0.527207136154
10.7969200611

Counterとdefaultdictは取り得る値の種類が多くなってもほぼ処理時間が変わりませんが、Sequence.countの場合は取り得る値の種類に比例して処理時間が長くなります。Sequence.countの呼び出し回数が倍々に増えているわけですから、当然処理時間も倍々に増えていくわけですね。
値の種類が8個になった時点で、Sequence.countはdefaultdictより時間が掛かるようになりました。Sequence.countの恩恵を受けられるのは、せいぜい6種類くらいまでの場合に限られるでしょうか。

Python 3.6の場合

terminal
$ python3.6 counter_list.py
# unique values: 1
0.41325897397473454
0.695587629918009
0.02663882402703166
# unique values: 2
0.4152745339088142
0.7006769538857043
0.14070909889414907
# unique values: 4
0.4618919459171593
0.7234666077420115
0.3422027160413563
# unique values: 8
0.4247186812572181
0.6958386925980449
0.8311411123722792
# unique values: 16
0.4215944930911064
0.6860581482760608
1.7771289623342454
# unique values: 32
0.41267539095133543
0.6848959219641984
3.570915916003287
# unique values: 64
0.41819067765027285
0.6896195830777287
7.129963087849319
# unique values: 128
0.4306373633444309
0.7228756221011281
14.110849821940064

defaultdictとCounterの順序がPython 2.7とは逆転していますが（前回の記事参照）、Python 2.7と同様に、8種類になるとSequence.countは最速ではなくなります。
Counterの処理がPython 2.7より速くなっているために、4種類の時点で既にかなり差が詰まっています。

文字列が入力される場合

前回のA, C, G, Tの例は文字列だったので、こちらのケースに該当します。

counter_string.py
import collections
import timeit

def count_counter(iterable):
    counter = collections.Counter(iterable)
    return dict(counter)

def count_defaultdict(iterable):
    counter = collections.defaultdict(int)
    for x in iterable:
        counter[x] += 1
    return dict(counter)

def count_seqcount(seq, setvalues):
    counter = dict((x, seq.count(x)) for x in setvalues)
    return counter

if __name__ == '__main__':
    for num_uniqvalues in (2**i for i in range(8)):
        seq = "".join(chr(x) for x in range(num_uniqvalues)) * (10000000 // num_uniqvalues)
        uniqvalues = set(seq)
        print("# unique values:", num_uniqvalues)
        print(timeit.timeit("count_counter(seq)", setup='from __main__ import count_counter, seq', number=1))
        print(timeit.timeit("count_defaultdict(seq)", setup='from __main__ import count_defaultdict, seq', number=1))
        print(timeit.timeit("count_seqcount(seq, uniqvalues)", setup='from __main__ import count_seqcount, seq, uniqvalues', number=1))

リストのときと比較して、seqの作り方が違うだけです。今回、seqは文字列です。

の3種類の比較になっています。

Python 2.7の場合

terminal
$ python2.7 counter_string.py
('# unique values:', 1)
2.64913105965
0.507971048355
0.004310131073
('# unique values:', 2)
2.55145812035
0.507522106171
0.0079140663147
('# unique values:', 4)
2.54508900642
0.505310058594
0.015830039978
('# unique values:', 8)
2.54428601265
0.520057916641
0.0289571285248
('# unique values:', 16)
2.55457091331
0.507193088531
0.0538790225983
('# unique values:', 32)
2.55689311028
0.504297971725
0.100095033646
('# unique values:', 64)
2.60951495171
0.53032207489
0.217819929123
('# unique values:', 128)
2.69009685516
0.531752824783
0.49088716507

str.countはリストより善戦していて、128種類のときにdefaultdictとほぼ同じという感じです。これ以上増やすとdefaultdictの方が速くなりますね。

Python 3.6の場合

terminal
$ python3.6 counter_string.py
# unique values: 1
0.4239531490020454
0.6908756061457098
0.0058090160600841045
# unique values: 2
0.44697694201022387
0.6905332137830555
0.022880982141941786
# unique values: 4
0.5058784820139408
0.7603472019545734
0.02937478106468916
# unique values: 8
0.4713318641297519
0.7984626600518823
0.05456399591639638
# unique values: 16
0.5241422927938402
0.8530813110992312
0.10187289072200656
# unique values: 32
0.4731873348355293
0.750194292049855
0.19266901584342122
# unique values: 64
0.4803232508711517
0.7610510247759521
0.41825661808252335
# unique values: 128
0.5159714459441602
0.812115999404341
0.8506077011115849

こちらだと64種類の時点でCounterとほぼ同等になり、128種類でCounterに（defaultdictにも）逆転されます。

まとめ

  • リストが入力されるときは、値が4種類程度までの場合
  • 文字列が入力されるときは、文字が**128種類（Python 2） / 64種類（Python 3）**程度までの場合

には、リストや文字列のcountメソッドを使うことで、defaultdictやCounterなどの汎用的に使える方法より速くできる可能性があります。
逆に、この範囲に収まらない可能性が高い場合は、素直にdefaultdictやCounterを使っておきましょう。

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?