Casio Python - 関数呼出オーバーヘッド

Python Casio Python
 Casioグラフ関数電卓の Python を使ってみる
     - 関数呼出オーバーヘッド:高速素因数分解(4) 
目次


初版:2020/08/02
前の記事 - 10. 大きな数の計算 |  次の記事 - 12. 要素数の多いリスト


11. 関数呼出オーバーヘッド:高速素因数分解(4) <fx-CG50 OS3.4以降>

前回、高速素因数分解の入力値を15桁まで拡張しました。

高速素因数分解 15桁対応版 - FactorF3.py のダウンロード

すると、以下のように素因数が15桁になるケースでは、実行時間が 23分30秒 もかかり、素因数探索のループを回る回数が 435万回程度になります (search:4349444)。
15digit_prime 

素因数探索の while ループでは、ckpwr() 関数を呼び出しています。そこで、この関数の中身を while ループ内に書き出し、ckpwr() 関数は削除します。つまり ckpwr() 関数呼出に要する時間 (呼出のオーバーヘッド) を節約して高速化を図ります。

ckpwr() 関数を削除するので for ループ内の ckpwr() 呼出部も関数内部を書き出します。


prime_list=[2,3,5,7,11]
for b in prime_list:
 search+=1
 d=a/b
 if frac(d)==0:
  e+=1
  z[e]=b
  while 1:
   a=int(d)
   z[e+21]+=1
   d=a/b
   if frac(d):
    break
  c=int(sqrt(a))
if b>cbreak


increment=\
[2,4,2,4,6,2,6,4,\
 2,4,6,6,2,6,4,2,\
 6,4,6,8,4,2,4,2,\
 4,8,6,4,6,2,4,6,\
 2,6,6,4,2,4,6,2,\
 6,4,2,4,2,10,2,10]

while 1:
 for i in increment:
  search+=1
  b+=id=a/b
  if frac(d)==0:
   e+=1
   z[e]=b
   while 1:
    a=int(d)
    z[e+21]+=1
    d=a/b
    if frac(d):
     break
   c=int(sqrt(a))
  if b>cbreak
 if b>c
break


11.1 関数呼出あり(ver 3) と なし(ver 4) の実行速度の違い

素因数の桁数の大きいケースとして、下記の10例を検討します。

search_30445_f Search_39969_f seach_47824_f 
Case1_14digit search_90872_f search_189426_f.png 
search_263027_f.png search_343013_f.png search_2025804_f.png 
search_4349444_f.png 


表1- ckpwr() 関数呼出の有無による実行時間の違い
関数あり (ver 3.0)関数なし (ver 4.0)
高速化
[秒]
関数呼出
[ミリ秒]
入力値serach回数実行時間
[秒]
1ループ
[ミリ秒]
実行時間
[秒]
1ループ
[ミリ秒]
547,896,321,054,78930,44510.00.3289.60.3150.40.013
7,845,162,037,84939,96913.00.32512.50.3130.50.013
748,159,026,374,81547,82415.50.32415.00.3140.50.010
36,209,518,473,62055,24117.70.32017.10.3100.60.011
986,753,421,098,67590,87229.70.32728.60.3151.10.012
96,835,724,130,261189,42660.00.31758.10.3071.90.010
748,159,026,396,835263,02783.00.31680.50.3062.50.010
96,835,724,136,209343,013109.00.318104.50.3054.50.013
748,159,026,336,2092,025,804667.0
(11分7秒)
0.329644.0
(10分44秒)
0.31823.00.011
362,095,184,736,2094,349,4441,410.0
(23分30秒)
0.3241,361.0
(22分41秒)
0.31349.00.011

ckpwr() 関数を使わずに while ループ内に書き出した ver 4.0 は、関数呼出のある ver 3.0 よりも速くなっていることが分かります。これらの時間差をグラフにしてみると、高速化の効果が分かりやすいです。
search_exectime 


11.2 Casio Python の関数呼出オーバーヘッド

関数呼出オーバーヘッド時間の平均値は 0.011 ミリ秒であり、Casio Python の関数呼出オーバーヘッドが思ったよりも小さいことが分かりました。

実際 Casio Python での関数呼出は、オーバーヘッドを殆ど気にする必要はなく、今回のロジックのように関数呼出を数百万回行うような場合に限って関数呼出のオーバーヘッドを気にすれば良いと思います。


==========

15桁入力対応、少し高速化版は下記のようになります。

※ 高速素因数分解 15桁入力対応少し高速化版 - FactorG4.py のダウンロード

fx-CG50 Pythonモード:高速素因数分解 - FactorG4.py
"""Sample script

Exercise;
ported from Casio Basic
"Prime Factor 10 digits"
factorG.py
ver 4.0

by Krtyski/e-Gadget
"""

from u import *
digit=
15
search=0

def disp():
 global a,e,f,z
 clear_screen()
 locate(00f3'm'0)
 locate(160': ' str(len(inp)) + ' digits'3'm'0)
 locate(16, 11, 'search:'+str(search), 2, 'm', 0)
 line(0,15,383,15,1,0)
 for i in range(115):
  if i<=e:
   dx=int(i/12)*16
   dy=int(i/12)*11
   locate(0+dxi-dyz[i], 1'm'0)
   locate(10+dxi-dy'^('2'm'0)
   locate(12+dxi-dyz[i+21], 1'm'0)
   locate(15+dxi-dy')'2'm'0)
 locate
(00''0'm'1)


while
1:
 try:
  inp=str(eval(input('Number:')))
 except (SyntaxError,TypeError,NameError) as e:
  print(e)
  print('*must be number or\n expression')
  continue
 if '.' in inp:
  print('*must be integer')
  continue
 elif inp.isdigit():
  if len(inp)>digit:
   print('*must be '+str(digit)+' digit\n or less')
   continue
  else:
   f=int(inp)
   break
 else:
  continue

z=list(range(23))
for e in range(1,23):
 z[e]=0
e=0
a=f
c=int(sqrt(a))

prime_list=[2,3,5,7,11]
for b in prime_list:
 search+=1
 d=a/b
 if frac(d)==0:
  e+=1
  z[e]=b
  while 1:
   a=int(d)
   z[e+21]+=1
   d=a/b
   if frac(d):
    break
  c=int(sqrt(a))
if b>cbreak


increment=\
[2,4,2,4,6,2,6,4,\
 2,4,6,6,2,6,4,2,\
 6,4,6,8,4,2,4,2,\
 4,8,6,4,6,2,4,6,\
 2,6,6,4,2,4,6,2,\
 6,4,2,4,2,10,2,10]

while 1:
 for i in increment:
  search+=1
  b+=id=a/b
  if frac(d)==0:
   e+=1
   z[e]=b
   while 1:
    a=int(d)
    z[e+21]+=1
    d=a/b
    if frac(d):
     break
   c=int(sqrt(a))
  if b>cbreak
 if b>c
break

if a>1:
 e+=1
 z[e]=a
 a=1
 z[e+11]=
1

disp
()


目 次

前の記事 - 10. 大きな数の計算

次の記事 - 12. 要素数の多いリスト





応援クリックをお願いします。励みになるので...
にほんブログ村 IT技術ブログ 開発言語へ


 


keywords: fx-CG50Pythonプログラム関数電卓

リンク集 | ブログ内マップ

関連記事

テーマ : プログラム関数電卓
ジャンル : コンピュータ

コメントの投稿

非公開コメント

最新記事
検索フォーム
最新コメント
カテゴリ
C# (3)
Visitors
Online Counter
現在の閲覧者数:
プロフィール

やす (Krtyski)

Author:やす (Krtyski)
since Oct 30, 2013


プログラム電卓は、プログラムを作って、使ってナンボ!

プログラム電卓を実際に使って気づいたこと、自作プログラム、電卓での Casio Basic や Casio Python プログラミングについて書いています。

なお管理人はカシオ計算機の関係者ではなく、Casio Basicが面白いと感じる1ユーザーです。


写真: 「4駆で泥んこ遊び@オックスフォード郊外」

リンク
月別アーカイブ
Sitemap

全ての記事を表示する

ブロとも申請フォーム

この人とブロともになる

QRコード
QR