平均処理時間が明らかに一致しない

Question

import time
import numpy as np

NA ='ACGT'
n = 100000
s = ''
N=10
myBytes = {}
for n in range(5000,100000,5000):
    myBytes[n] = (s.join([random.choice(DNA) for i in range(n)])).encode()
    for j in range(N):
        st1_time = time.time() 
        xR = makeSuffixArrayByInducedSorting(myBytes[n],256,0,False) 
        et1_time = time.time()
        lap1_time= et1_time-st1_time
        np.mean(lap1_time)
        
        st2_time = time.time()
        nR = naivelyBuildSA(myBytes[n])
        et2_time = time.time()
        lap2_time = et2_time-st2_time
        np.mean(lap2_time)
    print("processing time：{} {} {}".format(np.mean(lap1_time),np.mean(lap2_time), xR==nR))

このようなコードを作成して,n=5000から100000まで5000ずつで変化させた時のn=5000の時にxRとnRを計算してその時の10回の平均を結果としてlap1_timeとlap2_timeで答えとして出力し,その後n=10000について同様の処理を行うというプログラムを書いたつもりでした.
n=100000だけを10回の平均を取るなどせず求めると大体lap2は12秒かかるのに対してこのプログラムで出てきた結果は3秒で明らかにプログラムの動作自体が遅いのでこのような結果になるはずがないのですが,このプログラムが間違っているのでしょうか.lap1の方は大体単体と同じような結果が得られています.

import time
import numpy as np

NA ='ACGT'
n = 100000
s = ''
N=10
myBytes = {}
st0_time = time.time()
for n in range(5000,100000,5000):
    myBytes[n] = (s.join([random.choice(DNA) for i in range(n)])).encode()
    lap1_time =0
    lap2_time =0
    for j in range(N):
        st1_time = time.time() 
        xR = makeSuffixArrayByInducedSorting(myBytes[n],256,0,False) 
        et1_time = time.time()
        lap1_time = et1_time-st1_time +lap1_time
        st2_time = time.time()
        nR = naivelyBuildSA(myBytes[n])
        et2_time = time.time()
        lap2_time= et2_time-st2_time + lap2_time
    ave1=lap1_time/N
    ave2=lap2_time/N
    print("processing time：{} {} {}".format(ave1,ave2, xR==nR))
print(time.time()-st0_time)

Comments

[1T2R3M4]

入門からやり直してみてはいかがでしょうか。

[jbpb0]

lap1_time, lap2_timeどちらも、forループが回る毎回、単に上書きされてるだけです
前回の結果は残ってませんので、ループが終わった状態では、最後に測った値が入ってるだけなので、平均はできません

質問の時間が合わないのはなぜ？ とは直接関係無いかもしれませんが、気になったので

[kaeruuuun]

>>jbpb0さん
コメントありがとうございます.
np.meanが平均値をとるものだと認識して行っていて,meanを表示しているつもりなのですが,違いますか?

[jbpb0]

ループの1回目で、
lap1_time= et1_time-st1_time
で、「lap1_time」にその時(ループ1回目)に計算された時間が代入されます

ループの2回目で、
lap1_time= et1_time-st1_time
で、「lap1_time」にその時(ループ2回目)に計算された時間が代入されます
その時に、ループ1回目に「lap1_time」に代入された数値は消えます (上書き代入してるだけだから)

ループ3回目以降も同様です
毎回、
lap1_time= et1_time-st1_time
で、「lap1_time」にその時に計算された時間が代入されて、その数値だけ残ります

その結果、ループが終わった時に「lap1_time」に入ってる数値は、ループの最後の回に計算された時間だけです

[kaeruuuun]

meanをループの外に出してみた(for jと同じ位置)にしてもうまくいきませんでした.

[jbpb0]

lap1_time= et1_time-st1_time
という上書き代入をしていて最後に計算した時間だけしか残らない、というところを直さない限り、何をしてもダメです

[kaeruuuun]

lap1_time= et1_time-st1_timeを
lap1_time+=lap1_time
のように定義してみたのですが,これは前回のが保存されて足されていくという式になっていますか?

[jbpb0]

for j in range(N):
のループで、(N=10の)10回の平均をしたいのですよね？
そうならば、
[n]ではなくて[j]でしょう
ただし、ループ初回(j=0)の[j-1]=[-1]はダメなので、そこ回避しないといけないけど

[jbpb0]

というか、単に
lap1_time= et1_time-st1_time+lap1_time
でいいのではないですか？
ただし、下記も要りますけど
・ループに入る前に0を代入する
・ループ終わった後にN(=10)で割る

【追記】 上記「ループ」とは、「for j in range(N):」のループのことです

[jbpb0]

あるいは、
lap1_time[j]= et1_time-st1_time
として、ループ終わった後に平均する

【追記】 上記「ループ」とは、「for j in range(N):」のループのことです

[ppaul]

NA ='ACGT'
は、
DNA ='ACGT'
の誤りですか？
他に誤りはありませんか？

[kaeruuuun]

lap1_time =0
lap2_time =0
for j in range(N):
st1_time = time.time()
xR = makeSuffixArrayByInducedSorting(myBytes[n],256,0,False)
et1_time = time.time()
lap1_time = et1_time-st1_time+lap1_time
st2_time = time.time()
nR = naivelyBuildSA(myBytes[n])
et2_time = time.time()
lap2_time = et2_time-st2_time+lap2_time
ave1=lap1_time/N
ave2=lap2_time/N
print("processing time：{} {} {}".format(ave1,ave2, xR==nR))
このように変えてみました.

[kaeruuuun]

インデントがないように見えますが,aveとprintはforの外においています.

[kaeruuuun]

DNAでプログラムは作成できています.コピペのミスです.申し訳ございません.

[kaeruuuun]

上のように変えてみましたが,やはり中身としては変わっていなさそうです.

[jbpb0]

> インデントがないように見えますが,aveとprintはforの外においています.

はい
print(... で、10回平均の時間(ave1, ave2)が表示されると思います

それが、「for n in range(5000,100000,5000):」のループで毎回起きます (一つのnに対して1回)
それで意図通りですよね？

[kaeruuuun]

意図はnを5000から100000まで変化させる中で一つのnに対して10回計算を行い,それの平均を求めるということです.
ただ結果は前回同様単体での結果と大きく離れてしまっています.

[kaeruuuun]

なので意図としてはjbpb0さんの意図であっていると思います.

[退会済みユーザー]

回答者のみなさん、そもそも質問の意味わかってます？
私は質問文の意味（「質問者さんが何をおかしいと思っているのか」）が、質問文からはまったくわかりません。

質問者さん：次のような理解であってますか？
’’’
「for n in range(5000,100000,5000):」と「 for j in range(N):」のループを削除して、
n=100000だけに設定して実行したら、
lap2は「3秒」と表示された。

しかし for n とfor j のループを削除せずに、質問文記載のコードの通りに実行すると、
lap2は「12秒」と"表示された"。

同じコードを同じように実行しているだけなのに、明らかに後者の方が遅い時間として"表示"される。
これがなぜだかわからない’’’’

質問者さんが「聞きたいこと」はこのような理解であってますでしょうか？

[jbpb0]

myBytes = {}
の行の次に
st0_time = time.time()
を追加

コードの一番下(インデント無し)に
print(time.time()-st0_time)
を追加

上記をしてから実行したら、最後にコード全体の実行時間が表示されます

それと、ave1, ave2の表示される全部の合計を10倍したものは、全然違うのですか？

[kaeruuuun]

インデントなしに
print(time.time()-st0_time)を入れると全てのforを抜けた後になるので,それを10倍してもそれぞれの計算時間にはならない気がしますが,その位置で大丈夫でしょうか.

[kaeruuuun]

今のprintがある位置の下に入れたらそれぞれのnに対しての実行時間が分かりませんか?

[kaeruuuun]

現状の形を上に追加しました.インデントもそのまま示されています.

[jbpb0]

10倍するのは、ave1, ave2を全部足したもの
ave1, ave2は、「n」が変わる度に表示されるので、それぞれ19回表示されますよね？
それら38個の数値を全部足して10倍する

それと、print(time.time()-st0_time) の表示を比べる (こちらは10倍しないでそのまま)

[jbpb0]

仮に、「n」が変わっても、計算時間はほとんど変わらないとします
19個のave1はほとんど同じ、19個のave2もほとんど同じ場合です

その場合、
(ave1 + ave2) * 10 * 19 ≒ print(time.time()-st0_time)
になるはずなのですが、それが全然合わないのだろうか？？ と

もちろん、「n」によって計算時間がかなり変わるなら、上記のような安直な計算はできず、地道に全部のave1, ave2を足さないといけない

[kaeruuuun]

計算量が多くなってしまうので,n=15000までで計算してみたのですが,
processing time：0.02545895576477051 0.009452056884765626 True
processing time：0.04150521755218506 0.022467756271362306 True
1.0012428760528564

のように出力されて4つの和が0.0988839864730835だったので10倍しても一致しません.
のような結果になって

[kaeruuuun]

processing time：0.02383921146392822 0.008798360824584961 True
0.3307487964630127
processing time：0.04224090576171875 0.022389841079711915 True
0.9837450981140137
それぞれで合計時間を出してみたのですが,これもave1+ave2が等しくなっていないです.

[kaeruuuun]

nによって計算時間は大きく変わります.

[jbpb0]

> 1.0012428760528564のように出力されて

> 4つの和が0.0988839864730835だったので10倍しても一致しません

0.0988839864730835*10=0.988839864730835
と
1.0012428760528564
が一致しない、と言ってるのですか？
差は
0.988839864730835-1.0012428760528564=-0.012403011322021484
と0.01秒ほどで、ave1, ave2で時間測ってるところ以外のループ回すところとかでかかってる時間だと思いますが

[kaeruuuun]

ではこの結果だけで言えば,10回の平均が求まっていると言って良いのですか.
お分かりの通り私は知識が豊富ではないのですが,全く一致していなくでもこの程度の時間差なら等しいと言って良いのですか.

[退会済みユーザー]

>4つの和が0.0988839864730835だったので10倍しても一致しません.
（手計算お疲れ様です）

一致しないとしても、
1.0012428760528564　-　0.0988839864730835*10
＝0.012403011322021484(秒）
というように、差は大変小さいので、n=15000までの範囲では、ほとんど違わない、と考えていいでしょう。

つまり、jbpb0さんが多分確認したかったであろう
「makeSuffixArrayByInducedSortingとnaivelyBuildSA”以外"の部分に体感できるほどの計算時間がかかっているのか否か」については、n=15000までの範囲では、おそらくNOである、ということです。

（個人的な推測ですが、n=100000にしても特に差は大きい数値にならないでしょう（いって0.1秒））

[kaeruuuun]

print("processing time：{} {} {}".format(ave1,ave2, xR==nR))
print(time.time()-st0_time)
のようにインデントを揃えて配置した場合2つ目のprintで出力されるのはave1とave2の和を10倍したものと一致すると考えて良いですか.

[kaeruuuun]

n=100000も試してみたほうが良いですか?

[jbpb0]

> それぞれで合計時間を出してみたのですが

は、最後の「print(time.time()-st0_time)」のインデントを、その前の「print("processing...」に合わせる、という意味ですかね？
もしそうなら、「st0_time = time.time()」の位置を、
for j in range(N):
のすぐ上に変えないといけません

> 2つ目のprintで出力されるのはave1とave2の和を10倍したものと一致すると考えて良いですか

上記を行えば、そうなります

[退会済みユーザー]

>一致していなくでもこの程度の時間差なら等しいと言って良いのですか.
厳密にいえば、等しくはないですが、差が小さければ特に問題になりません。

>インデントを揃えて配置した場合2つ目のprintで出力されるのはave1とave2の和を10倍したものと一致すると考えて良いですか.
→修正します。これについてはjbpb0さんの書かれた通りです。

[kaeruuuun]

であればこれは比較対象が間違っていますね.今は全体の時間で考えます.

[kaeruuuun]

>baitokunさん
分かりました.
ありがとうございます.

[jbpb0]

たくさんのave1, ave2を足すのが面倒なら、下記のように変えたら簡単になります

lap1_time =0
lap2_time =0
を
for n in range(5000,100000,5000):
よりも上に移す

ave1=lap1_time/N
ave2=lap2_time/N
print("processing time：{} {} {}".format(ave1,ave2, xR==nR))
のインデントを無くす

ave1=lap1_time/N
ave2=lap2_time/N
の「/N」を取る (割り算やめる)

そうすれば、ave1, ave2(名前が良くないけど)はコード全体の合計値になるので、ave1+ave2はコード全体の計算時間とだいたい合うはず (10倍とかしなくていい)

[kaeruuuun]

n=95000単体で求めるとprocessing time：0.4466898441314697 3.4324429035186768 True
となってこのプログラムを使って求まったものがprocessing time：0.41282033920288086 2.7798306941986084 Trueと微小な差ですがこれをn=100000にすると単体だと10秒くらいと出て,このプログラムだと4秒くらいになるのが私の疑問点です.

[kaeruuuun]

>jbpbさん
やってみます.

[kaeruuuun]

自分のミスで95000までの時間になっています.
processing time：39.85334515571594 168.13135766983032 True
208.5171971321106
大体一致はしています.

[退会済みユーザー]

>これをn=100000にすると単体だと10秒くらいと出て,このプログラムだと4秒くらいになるのが私の疑問点です.

ああ、そういうことですか。やっとあなたが知りたい疑問点が分かりました。

これは naivelyBuildSAの具体的なプログラムを載せてもらわないと、だれも何とも言えないと思いますよ？

質問のプログラムの通りならば、

・単体でn=100000のとき　naivelyBuildSAが10秒かかった、
・n を5000から95000まで、5000刻みで実行したときにn=95000のときの最後の10回目のnaivelyBuildSA（lap2）が3～4秒しかかからなかった
ということですよね？

後者はたまたまキャッシュ？等が利いて早く実行された、という可能性がゼロではないと思いますが、
実際のコードで検証しないと何とも言えない。

[jbpb0]

(39.85334515571594+168.13135766983032)/208.5171971321106=0.9974462811034863
ですから、総合計時間の内の99.7%は、二つの関数の計算時間である、ということです
よく合ってると思いますけど

[kaeruuuun]

>・単体でn=100000のとき　naivelyBuildSAが10秒かかった、
・n を5000から995000まで、5000刻みで実行したときにn=95000のときの最後の10回目のnaivelyBuildSA（lap2）が3秒しかかからなかった
ということですよね？

そうです.
単純に求めたコードは
import time

NA ='ACGT'
n = 100000
s = ''
myBytes = (s.join([random.choice(DNA) for i in range(n)])).encode()

st1_time = time.time()
xR = makeSuffixArrayByInducedSorting(myBytes,256,0,False)
et1_time = time.time()
lap1_time = et1_time-st1_time

st2_time = time.time()
nR = naivelyBuildSA(myBytes)
et2_time = time.time()
lap2_time = et2_time-st2_time

print("processing time：{} {} {}".format(lap1_time, lap2_time, xR==nR))
このような形です.このコードと上のプログラムで10回の平均を求めた結果とこんなにも差が出るものですか.

[退会済みユーザー]

ちなみにネットで makeSuffixArrayByInducedSorting　を手掛かりに検索して
出てきたコードを私の手元で実行した限りでは、naivelyBuildSAに該当する関数（実際には「naivelyMakeSuffixArray」という名前）が含まれるコードを
n=100000で10回繰り返して各回の実行時間を計測しましたが、
1回目～10回目まで、どの回でも15秒～20秒かかっています。

1回目も10回目もブレはあるにしても15～20秒の範囲でバラバラの秒数であり、後になるにしたがって早くなるという現象は起きていません。
（Intel Core i5 9400F 2.9GHz/Windows 10/Python 3.9.5 Visual Studio Code上のPowerShell）
ただし私の手元のコードとあなたのコードが同じかどうかはわからないので、「何とも言えません」

[kaeruuuun]

>よく合ってると思いますけど
私もそう思います.
ただ,一つ前に載せたコメントで求めたものと大きく時間が違うので,プログラムとしては10回平均を求めているのに平均を求めた方が計算時間が早くなるのは腑に落ちない部分があります.

[kaeruuuun]

もし可能であればそのnaivelyMakeSuffixArrayを載せていただけますか.こちらで一致しているか確認します.

[kaeruuuun]

>>> def naivelyMakeSuffixArray(source):
... """
... A naive, slow suffix-array construction algorithm.
... """
...
... # Construct a list of suffixes of the source string.
... suffixes = []
... for offset in range(len(source) + 1):
... suffixes.append(source[offset:])
...
... # Sort the suffixes
... suffixes.sort()
...
... # Calculate the start offset of each suffix, storing them in
... # sorted order into the suffix array.
... suffixArray = []
... for suffix in suffixes:
... offset = len(source) - len(suffix)
... suffixArray.append(offset)
...
... return suffixArray
ですか？

[jbpb0]

> これをn=100000にすると単体だと10秒くらいと出て

for n in range(5000,100000,5000):
のループには「n=100000」の場合は含まれません

ループに含まれない条件の時間と、ループの総合計時間を比べて「合わない」と言われても

そこが気になるなら、ループを
for n in range(5000,100001,5000):
に変えて時間測ったらいいのでは？？

[kaeruuuun]

申し訳ございません.
確認します.

[kaeruuuun]

ave2の方がずれているのでave2の方だけ言うと
単体:9.259315967559814
プログラム:processing time：4.121449637413025
です.

[kaeruuuun]

たまたま単体の方はこの秒数なわけではなく,いつも10秒付近です.

[退会済みユーザー]

環境要因かもしれないので、OSと実行環境、pythonのバージョン、CPU、メモリを教えてください。

[kaeruuuun]

python3でjupyternotebookを使っています.
環境はMacOSでCPUは2.0GHz,メモリは8GBです.

[kaeruuuun]

OSのバージョンは11.4
Mac OS Big Surです.
Python 3.8.8です.

[退会済みユーザー]

2.0GHzということは、MacのCPUはM1ですか？ Mac book pro？　いずれにしても自分はIntelなので同じ条件で計測できません。

[kaeruuuun]

Mac book proです.

[jbpb0]

ループを
for n in range(5000,100001,5000):
に変えて時間測ったら、総合計時間と、ave1+ave2のどちらも、10*10=100秒くらい増えて、結果やはり時間合いました、になるのではないですかね

「n=100000」での計算1回あたり約10秒で、
for j in range(N):
のループで10回計算されるから、10秒の10倍

ave1, ave2の計算は、総合計バージョンの場合です (2021/06/01 15:29のコメント)

[kaeruuuun]

processing time：0.027766036987304687 0.013672447204589844 True
processing time：0.04400126934051514 0.02627565860748291 True
processing time：0.0701488733291626 0.05143883228302002 True
processing time：0.09950840473175049 0.08780455589294434 True
processing time：0.10814404487609863 0.119659423828125 True
processing time：0.1344465732574463 0.15548162460327147 True
processing time：0.15326950550079346 0.23942835330963136 True
processing time：0.1734851121902466 0.38886399269104005 True
processing time：0.18961904048919678 0.5400986194610595 True
processing time：0.21131110191345215 0.7217737436294556 True
processing time：0.2361222267150879 0.9357278347015381 True
processing time：0.2673609256744385 1.167260479927063 True
processing time：0.32854504585266114 1.711254620552063 True
processing time：0.3717369556427002 2.1400886297225954 True
processing time：0.3733197212219238 2.351224398612976 True
processing time：0.43237712383270266 2.970620846748352 True
processing time：0.42038469314575194 3.0756006479263305 True
processing time：0.4015098333358765 2.96927649974823 True
processing time：0.42518389225006104 3.8412546873092652 True
processing time：0.5294559717178344 6.706105041503906 True
352.86083817481995
これがfor n in range(5000,100001,5000):でしてみた結果です.

[退会済みユーザー]

for n in range(5000,100001,5000)　で最後が6.7秒
単体n=100000だと10秒
3.3秒を誤差と見るか、大きな差と見るか、ですね。

[jbpb0]

> ave1, ave2の計算は、総合計バージョンの場合です (2021/06/01 15:29のコメント)

でやってほしかった

めんどくさかったけど、20個のave1, ave2を全部足したら、35.21060729でした
それを10倍したら、352.1060729です

それを352.86083817481995で割ったら、0.997861012です
総合計時間の99.8%がave1, ave2で説明できます
まだ「腑に落ちません」か？

ちなみに、一番下のave1, ave2
processing time：0.5294559717178344 6.706105041503906 True
の合計7.235561013秒が、n=100000での計算時間の10回平均

[jbpb0]

ループを
for n in range(100000,100001,5000):
に変えて実行してみてください
そうしたら、「n=100000」での計算だけを10回やります

その時の総合計時間(一番最後に表示される数値)はいくつですか？
それを10で割った数値が、「n=100000」単独の計算時間です
1回だけで測るよりも、10回平均の方が信頼できます

[kaeruuuun]

>jbpb0さん
色々と申し訳ございませんでした.
私が意図していることとずれていないか確認したいのですが,ave1はlap1の10回平均,ave2はlap2の10回平均で私はそれぞれの10回平均を求めたいという認識で間違っていないですよね？
>for n in range(100000,100001,5000):の結果は
processing time：0.5066619873046875 7.232007169723511 True
77.4687888622284
です.

[kaeruuuun]

これがやはり単独計算と差が出てしまうのが個人的には不思議です.
しつこくてごめんなさい.

[退会済みユーザー]

単独でやると10秒
10回繰り返して平均したところ7.7秒、ということですよね？

で
＞やはり単独計算と差が出てしまうのが個人的には不思議です.
という疑問に答えるためには、次に「1回目から10回目はそれぞれ何秒かかっているのか」を確認する必要があると思います。

仮に1回目が単体でやったときと同じ10秒くらいかかっていて、回数を繰り返すにしたがってだんだん早くなっているならば
「同じ処理を繰り返している」ためにだんだん速くなっているのだ、と推測できます。

（当初の質問のコードで「３～４秒しかかからなかった」理由は、n=100000より5000少ないn=95000の、しかも10回繰り返したときの最後の結果だけしか表示されていなかったから、です）

ではなぜ同じ処理を繰り返していると速くなるのか、の本当の理由については、実際のコードを掲載していただかなければ解析しようがないと思います。

もっとも、実際は速度がばらばらで、たまたま最後が速かっただけ、という可能性もあります。

[jbpb0]

> ave1はlap1の10回平均,ave2はlap2の10回平均

そうです

> processing time：0.5066619873046875 7.232007169723511 True
> 77.4687888622284

から、「n=100000」での10回計算の総合計時間は77.5秒なので、1回あたりは平均約8秒です
その内の約7秒がave2、すなわち「naivelyBuildSA()」でかかってる時間です

[jbpb0]

10秒と言ってますが、実際は

> ave2の方がずれているのでave2の方だけ言うと
単体:9.259315967559814

9秒のこともあるのですよね
10秒が、どこまで正しいのか？？

【追記】 上記9秒は、1回計算のave2だけの時間ですね
失礼しました

[kaeruuuun]

>baitokonさん
内容理解しました.
ありがとうございます.

[kaeruuuun]

>jbpd0さん
>9秒のこともあるのですよね
10秒が、どこまで正しいのか？？

よく考えればそうですね.
一度1から2とか10回にせずにやってみます.

[kaeruuuun]

やはりその時の環境によって誤差は出ます.
先ほどYouTubeをつけながら計測してみたら単体だと15秒でした.
短くなることはあまりないような気がします.

[kaeruuuun]

皆さん少し自分の中で理解ができたような気がします.
今N=1から少しずつ増やして行っているのですが,Nが小さいとave2が10秒という値が出ます.どういう理由かは分かりませんが,Nを増やすと計算時間が短くなるようなことがあるという発想が自分の中ではありませんでした.
N=1は10秒程度だったり8秒だったりもするのですがN=2以上にすると8秒だったり7秒だったりしてNを7など大きい値にするほど4秒程度に収束するような感じです.

[kaeruuuun]

自分の知識不足で皆さんを巻き込んでしまい申し訳ございませんでした.
ご対応いただいた方本当にありがとうございました.
jbpb0さんいつもありがとうございます.

Answer 1

測定に影響する要因は多数あるので。以下のことに気をつけてください。

• CPUの省電力設定(BIOSで設定)

　省電力設定がenableになっていると、負荷が低いときはクロックが遅くなっているため、高負荷の場合にくらべて長い時間がかかるけいこうがある。
省電力設定はdisableにしておきましょう。

• キャッシュに載っているかどうか

　最初に一回ダミー実行をしてコードをキャッシュに載せ、データも可能な限りキャッシュに載せる。

• データのページ内配置

　データがページング単位の1ページに入っているか、複数ページにまたがっているかで性能に差が出ることがある。コントロールは難しい。

以下はPythonに特有のものです。

• ライブラリの読み込み時間

　Pythonの場合は、Numpy、Scipy、Pandasなど、読み込み時間がかかるものが多い。
測定するときはimportが全て終わった時点から測定を開始することで正確に測定できます。

• for文のオーバーヘッド

　Python3になってfor文のオーバーヘッドが増えました。
for文で10回繰り返しをするより、同じことを10回書いた方が正確に測定できます。

こういうことに注意して測定し直してみてください。

Comments

[kaeruuuun]

分かりました.
ありがとうございます.

Answer 2

コメントで

もし可能であればそのnaivelyMakeSuffixArrayを載せていただけますか.こちらで一致しているか確認します.

との要望がありましたので、記載します。

def naivelyMakeSuffixArray(source):

     """
     A naive, slow suffix-array construction algorithm.
     """

     # Construct a list of suffixes of the source string.
     suffixes = []
     for offset in range(len(source) + 1):
         suffixes.append(source[offset:])

     # Sort the suffixes
     suffixes.sort()

     # Calculate the start offset of each suffix, storing them in
     # sorted order into the suffix array.
     suffixArray = []
     for suffix in suffixes:
         offset = len(source) - len(suffix)
         suffixArray.append(offset)

     return suffixArray

Comments

[kaeruuuun]

ありがとうございます.全く同じではないようです.

[退会済みユーザー]

コメントに貴方が書かれたソースと、どこがちがうのでしょうか？(コメントではインデントがわからないのですが、インデントが異なるのでしょうか？）

[kaeruuuun]

私が書いたのはサイトからのコピペで私が実際に使っている関数とは異なります.

[退会済みユーザー]

承知しました