＊ 以下の項目における各手法の評価はあくまで個人的なものです。
目次
- 既存ツールを用いた手法１（評価 ☆）
- 既存ツールを用いた手法２（評価 ☆☆）
- 既存ツールを用いた手法３（評価 ☆☆☆）
- ユーザ定義型１（評価 ☆☆）
- ユーザ定義型２（評価 ☆☆☆）
- ユーザ定義型３（評価 ☆☆）
- 番外編
- 計算時間の比較
- まとめ
既存ツールを用いた手法１（評価 ☆）
itertools.combinations()で組み合わせのリスト作ってその大きさを求める。
sample.py
import itertools
a = len(list(itertools.combinations(range(n), r)))
メリット
思いつきません...
デメリット
- 遅い
- メモリを圧迫する
既存ツールを用いた手法２（評価 ☆☆）
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 → 成功
既存ツールを用いた手法３（評価 ☆☆☆）
外部ライブラリ 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型で近似された値が返されるので，正確な値を求めたい場合にも，この引数が必要になります。（その分若干遅くなります。）
ユーザ定義型１（評価 ☆☆）
辞書と再帰を利用
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が大きい場合にはメモリを圧迫する
ユーザ定義型２（評価 ☆☆☆）
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文が増える
ユーザ定義型３（評価 ☆☆）
「組み合わせの数」 にある方法を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 | ユーザ１ | ユーザ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 | ユーザ１ | ユーザ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 | ユーザ１ | ユーザ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で組み合わせ計算を高速化
組み合わせの数