fork(1) download
copy 
  1. import time
  2. import numpy as np
  3.  
  4. N = 10
  5.  
  6. def mul(m, n):
  7.   if m > n: m, n = n, m
  8.   sum = 0
  9.   for i in range(m):
  10.     sum += n
  11.   return sum
  12.  
  13. def dev(m, n):
  14.   count = 0
  15.   while m >= n:
  16.     m -= n
  17.     count += 1
  18.   return count
  19.  
  20. def fact(n, r=1):
  21.   if n <= 1 or n <= r:
  22.     return 1
  23.   m = 1
  24.   for i in range(r, n+1):
  25.     m = mul(m, i)
  26.   return m
  27.  
  28. def show_time(func):
  29.   t_start = time.time()
  30.   for i in range(8000):
  31.     for j in range(N):
  32.       func(N, j)
  33.   t_end = time.time()
  34.   print("{0}: {1:.3f} [sec]".format(func.__name__, t_end - t_start))
  35.  
  36. def comb1(n, r):
  37.   return dev(fact(n), mul(fact(r), fact(n-r)))
  38.  
  39. def comb2(n, r):
  40.   return dev(fact(n, n-r+1), fact(r))
  41.  
  42. def comb3(n, r):
  43.   r, n = r+1, n-r+1
  44.   c = np.zeros((r, n), dtype=np.int32)
  45.   c[0], c[:] = 1, 1
  46.   for i in range(1, r):
  47.     for j in range(1, n):
  48.       c[i][j] = c[i][j-1] + c[i-1][j]
  49.   return c[r-1][n-1]
  50.  
  51. def comb4(n, r):
  52.   c = np.zeros(r+1, dtype=np.int32)
  53.   c[-1] = 1
  54.   for i in range(n): c[:r] += c[1:r+1]
  55.   return c[0]
  56.  
  57. show_time(comb1)
  58. show_time(comb2)
  59. show_time(comb3)
  60. show_time(comb4)
Success #stdin #stdout 4.93s 24860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
comb1: 1.451 [sec]
comb2: 0.916 [sec]
comb3: 1.336 [sec]
comb4: 1.138 [sec]
https://ideone.com/HiLbVM
language:
Python 3 (python  3.9.5)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!