毎朝Codewars@2019.04.30(火): Gap in Primes
毎朝ちびちびCodewars。
Gap in Primes [5級] www.codewars.com
今日のお題：
""" m以上 n以下の素数で、隣の素数との差がgである最小の組み合わせ[P(i), P(i+1)]を返す
Args:
g (int >= 2):
m (int > 2): 対象範囲の開始値（mを含む）
n (int >= m): 対象範囲の終了値 (nを含む）
Returns:
(list): ギャップgとなる最初の組み合わせ
gap(2, 5, 7) -> [5, 7]
gap(4, 130, 200) --> [163, 167]
gap(2, 5, 5) -> None
"""
コード
最終的に提出したコード: 対象数を順に素数判定する方法
# Gap in Primes # https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4 def gap(g, m, n): p0 = n for p1 in range(m, n+1): if is_prime(p1): if p1 - p0 == g: return [p0, p1] p0 = p1 return None def is_prime(num): for i in range(2, int(num**0.5+1)): if num % i == 0: return False return True
参考≫ 実行時間の計測
import timeit if __name__ == '__main__': loop = 1 print("gap(2, 5, 7)",timeit.timeit('gap(2, 5, 7)',globals=globals(), number=loop)) print("gap(20, 5, 1000)",timeit.timeit('gap(20, 5, 1000)',globals=globals(), number=loop)) print("gap(20, 800, 1000)",timeit.timeit('gap(20, 800, 1000)',globals=globals(), number=loop)) print("gap(44, 5, 20000)",timeit.timeit('gap(44, 5, 20000)',globals=globals(), number=loop)) print("gap(44, 15000, 20000)",timeit.timeit('gap(44, 15000, 20000)',globals=globals(), number=loop)) print("gap(2,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) print("gap(154,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) print("gap(154,5,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) # 結果 # gap(2, 5, 7) 1.5234982129186392e-05 # gap(20, 5, 1000) 0.0007256029930431396 # gap(20, 800, 1000) 9.462502202950418e-05 # gap(44, 5, 20000) 0.017462561023421586 # gap(44, 15000, 20000) 0.0009225230023730546 # gap(2,10000000,11000000) 0.0014848650025669485 # gap(154,10000000,11000000) 0.0014871359744574875 # gap(154,5,11000000) 0.0014404239773284644 # [Finished in 0.2s]
最初の解き方: あらかじめ素数の一覧を用意する方法（エラトステネスのふるい）
最初考えたのは、エラトステネスのふるい方式であらかじめ素数の一覧を用意して、それとの比較で素数判定する方法だった。この解き方は、m, n値と共に所持時間が膨大になり、codewarsの規定時間内に収まらなかった。
v1.0
- エラトステネスのふるい方式。
- 2からnまでの2と奇数のリストを用意する。最初の2と3は素数で、以降には素数以外が含まれるいわば素数候補リスト。小さい方から順に素数の倍数を除外していって素数のリストを完成させる。
- 同時に素数ギャップの計算をして解が見つかったところで処理を終了する。
- m, nが大きい値になると素数リスト生成処理に膨大な時間がかかりcodewarsの規定時間に収まらない。
- v1.0（下記コード）では gap(2,10000000,11000000) で125秒もかかってしまう。
# Gap in Primes # https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4 def gap(g, m, n): numbers = [2] + list(range(3, n+1, 2)) # [2, 3,...] 2と奇数 i=0 while i < len(numbers)-1: p0 = numbers[i] p1 = numbers[i+1] if p1**2 <= n: omit = list(range(p1*p1, n+1, p1)) numbers = list(set(numbers)-set(omit)) numbers.sort() if p0 >= m and p1 - p0 == g: return [p0, p1] i += 1 return None
参考≫ 実行時間の計測
import timeit if __name__ == '__main__': loop = 1 print("gap(2, 5, 7)",timeit.timeit('gap(2, 5, 7)',globals=globals(), number=loop)) print("gap(20, 5, 1000)",timeit.timeit('gap(20, 5, 1000)',globals=globals(), number=loop)) print("gap(20, 800, 1000)",timeit.timeit('gap(20, 800, 1000)',globals=globals(), number=loop)) print("gap(44, 5, 20000)",timeit.timeit('gap(44, 5, 20000)',globals=globals(), number=loop)) print("gap(44, 15000, 20000)",timeit.timeit('gap(44, 15000, 20000)',globals=globals(), number=loop)) print("gap(2,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) print("gap(154,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) print("gap(154,5,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop)) # 結果 # gap(2, 5, 7) 8.681003237143159e-06 # gap(20, 5, 1000) 0.0004923160013277084 # gap(20, 800, 1000) 0.0004484140081331134 # gap(44, 5, 20000) 0.018813159986166283 # gap(44, 15000, 20000) 0.017344633990433067 # gap(2,10000000,11000000) 124.84585471099126 # gap(154,10000000,11000000) 125.46680217300309 # gap(154,5,11000000) 125.57621433699387
v1.3
- あらかじめ素数リストを生成するエラトステネスのふるい方式は踏襲しつつ、時短のための改善バージョン 。
- setからlistへの変換など無駄な処理をやめた。他には終了判定の見直し。
- 同時に素数ギャップの計算をして解が見つかったところで処理を終了する。
- m, nが大きい値になると素数リスト生成処理に膨大な時間がかかりcodewarsの規定時間に収まらない。
- gap(2,10000000,11000000) で125秒->3秒台まで時短したが、m, n値とともにsetの演算処理が膨大になる点の根本解決とはならず、この方式ではcodewarsの規定処理時間をクリアできないので断念。
# Gap in Primes # https://www.codewars.com/kata/561e9c843a2ef5a40c0000a4 def gap(g, m, n): # numbersは素数候補からなるset。初期値は[2, 3,...] 2と奇数。 max = int(n**.5+1) numbers = set([2] + list(range(3, n+1, 2))) for i in range(3, max): if i in numbers: # numbers内のi以下の数字は全部素数 # エラトステネスのふるい: i^2以降のiの倍数を除外する numbers -= set(list(range(i**2, n+1, i))) prev = n for i in range(m, n+1): if i in numbers: if i - prev == g: return [prev, i] prev= i return None
参考≫ 実行時間の計測
import time import timeit def gap(g, m, n): # numbersは素数候補からなるset。初期値は[2, 3,...] 2と奇数。 t0 = time.time() cnt1 = 1 max = int(n**.5+1) numbers = set([2] + list(range(3, n+1, 2))) for i in range(3, max): if i in numbers: # numbers内のi以下の数字は全部素数 # エラトステネスのふるい: i^2以降のiの倍数を除外する numbers -= set(list(range(i**2, n+1, i))) cnt1 += 1 t1 = time.time() period1 = t1 - t0 avr1 = period1 / cnt1 cnt2 = 1 prev = n for i in range(m, n+1): if i in numbers: if i - prev == g: period2 = time.time() - t1 avr2 = period2 / cnt2 print(f"time: {period1}({cnt1}) , {period2}({cnt2})") return [prev, i] prev= i cnt2 += 1 return None if __name__ == '__main__': # print(gap(20, 5, 1000)) loop = 1 print("gap(2, 5, 7)",timeit.timeit('gap(2, 5, 7)',globals=globals(), number=loop), "\n", "="*20) print("gap(20, 5, 1000)",timeit.timeit('gap(20, 5, 1000)',globals=globals(), number=loop), "\n", "="*20) print("gap(20, 800, 1000)",timeit.timeit('gap(20, 800, 1000)',globals=globals(), number=loop), "\n", "="*20) print("gap(44, 5, 20000)",timeit.timeit('gap(44, 5, 20000)',globals=globals(), number=loop), "\n", "="*20) print("gap(44, 15000, 20000)",timeit.timeit('gap(44, 15000, 20000)',globals=globals(), number=loop), "\n", "="*20) print("gap(2,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop), "\n", "="*20) print("gap(154,10000000,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop), "\n", "="*20) print("gap(154,5,11000000)",timeit.timeit('gap(2,10000000,11000000)',globals=globals(), number=loop), "\n", "="*20) # 結果 # time: 0.00014400482177734375(11) , 4.9114227294921875e-05(153) # gap(20, 5, 1000) 0.0002230769896414131 # ==================== # time: 0.00013589859008789062(11) , 7.867813110351562e-06(16) # gap(20, 800, 1000) 0.00017084201681427658 # ==================== # time: 0.0029828548431396484(34) , 0.0008180141448974609(1830) # gap(44, 5, 20000) 0.003917734982678667 # ==================== # time: 0.0019800662994384766(34) , 3.695487976074219e-05(78) # gap(44, 15000, 20000) 0.0021105850173626095 # ==================== # time: 3.0778968334198(466) , 1.2159347534179688e-05(6) # gap(2,10000000,11000000) 3.1167126119835302 # ==================== # time: 3.0525267124176025(466) , 1.1205673217773438e-05(6) # gap(154,10000000,11000000) 3.0880573879985604 # ==================== # time: 3.1027848720550537(466) , 1.1205673217773438e-05(6) # gap(154,5,11000000) 3.140642618993297 # ==================== # [Finished in 9.6s]```
note: Pythonで処理時間の計測を行う方法
プログラム内の処理時間を計測したい場合、timeモジュールを使って2点間の経過時間を測定する方法と、timeitモジュールを使う方法とある。 timeitモジュールを使う方法は、処理の繰り返し回数を指定して計測できる。
timeを使う: プログラム内 2点間の経過時間を測定
# Pythonのプログラム内で経過時間を測定 import time start = time.time() # # 計測対象の処理 # ... end = time.time() t = end - start
- time.time()で、エポックからの経過秒数を浮動小数点で返す。エポックはUTCで1970 年 1 月 1 日 0 時 0 分 0 秒。精度はシステムに依存する。 time --- 時刻データへのアクセスと変換 — Python 3.7.3 ドキュメント
timeitを使う: 関数やメソッドの処理時間を測定
import timeit
def test(n):
"""Stupid test function"""
L = [i for i in range(n)]
def f(x):
return x**2
def g(x):
return x**4
def h(x):
return x**8
if __name__ == '__main__':
num = 100
print(timeit.timeit("test(num)", number=10000, globals=globals()))
print(timeit.timeit('[func(42) for func in (f,g,h)]', globals=globals(), number=100))
- globalsでグローバルな名前空間を渡すことにより関数や変数にアクセスできる。これがないと関数test, f, g, hや変数nが認識されない。
- number: でメイン文の繰り返し回数を指定する。デフォルトは100万回。
note: 素数を求める方法「エラトステネスのふるい」
- エラトステネスのふるいは指定された整数x以下の全ての素数を発見するアルゴリズム。
- エラトステネスの篩 - Wikipedia
- エラトステネスのふるいとその計算量 | 高校数学の美しい物語
2番目の文献によればエラトステネスのふるいは、愚直に割り算して判定する方法に比べ "圧倒的に計算量が少ない" とあるのだが、自分が組んだプログラムでは反対の結果になった。 setの演算部分が重いのだが、コードの書き方が悪いのかこの方法の限界なのか問題根本的な原因まで行き着けず。後日の宿題となった。
import timeit def prime_by_era(n): # numbersは素数候補からなるset。初期値は[2, 3,...] 2と奇数。 max = int(n**.5+1) numbers = set([2] + list(range(3, n+1, 2))) for i in range(3, max): if i in numbers: # numbers内のi以下の数字は全部素数 # エラトステネスのふるい: i^2以降のiの倍数を除外する numbers -= set(list(range(2*i, n+1, i))) def prime(n): numbers = [2] max = int(n**.5+1) for num in range(3, max): if is_prime(num): numbers.append(num) def is_prime(num): for i in range(2, int(num**0.5+1)): if num % i == 0: return False return True if __name__ == '__main__': loop = 1 print("prime_by_era(7)",timeit.timeit('prime_by_era(7)',globals=globals(), number=loop)) print("prime(7)",timeit.timeit('prime(7)',globals=globals(), number=loop)) print("="*20) print("prime_by_era(100000)",timeit.timeit('prime_by_era(100000)',globals=globals(), number=loop)) print("prime(100000)",timeit.timeit('prime(100000)',globals=globals(), number=loop)) # 結果 # prime_by_era(7) 1.8274993635714054e-05 # prime(7) 3.482011379674077e-06 # ==================== # prime_by_era(100000) 0.02143146700109355 # prime(100000) 0.00028548698173835874
