acokikoy's notes

最近気になる=[NoCode, Shopify], I am..=[Python, ウクレレ, マニュアル車, CMS] LoveなWebディレクター

毎朝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
"""

コード

最終的に提出したコード: 対象数を順に素数判定する方法

  • mからnまで小さい方から順に素数判定し、素数ならギャップ判定する。
  • 素数判定は、2から自身の平方根+1まで、順に割って割りきれなかったら素数と判断する。
# 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

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))

note: 素数を求める方法「エラトステネスのふるい」

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