fork download
copy 
  1. //original post: http://s...content-available-to-author-only...o.com/2011/03/17/automatic-memoization-in-cplusplus0x/
  2. //a BOOST way of doing it: http://w...content-available-to-author-only...t.org/doc/libs/1_49_0/libs/flyweight/example/fibonacci.cpp
  3. #include <iostream>
  4. #include <functional>
  5. #include <map>
  6.  
  7. #include <time.h>
  8.  
  9. //maahcros
  10. #define TIME(__x) init=clock(); __x; final=clock()-init; std::cout << "time:"<<(double)final / ((double)CLOCKS_PER_SEC)<<std::endl;
  11. #define TIME_INIT  clock_t init, final;
  12. //void sleep(unsigned int mseconds) { clock_t goal = mseconds + clock(); while (goal > clock()); }
  13.  
  14. //the original memoize
  15. template <typename ReturnType, typename... Args>
  16. std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
  17. {
  18. 	std::map<std::tuple<Args...>, ReturnType> cache;
  19. 	return ([=](Args... args) mutable  {
  20. 		std::tuple<Args...> t(args...);
  21. 		if (cache.find(t) == cache.end()) {
  22. 			cache[t] = func(args...);
  23. 		}
  24. 		return cache[t];
  25. 	});
  26. }
  27.  
  28. /// wrapped factorial
  29. struct factorial_class {
  30.  
  31. 	/// the original factorial renamed into _factorial
  32. 	int _factorial(int n) {
  33. 		if (n==0) return 1;
  34. 		else {
  35. 		 std::cout<<" calculating factorial("<<n<<"-1)*"<<n<<std::endl;
  36. 		 sleep(0.5);
  37. 		 return factorial(n-1)*n;
  38. 		}
  39. 	}
  40.  
  41. 	/// the trick function :)
  42. 	int factorial(int n) {
  43. 		if (memo) return (*memo)(n);
  44. 		return _factorial(n);
  45. 	}
  46.  
  47. 	/// we're not a function, but a function object
  48. 	int operator()(int n) {
  49. 		return _factorial(n);
  50. 	}
  51.  
  52. 	/// the trick holder
  53. 	std::function<int(int)>* memo;
  54.  
  55. 	factorial_class() { memo=0; }
  56. };
  57.  
  58. int main()
  59. {
  60.  TIME_INIT
  61. 	auto fact=factorial_class(); //virgin wrapper
  62. 	auto factorial = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy
  63. 	fact.memo=&factorial; //spoilt wrapper
  64. 	factorial = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy
  65.  
  66. 	TIME ( std::cout<<"factorial(3)="<<factorial(3)<<std::endl; ) // 3 calculations
  67. 	TIME ( std::cout<<"factorial(4)="<<factorial(4)<<std::endl; ) // 1 calculation
  68. 	TIME ( std::cout<<"factorial(6)="<<factorial(6)<<std::endl; ) // 2 calculations
  69. 	TIME ( std::cout<<"factorial(5)="<<factorial(5)<<std::endl; ) // 0 calculations
  70.  
  71.  	TIME ( std::cout<<"factorial(12)="<<factorial(12)<<std::endl; )
  72. 	TIME ( std::cout<<"factorial(8)="<<factorial(8)<<std::endl;  )
  73. 	return 0;
  74. }
  75.  
  76. //upd: gotta find a way to make it work with std::function<int(int)>* memo; instead of a pointer
Success #stdin #stdout 0s 3024KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 calculating factorial(3-1)*3
 calculating factorial(2-1)*2
 calculating factorial(1-1)*1
factorial(3)=6
time:0
 calculating factorial(4-1)*4
factorial(4)=24
time:0
 calculating factorial(6-1)*6
 calculating factorial(5-1)*5
factorial(6)=720
time:0
factorial(5)=120
time:0
 calculating factorial(12-1)*12
 calculating factorial(11-1)*11
 calculating factorial(10-1)*10
 calculating factorial(9-1)*9
 calculating factorial(8-1)*8
 calculating factorial(7-1)*7
factorial(12)=479001600
time:0
factorial(8)=40320
time:0
https://ideone.com/up6Vy
language:
C++14 (gcc 8.3)
created:
11 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!