プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問 – Q11をPython（Cython）で解く

プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問 – Amazon

より問11を．

!pip install -q Cython
%load_ext Cython

Q11 フィボナッチ数列

Pythonは任意精度演算なので，特に気を付ける事もない．
フィボナッチ関数はメモ化再帰が有効な典型例．

from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
  return n if n<2 else fib(n-1) + fib(n-2)


def sol_q11():
  res, cnt = [], 0
  for i in range(100):
    a = fib(i)
    if a <= 144:      continue
    if a % sum(int(s) for s in str(a)) == 0:
      res.append(a)
      cnt += 1
    if cnt == 5:
      return res
  return 'Failed'


print(sol_q11())
%timeit sol_q11()

[2584, 14930352, 86267571272, 498454011879264, 160500643816367088]
1000 loops, best of 3: 259 µs per loop

%%cython
import cython
from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
  return n if n<2 else fib(n-1) + fib(n-2)


@cython.ccall
@cython.returns(list)
@cython.locals(res=list, cnt=cython.uint, i=cython.uint, a=cython.ulonglong, x=str) 
def sol_q11_cython02():
  res, cnt = [], 0
  for i in range(100):
    a = fib(i)
    if a <= 144:      continue
    if a % sum([int(x) for x in str(a)]) == 0:
      res.append(a)
      cnt += 1
    if cnt == 5:
      return res
  return

print(sol_q11_cython02())
%timeit sol_q11_cython02()

[2584, 14930352, 86267571272, 498454011879264, 160500643816367088]
10000 loops, best of 3: 107 µs per loop

1分1秒でも高速化したい場合は，一から書き下す覚悟が必要だけど，
（ただ今の様なメモ化再帰関数があったり，元のコードが効率的な場合は，
書き下したとしてもより効率的になるとは限らない……時間が掛かる）
手軽に（でも元のコードによっては何十倍も）高速化したい場合は，
Pure Python Mode – Cython documentationがリーズナブル．

サポートしている内包表記はlist, set, dictのみなので，
日頃，ジェネレータ式，ジェネレータ内包表記を活用していると，
Pure Python Modeでも多少の書き換えコストはあるけど．

intではオーバーフローを起こすので，unsigned long longにする．
桁出しはyieldを用いると簡単だが，yieldはcythonに無いので，そのままで．
メモ化再帰のままだと，Cythonを用いる部分が無くなるので，
フィボナッチ関数をループに置き換える．

%%cython


def od_gen(unsigned long long val):
  if val < 10:
    yield val
  else:
    yield from od_gen(val//10)
    yield val % 10


cdef unsigned long long fib(unsigned int n):
    cdef unsigned long long a = 0
    cdef unsigned long long b = 1
    
    for _ in range(n):
        a, b = b, a + b
    return b


cpdef list sol_q11_cython():
  cdef unsigned int cnt = 0
  cdef unsigned long long i
  cdef unsigned long long a, temp
  cdef list res = []
  
  for i in range(100):
    a = fib(i)
    if a <= 144:      continue
    temp = sum(od_gen(a))
    if a % temp == 0:
      res.append(a)
      cnt += 1
    if cnt == 5:
      break
  return res

print(sol_q11_cython())
%timeit sol_q11_cython()

[2584, 14930352, 86267571272, 498454011879264, 160500643816367088]
10000 loops, best of 3: 149 µs per loop

%%cython
import array
from cpython cimport array


cdef unsigned int N = 5


def od_gen(unsigned long long val):
  if val < 10:
    yield val
  else:
    yield from od_gen(val//10)
    yield val % 10


cdef unsigned long long fib(unsigned int n):
    cdef unsigned long long a = 0
    cdef unsigned long long b = 1
    
    for _ in range(n):
        a, b = b, a + b
    return b


cpdef array.array sol_q11_cython():
  cdef unsigned int cnt = 0
  cdef unsigned long long i
  cdef unsigned long long a, temp
  cdef array.array template = array.array('Q')
  cdef array.array res   = array.clone(template, N, zero=True)
  
  for i in range(100):
    a = fib(i)
    if a <= 144:      continue
    temp = sum(od_gen(a))
    if a % temp == 0:
      res[cnt] = a
      cnt += 1
    if cnt == N:
      break
  return res

print(sol_q11_cython())
%timeit sol_q11_cython()

array('Q', [2584, 14930352, 86267571272, 498454011879264, 160500643816367088])
10000 loops, best of 3: 150 µs per loop

%%cython
import numpy as np
cimport numpy as np


DTYPE = np.uint64
ctypedef np.uint64_t DTYPE_t

cdef unsigned int N = 5


def od_gen(unsigned long long val):
  if val < 10:
    yield val
  else:
    yield from od_gen(val//10)
    yield val % 10


cdef unsigned long long fib(unsigned int n):
    cdef unsigned long long a = 0
    cdef unsigned long long b = 1
    
    for _ in range(n):
        a, b = b, a + b
    return b


cpdef np.ndarray[DTYPE_t, ndim=1] sol_q11_cython():
  cdef unsigned int cnt = 0
  cdef unsigned long long i
  cdef unsigned long long a, temp
  cdef np.ndarray[DTYPE_t, ndim=1] res = np.zeros((N,), dtype=DTYPE)
  
  for i in range(100):
    a = fib(i)
    if a <= 144:      continue
    temp = sum(od_gen(a))
    if a % temp == 0:
      res[cnt] = a
      cnt += 1
    if cnt == N:
      break
  return res

print(sol_q11_cython())
%timeit sol_q11_cython()

[              2584           14930352        86267571272
    498454011879264 160500643816367088]
10000 loops, best of 3: 152 µs per loop

N数を増やすと，空間効率の順にnumpy.ndarray，array.array，listだった．
もう少し，色々な条件で確かめないとなんとも言えないけど，
実装効率も考慮すれば，numpy.ndarrayを用いるのがリーズナブルか．

しかし，今の場合はあれこれやるよりも，Pure Python Modeの方が良い．
アルゴリズムを一から考え直さない場合は，
Pure Python Modeがリーズナブルだなという印象．

プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問 – Q09をPython（Cython）で解く

プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問 – Q01からQ08をPython（Cython）で解く

「プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問」をPythonで解く – 問64

「プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問」をPythonで解く – 問18, 問22

「プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問」を何問か解く

プログラマ脳を鍛える数学パズルシンプルで高速なコードが書けるようになる70問 – Q04, Q05, Q07, Q09, Q10, Q11, Q13, Q14, Q15, Q16, Q17, Q20, Q21, Q28 をPythonで解く

	テーブルの再配置-Pandasでデータの整形に Funmatu より
	テーブルの再配置-Pandasでデータの整形に匿名より
	pandas.DataFrame.applyは（時空間効率の… に Pandasを使用してデータフレーム内の… より
	pandas.DataFrame.applyは（時空間効率の… に Pandasで構造化されていないデータを… より
	ある列でグループ分けして任意の列に基づいて値をアサインに Funmatu より