Help us understand the problem. What is going on with this article?

【Python】組み合わせ(nCr) 計算の高速化

* 以下の項目における各手法の評価はあくまで個人的なものです。

目次

既存ツールを用いた手法1(評価 ☆)

itertools.combinations()で組み合わせのリスト作ってその大きさを求める。

sample.py
import itertools
a = len(list(itertools.combinations(range(n), r)))

メリット

思いつきません...

デメリット

  • 遅い
  • メモリを圧迫する

既存ツールを用いた手法2(評価 ☆☆)

math.factorial()を使う

sample.py
from math import factorial
a = factorial(n) / factorial(r) / factorial(n - r)

メリット

  • それなりに速い

デメリット

  • nとrの値によってはエラーになる (どこでエラーになるか分かりにくい)
    • n = 200, r <= 51 → エラー
    • n = 200, r > 51 → 成功
    • n = 1000, r <= 896 → エラー
    • n = 1000, r > 896 → 成功

既存ツールを用いた手法3(評価 ☆☆☆)

外部ライブラリ scipy の scipy.misc.comb() を使う。

(2018/08/12 追記)
scipyの仕様が変わって、現在は scipy.special.comb() が推奨されているようです。

sample.py
from scipy.special import comb
# a = comb(n, r)
a = comb(n, r, exact=True)

メリット

  • 速い

デメリット

  • 外部モジュールが使えない環境(競プロなど)では不可
  • 答えが大きすぎる場合には戻り値が "inf" になる

(2019/01/10追記)
引数にexact=Trueを指定することで戻り値が"inf"になるのを回避できるようです。また,デフォルトの状態ではfloat型で近似された値が返されるので,正確な値を求めたい場合にも,この引数が必要になります。(その分若干遅くなります。)

ユーザ定義型1(評価 ☆☆)

辞書と再帰を利用

sample.py
# 再帰制限に引っかかった場合に外す
# import sys
# sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

a = cmb(n,r)

メリット

  • ムダな計算を行わない
  • 計算回数が多い場合に有効

デメリット

  • 一回目の計算が遅い
  • nが大きい場合にはメモリを圧迫する

ユーザ定義型2(評価 ☆☆☆)

operator と functools の関数を利用

sample.py
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

a = cmb(n, r)

メリット

  • 安定した速さ(nの値によって極端に遅くなることはない)

デメリット(?)

  • import文が増える

ユーザ定義型3(評価 ☆☆)

組み合わせの数」 にある方法をPythonで実装

sample.py
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

a = cmb(n,r)

メリット

  • n の値がとても大きい場合に有効

デメリット

  • n の値が小さい場合には遅い
  • コード量が多い

番外編

競技プログラミングでよく目にする「10^9+7で割った余り」を求める場合は以下のようなやり方ができるそうです。

sample.py
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

a = cmb(n,r,mod)

メリット

  • nが大きい場合も高速

デメリット

  • フェルマーの小定理を用いているので,「10^9(素数でない値)で割った余り」とかはできない

計算時間の比較

  • rはnの半分の値に設定
  • 最速値は太字,2位は斜体

10回実行した時

n scipy ユーザ1 ユーザ2 ユーザ3
10 0.000007 0.000023 0.000017 0.000063
100 0.000061 0.002005 0.000116 0.000730
1000 0.001784 0.313290 0.001653 0.004810
10000 0.126295 over 60sec 0.114638 0.047322

100回実行した時

n scipy ユーザ1 ユーザ2 ユーザ3
10 0.000043 0.000059 0.000141 0.000507
100 0.000535 0.001821 0.000750 0.004292
1000 0.018275 0.306701 0.017078 0.043484
10000 1.225358 over 60sec 1.161715 0.497158

1000回実行した時

n scipy ユーザ1 ユーザ2 ユーザ3
10 0.000385 0.000430 0.001337 0.004979
100 0.005945 0.003403 0.007389 0.040263
1000 0.165513 0.281874 0.179260 0.458516
10000 12.191156 over 60sec 11.926124 5.118705

まとめ

scipyは安定して速いですが,条件によってはユーザ定義型の方が高速に計算できることもあるようです。ただし,ユーザ定義型はそれぞれ一長一短なので,条件(想定される n の大きさや計算回数)に応じて使い分ける必要がありそうです。

参考

python リスト、辞書、セット型のinを使った時の参照速度を調べてみた。
Python3で組み合わせ計算を高速化
組み合わせの数

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away