以前のバージョン（3.5より前）ではmathモジュールではなくfractionsモジュールにgcd()関数があるので注意。fractionsをインポートして、fractions.gcd()とする必要がある。. 【Python】組み合わせ(nCr) 計算の高速化 – Qiita.
| ➡gcd(3042, 390) = gcd(312, 390), 390 ÷ 312 = 1 余り 78 ユークリッド互除法とは、2つの自然数の最大公約数を高速に求めるアルゴリズムである。RSA暗号の処理などに用いられる。, この記事ではユークリッド互除法の解説とpythonで実装したプログラムを紹介する。, aとb(共に正の整数,a>b)の最大公約数gcd(a,b)を求めるとする。またa÷bの余りをrとすると、次の式が成り立つ。, ここで(a > b > r)であるから、gcd(a, b)と比べてgcd(r, b)のほうが扱う数字の値が小さくなる。, となる。このような操作を何度も繰り返していくとどんどん値が小さくなっていき、いずれ余りが0になる。そのときの割った数が最大公約数gcd(a,b)となる。, ユークリッド互除法の「互除」というのは、このような「お互いに除算し合う」という操作を表している。, 6474 ÷ 3432 = 1 余り 3042
0
完了する.
サトゥー. ➡ gcd(3042, 3432) = gcd(3042, 390), 3042 ÷ 390 = 7 余り 312
1-3. 問題集.
p)、逆元 (a^-1 mod. この章では速度の比較を省略しますが、The Performance of Python, Cython and C on a Vector — Cython def, cdef and cpdef functions 0.1.0 documentationによると最大で100倍程度速くなることもあるようです。 Pythonで実装したときに、処理時間が長すぎて要件を満たせないことがあります。そんなときにはこの記事で示す4種類の対策があります。, なお、高速化のために何かをすると別の何かを失います。トレードオフの代表例としては、表現の自由度、可読性、依存度、メモリ使用量、CPU使用量でしょうか。用法・容量を守って正しくお使いください。, また、高速化をする前にはスクリプトのどこが遅いのか、プロファイリングツールなどを使って確かめる必要があります。遅くない処理を頑張って高速化しても、全体の実行時間にはほとんど影響を与えません。この記事ではその手順については説明しません。, 本来は「ライブラリを使う」や「ライブラリを作る」といったほかの対策も「スクリプトを書き直す」に該当します。ここではPythonの言語仕様と標準ライブラリの範疇でできることとして、下記の手法を紹介します。標準ライブラリの範疇でできることなので、依存はあまり増えません(ただし、Pythonのバージョンには依存することがあります)。, Pythonのインタプリタの最適化はそれほど頑張ってくれません。同じことをするにもいろいろな書き方があるので、より高速な書き方を選んで高速化することができます。, ただし、実際のアプリケーションではここで例を挙げる書き方の違いでそんなに差は出ません。書き方の変換が思いつかない場合や遅い処理はほかの場所にあることが多いはずです。, もちろん、ちりも積もればなんとやらです。例えば、Pythonのみでデータベースの実装をしようと思うと、ここで例を挙げるような処理の遅さが効いてきて、全体としても使い物にならないくらい遅くなってしまいます。, 例えば、1からnまでの整数を足す処理を、「(1)forを使って足していく」「(2)ビルトインのsumを使う」「(3)総和の公式を使う」の3通りで実装して、時間を計ってみると下記のようになります。, リストを生成するときに、「(1)リスト内包表記を使う」「(2)forループでappendする」「(3)appendをキャッシュする」「(4)ビルトインのlist関数を使う」の4通りで実装して、時間を計ってみると下記のようになります。, この例では、リストを生成しているだけですが、一般的にはappendする前に「いろいろな処理」をするはずです。この「いろいろな処理」のほうが遅いことが多いので、「いろいろな処理」を高速化したほうが効果があります。, アルゴリズムとデータ構造は、大昔から研究されている分野です。計算量がオーダー記法で$O(n)$と$O(n^2)$では、実行時間も全然違います。アルゴリズムとデータ構造を自分で実装することもあれば、標準ライブラリにある便利なクラスを使う場合こともあります。, リストに特定の要素が含まれているかを何回も判定するときは、リストを集合(set)に変換してからinで確かめたほうが早いです。1回しか判定しないのであれば、集合に変換する処理時間が効いてくるでしょう。, 今回は、10000個の要素からなるリストに対して、10000回検索するだけでこの結果となりました。これくらいの量の探索なら、実際のアプリケーションでもよく出てくるのではないでしょうか。, リストの先頭に何度も値を追加したい時にはcollections.dequeを使うことができます。, Pythonのリストは、可変長配列のようなものです。配列の中身については、型や順序など何の前提もないので汎用性は高いですが、特定の処理では高速化・効率化の余地があります。collections.dequeのほかにもheapqやbisectなどコレクション(データの集まり)を扱う機能が標準ライブラリに用意されています。, 一度行った計算の結果をメモリ内に格納して再利用したり、データベースからとってきたデータをpickle形式でdumpすることで、高速化することができます。数学的な関数のような引数が一緒ならば常に同じ結果を返すものは、キャッシュすることができます。データベースと通信するよりも、ローカルファイルを読み込んだほうが高速な場合もあります。, Pythonにはfunctools.lru_cacheという関数をメモ化するためのデコレータが標準ライブラリに定義されています。これを使えば一度計算した結果がキャッシュされ、引数が同じであれば再利用されます。, @lru_cacheデコレータを付ければいいだけなのでお手軽ですね。実際にフィボナッチ数列を計算したいことはあまりないですし、計算したいとしても別の実装にするかもしれません。機械学習で積分を計算したい時などが代表的な応用例でしょうか。, 標準ライブラリのthreadingやmultiprocessingを使ったり、Python3.2で追加されたconcurrentを使って並列化することで高速化します。CPUがボトルネックでなければthreading、そうでなければmultiprocessingを使います。threadingのほうがデータの共有が簡単ですがGIL(Global Interpreter Lock)によりのCPU100%の壁を越えられないため、マルチコアCPUを使い切りたいのであればmultiprocessingを使うことになります。, concurrent.futureを使うのが簡単です。ProcessPoolExecutorを使えば、マルチプロセスで並列実行できます。マルチスレッドで実行するThreadPoolExecutorもあります。, 並列化したい処理を関数化して、ワーカー数を指定して呼び出すだけです。定型句として覚えてしまいましょう。, マルチプロセスにするのであれば、Pythonではなくshellで頑張ることもできます。前述の関数fをコマンドラインから実行可能にして、shellから並列に呼び出してあげることでマルチプロセスが実現できます。, Pythonの中で全部実現することもできますが、shellで&を付けるだけで気楽にマルチプロセスにするのも状況によってはありだと思います。, Pythonには標準ライブラリがたくさんありますし、サードパーティのライブラリはもっとたくさんあります。サードパーティのライブラリは、PyPIで公開されており、pipコマンドで簡単にインストールすることができます。, NumPyのような数値計算に特化したライブラリを使えば高速に数値計算できます。数値計算に限らず、特定の計算に対して最適化されたライブラリがあります。CuPyは、CUDAを使ってGPUによる計算をPythonから簡単に実行できるようにしてくれます。, NumPyを使うと行列やベクトルの計算が高速化できます。高速化できるだけでなく、コードが簡略になってわかりやすくなります。ここでは、100×1000の行列をイメージして100000個の要素からなるリストの各要素を足しています。, NumPyのほうが圧倒的に早いことがわかります。リストでは、要素の型やリストのメソッドが変わってしまうことを考慮しますが、NumPyでは型が固定されているのとBLASなどのライブラリを使えるため高速化できます。, ライブラリが何で実装されているかでも、速度に差ができます。まもなくサポートが終了するPython 2系ではpickle化にはpickleとcPickleという二つのライブラリがありました。どちらを使うかで実行時間に結構な差が出ます。Python 3系では、cPickleは_pickleライブラリという名前に代わってpickleをインポートしたときにcPickleが利用可能であれば内部的に呼び出されるようになりました。, Python 2系のIPythonなので表示が他と違いますが、10倍くらいの実行時間比ですね。, 最近のCPUにはいろいろな高速化機能があります。高速化機能自身が有効になっているか、高速化機能をうまく使えるライブラリを呼んでいるかで、実行時間に差ができます。下記のページに解説があります。, すでにPythonライブラリがあればインストールして使うだけでいいのですが、やりたいことに対応するPythonライブラリが必ずしもあるとは限りません。また、Pythonで書いたのではどうしても解消できない無駄な処理も結構あります。それでも高速化したい場合は、下記のいずれかの手法をとることになります。 Python 2系のIPythonなので表示が他と違いますが、10倍くらいの実行時間比ですね。 2-2.
78
どうも僕です。 Python(パイソン)を勉強し始めたので、いろいろなプログラムを書いています。今回は最大公倍数と最小公倍数を求めるプログラムを書きました。プログラムを書きながら、Pythonの使い方を勉強しています。私は数年前にC言語を少し授業で勉強したっきりの、まるっきりの素人です。 問題集. 標準ライブラリの例で挙げた例9: pickleとcPickleでは、10倍速くなっていました。, Pythonには、WindowsのdllファイルやLinuxのsoファイルからライブラリを読み込んで、ライブラリ内の関数を実行する機能(ctypes)が標準ライブラリあります。Pythonで書くと遅い処理を高速に実行する実装がすでにあるけれど、Pythonから呼び出せるようになっていない場合に使うことができます。, Pythonのmathライブラリには、立方根を求めるcbrt関数はありませんが、libmには定義されています。これを呼び出すには下記のようにします。, この例では嬉しさはわかりませんが、簡単に呼べることだけはおわかりいただけたかと思います。Python側でforを回すと遅いので、forで回す処理も実行してくれるような関数を呼び出せると高速化できます。, PythonのC拡張を使うと、C言語やC++言語を使ってPythonから呼び出せるライブラリを作ることができます。PythonはそもそもC/C++で作られたライブラリのラッパみたいなものなので、ラッパに呼び出される側を作ろうということです。, sample.soが出来上がるので、Pythonインタプリタ(IPython)を起動して読み込んでみます。, Boost.Pythonを使うと、少ないコードでPythonライブラリを実装できます。Pythonのバージョン差異もあまり気にしなくてよくなります。その代わり、Boostライブラリに依存してしまうため、Boostライブラリがない環境ではPythonライブラリが読み込みません。Boost.Pythonを使って作られたライブラリは、実装の方法にもよりますがC言語で実装した場合と同じくらい高速です。, Boost.Pythonで足し算関数を作ってみます。まずは、C++言語で下記のソースコードを書きます。たったこれだけです。, PythonのヘッダファイルやBoost.Pythonを指定して、g++でコンパイルします。, Cythonを使えば、Pythonをちょっと改造した言語でソースコードを書いて、C言語で書いたものと同じくらい高速なライブラリを生成することができます。手順は、Pythonライクな言語でpyxファイルを作成し、C言語のソースコードを生成し、それをコンパイルするという流れになります。, フィボナッチ数列を計算する関数をCythonで作ってみます。まずは、pyxファイルを作成します。ちょっと型の情報があるくらいで、ほぼPythonと同じ文法です。, cythonコマンドでpyxファイルをC言語のソースコードに変換します。そして、gccでコンパイルします。, fib.soが出来上がるので、Pythonインタプリタ(IPython)を起動して読み込んでみます。, Pythonですべて書いた場合が、「448 ms ± 4.22 ms」だったのでかなり改善されました。, ここまでは、C言語でライブラリを作成して高速化していました。ライブラリを作成するにはC言語やCythonによるPythonを拡張した言語の知識が必要で、Python以外の言語を学ぶ必要がありました。しかし、新しい言語を学ぶのはなかなか大変です。ここでは既存のPythonプログラムをできるだけそのままで拡張できる下記の手法を紹介します。, NumbaはLLVMを使ってLLRM IRからバイトコードを生成して高速化します。Pythonスクリプトが実行されるまでにできるもの - Qiitaにあるように、PythonはVM型のスクリプト言語で中間命令(バイトコード)を愚直に実行することで処理を実現します。, 本家サイトのガイドによると、バイトコードを最適化するだけでなくマシン命令を生成し関数呼び出しを置き換えるようです。すごいですね...。, PyPyは、Pythonで書かれたPython処理系です。 RPythonという、Pythonより少し機能が制限されていて最適化がしやすいPythonが動作します。 RPythonで実装されており、Python2.7とPython3.6と互換性があります。Python compatibility - PyPyによるとDjangoやFlaskといった著名なライブラリは動作確認しているとのことですし、PyPy Speedによると実行速度もなかなか優秀なようです。, 遅いと感じた処理への対応としてどの手法が適切かは時と場合によります。いろいろな選択肢を考慮したうえで、最適な手法を適用できると素敵ですね。, フィボナッチ数列の例ばかり出していますが、フィボナッチ数列を求めるのがアプリケーションの一般的なタスクではありません。高速化したい処理によってはNumbaよりCythonのほうが早いこともあるでしょう。
2重のfor文で全探索して条件を満たすものを見つければOKです。 Pythonスクリプトの書き方を見直す 2.
390 X=int(input())
å¼æ°ã§ä»»æã®åæ°ã®å¤ãåãåãé¢æ°, ãªã¹ãï¼é
åï¼ã§å¤ãåãåãé¢æ°.
1-4. 1-2. NumPyを用いた簡単な高速化2節では1節のプログラムの高速化について考えます。Pythonにおいては繰り返し文(for文など)は遅いと言われることが多いので、NumPyを用いて1節で取り扱ったプログラムの高速化を試みてみます。, x = np.arange(100000000)+1print(np.sum(x)), 計算結果自体は1節の1〜1億までの和を計算した結果と同じですが、処理時間についてはtotalで849msと、1節の15分の1程度に抑えられていることがわかります。このようにちょっとした処理を書き換えるだけでも、高速化が可能になります。もう少し実験を行なってみます。, 上記はさらにもう1桁上げ、1〜10億までの結果を計算して比較した結果です。繰り返し文を用いた実装の方が時間はかかっていますが、NumPyの方もそれなりにかかっていることがわかります。, 確認するとNumPyの実装の方がsysにかかる時間が多いので、totalの比とuserの比に分けて計算してみた結果が上記です。NumPyはuserよりもsysに時間がかかりやすいことがある程度見て取れます。, このように単純な和を計算するプログラムでも様々な要素が絡んでくるので、色々と試しつつ内部処理なども含めて高速化を行なっていくのが良さそうです。今回はラフに確認を行えれば十分だったのでここまでとします。, 3. 基本的にプログラミングは動けば良い派で可読性の高さを優先することが多いですが、処理の高速化が必要な際もあるので、Pythonを用いた処理高速化について考える新規シリーズを作成いたしました。最初から難しく考えると大変なので、しばらくは緩めに進め、徐々に内容を本格化していければと思います。（しばらくは体系立った解説にはしませんので、そういう意味ではあまり参考にしないようにお願いします）#1では繰り返し文の処理をmapを用いて置き換えた際の簡単なパフォーマンス比較を行います。以下、目次になります。1. 今回フィボナッチ数列を求めるのに再起を使っていますが、そもそも再起を除去すればもっと高速になりますね...。, 皆様のQuality of Python Lifeが素晴らしいものになりますように。, なお、私がこれまでPythonを学ぶにあたっては、上記以外の素敵な記事や書籍にお世話になっています。ここで紹介しきれないことを大変申し訳なく思っています。素晴らしい情報を公開・出版してくださり、ありがとうございます。その素晴らしい情報が、これからPythonを学ぶ方々の役に立つと信じています。, 株式会社日立製作所の横浜事業所で、データベース(HiRDB/HADB)を開発する部署の隣で、自社データベースを活用するサービス・ソリューションを作っています。
コード例
競技プログラミングを2020年4月に始めて、2か月半くらい経ちました。