This document is one of More SageMath Tutorials. You may edit it on github. \(\def\NN{\mathbb{N}}\) \(\def\ZZ{\mathbb{Z}}\) \(\def\QQ{\mathbb{Q}}\) \(\def\RR{\mathbb{R}}\) \(\def\CC{\mathbb{C}}\)
Demonstration: Cython: Python -> CΒΆ
Here is a function that computes \(\sum_{k=0}^N k\) in pure Python:
sage: def mysum(N):
....: s = int(0)
....: for k in range(1,N):
....: s += k
....: return s
sage: %time mysum(10^7)
Let us compare this with the Cython version:
sage: %%cython
sage: def mysum_cython(N):
....: cdef long long s = 0
....: cdef int k
....: for k in range(1,N):
....: s += k
....: return s
sage: %time mysum_cython(10^7)
A function to count the number of integer partitions with parts in a given set:
sage: def buying(coins, total):
....: vlist = [ [0] * len(coins) for _ in range(total + 1) ]
....: for i in range(total + 1):
....: for j, coin in enumerate(coins):
....: if j == 0:
....: if i % coin == 0:
....: vlist[i][j] = 1
....: else:
....: k = 0
....: while i - k >= 0:
....: vlist[i][j] += vlist[i - k][j - 1]
....: k += coin
....: return vlist[total][len(coins) - 1]
sage: [buying([1,2,5,10], i) for i in [1..20]]
[1, 2, 2, 3, 4, 5, 6, 7, 8, 11, 12, 15, 16, 19, 22, 25, 28, 31, 34, 40]
sage: [1,3..10]
[1, 3, 5, 7, 9]
Let us see how long it takes to find the number of partitions of 500 into odd parts:
sage: %time buying([1,3..500], 500)
732986521245024
Time: CPU 3.05 s, Wall: 3.05 s
Make two changes:
sage: %%cython
sage: def cybuying(coins, total):
....: cdef int i, j, k, coin
....: vlist = [ [0] * len(coins) for _ in range(total + 1) ]
....: for i in range(total + 1):
....: for j, coin in enumerate(coins):
....: if j == 0:
....: if i % coin == 0:
....: vlist[i][j] = 1
....: else:
....: k = 0
....: while i - k >= 0:
....: vlist[i][j] += vlist[i - k][j - 1]
....: k += coin
....: return vlist[total][len(coins) - 1]
Surely two tiny changes in some Python code cannot make it much faster:
sage: %time cybuying([1,3..500], 500)
732986521245024L
Time: CPU 0.08 s, Wall: 0.09 s
sage: 3.05/0.08
38.1250000000000