Effizienz von Rekursion

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Effizienz von Rekursion

    Hallo,

    mein Programm funktioniert sehr gut aber nur solange ich kleine m und n angebe. Wenn ich große Zahlen für m und n wähle, rechnet es ein paar Tage. Kann mir jemand helfen, um diese Rekursion effizienter zu machen??? Ich wollte die Daten in eine Tabelle schreiben aber das hat irgendwie nicht geklappt. Danke für jeden Hinweis.

    Quellcode

    1. #include<stdio.h>
    3. float zeta_0(int m, int n)
    4. {float epsilon=1;
    5. float delta=6
    6. if(m==0) return 0;
    7. if(n==0) return 0;
    8. else return 1+((delta*n*zeta_0(m,n-1)+epsilon*m*n*zeta_0(m-1,n+1))/(delta*n+epsilon*m*n));
    9. }
    12. float zeta_1(int m, int n)
    13. {
    14. float M=6;
    15. float rho=6;
    16. if(m==0) return 0;
    17. if(n==0) return 0;
    18. else
    19. return ((M/rho)+M*n+m*n+M*zeta_0(m+1,n)+M*n*zeta_1(m,n-1)+m*n*zeta_1(m-1,n+1)-M*zeta_0(m,n))/(M*n+m*n);
    20. }
    22. main()
    23. {int m;
    24. int n;
    26. m=20;n=20;
    28. printf("%f\n",zeta_0(m,n));
    29. printf("%f\n",zeta_1(m,n));
    30. }
    Alles anzeigen


    Maria

  • Hallo!

    Wie du vielleicht bemerkt hast, werden die selben Werte irrsinnig oft berechnet wie z.B. zeta0(1,1) etc.
    Wenn man sich die Zwischenergebnisse cached, geht das ganze super schnell.
    Ich habe einen simplen Cache eingeführt bei dessen Anwendung sogar 100/100 ganz flott geht.

    Der Caches ist eine map die für jedes "m" eine Map enthält, die jedem "n" einen Wert zuweist. Mehr oder weniger ein dynamisches 3 dimensionales Array mit log(N) Zugriff pro Dimension :)

    Quellcode

    1. #include <stdio.h>
    2. #include <float.h>
    3. #include <map>
    4. #include <set>
    5. using namespace std;
    7. const float INVALID_CACHE_VALUE = FLT_MAX;
    9. class Cache : private map <int, map <int, float>* >
    10. {
    11. private:
    12. typedef map<int, float> innercont_t;
    13. public:
    14. virtual ~Cache ()
    15. {
    16. // free memory
    17. const_iterator cit = begin ();
    18. for (; cit != end (); ++cit)
    19. delete (*cit).second;
    20. }
    22. // returns INVALID_CACHE_VALUE if not found
    23. float getCachedValue (const int m, const int n)
    24. {
    25. // is m contained?
    26. const_iterator cit = find (m);
    27. if (cit != end ())
    28. {
    29. // yes -> is n contained?
    30. innercont_t* pCont = (*cit).second;
    31. innercont_t::const_iterator cit2 = pCont->find (n);
    32. if (cit2 != pCont->end ())
    33. return (*cit2).second;
    34. }
    35. return INVALID_CACHE_VALUE;
    36. }
    38. void addToCache (const int m, const int n, const float aValue)
    39. {
    40. // get container mapping of m
    41. innercont_t* pCont;
    42. const_iterator cit = find (m);
    43. if (cit != end ())
    44. pCont = (*cit).second;
    45. else
    46. {
    47. pCont = new map<int, float> ();
    48. insert (make_pair (m, pCont));
    49. }
    51. // add to inner cont
    52. pCont->insert (make_pair (n, aValue));
    53. }
    54. };
    56. // global variables for the cache
    57. Cache g_aCacheZeta0, g_aCacheZeta1;
    59. float zeta_0(const int m, const int n)
    60. {
    61. // check at the beginning - faster than cache lookup
    62. if (m == 0 || n == 0)
    63. return 0;
    65. // query cache
    66. float ret = g_aCacheZeta0.getCachedValue (m, n);
    67. if (ret == INVALID_CACHE_VALUE)
    68. {
    69. // calculate
    70. const float epsilon=1;
    71. const float delta=6;
    72. ret = 1+((delta*n*zeta_0(m,n-1)+epsilon*m*n*zeta_0(m-1,n+1))/(delta*n+epsilon*m*n));
    73. // add to cache
    74. g_aCacheZeta0.addToCache (m, n, ret);
    75. }
    76. return ret;
    77. }
    80. float zeta_1 (const int m, const int n)
    81. {
    82. // check at the beginning - faster than cache lookup
    83. if(m == 0 || n == 0)
    84. return 0;
    86. // query cache
    87. float ret = g_aCacheZeta1.getCachedValue (m, n);
    88. if (ret == INVALID_CACHE_VALUE)
    89. {
    90. // calculate
    91. const float M=6;
    92. const float rho=6;
    93. ret = ((M/rho)+M*n+m*n+M*zeta_0(m+1,n)+M*n*zeta_1(m,n-1)+m*n*zeta_1(m-1,n+1)-M*zeta_0(m,n))/(M*n+m*n);
    94. // add to cache
    95. g_aCacheZeta1.addToCache (m, n, ret);
    96. }
    97. return ret;
    98. }
    100. int main()
    101. {
    102. int m = 100;
    103. int n = 100;
    104. printf("%f\n",zeta_0(m,n));
    105. printf("%f\n",zeta_1(m,n));
    106. return 0;
    107. }
    Alles anzeigen


    hth

  • Und das ganze kann für mehrere Durchläufe insofern noch optimiert werden, als das der Inhalt des Caches in eine Datei gespeichert wird, bzw. von dort gelesen wird.
    Edit: Außerdem habe ich einige Berechnungen die doppelt durchgeführt wurden gespeichert (M*n, m*n, ...)
    Das ganze schaut dann so aus:

    Quellcode

    1. // compile with:
    2. // cl -EHsc -Ox zeta.cxx
    4. #if _MSC_VER >= 1400
    5. #define _CRT_SECURE_NO_DEPRECATE
    6. #endif
    8. #include <stdio.h>
    9. #include <float.h>
    10. #include <map>
    11. #include <set>
    12. using namespace std;
    14. const float INVALID_CACHE_VALUE = FLT_MAX;
    16. class Cache : private map <int, map <int, float>* >
    17. {
    18. private:
    19. typedef map<int, float> innercont_t;
    20. unsigned long m_nHits;
    21. unsigned long m_nMisses;
    22. bool m_bAltered;
    23. public:
    24. Cache ()
    25. : m_nHits (0),
    26. m_nMisses (0),
    27. m_bAltered (false)
    28. {}
    30. virtual ~Cache ()
    31. {
    32. // free memory
    33. const_iterator cit = begin ();
    34. for (; cit != end (); ++cit)
    35. delete (*cit).second;
    36. }
    38. // read cache file
    39. void read (const char *pFilename)
    40. {
    41. FILE* f = fopen (pFilename, "rb");
    42. if (f)
    43. {
    44. int m, n;
    45. unsigned long nSize;
    46. float v;
    47. innercont_t* pCont;
    48. while (fread (&m, sizeof (int), 1, f) == 1)
    49. {
    50. // read number of mappings
    51. fread (&nSize, sizeof (unsigned long), 1, f);
    53. // create new map for current m
    54. pCont = new innercont_t ();
    55. insert (make_pair (m, pCont));
    57. // read all mappings
    58. for (unsigned long i = 0; i < nSize; ++i)
    59. {
    60. fread (&n, sizeof (int), 1, f);
    61. fread (&v, sizeof (float), 1, f);
    63. // add mapping
    64. pCont->insert (make_pair (n, v));
    65. }
    66. }
    67. fclose (f);
    68. }
    69. }
    71. // write cache file
    72. void write (const char *pFilename)
    73. {
    74. // save cache only if something was changed
    75. if (m_bAltered)
    76. {
    77. FILE* f = fopen (pFilename, "wb");
    78. if (f == NULL)
    79. {
    80. fprintf (stderr, "Failed to open cache file %s for writing\n", pFilename);
    81. return;
    82. }
    83. for (const_iterator cit = begin (); cit != end (); ++cit)
    84. {
    85. const int m = (*cit).first;
    86. innercont_t* pCont = (*cit).second;
    87. const unsigned long nSize = pCont->size ();
    88. fwrite (&m, sizeof (int), 1, f);
    89. fwrite (&nSize, sizeof (unsigned long), 1, f);
    90. for (innercont_t::const_iterator cit2 = pCont->begin (); cit2 != pCont->end (); ++cit2)
    91. {
    92. const int n = (*cit2).first;
    93. const float v = (*cit2).second;
    94. fwrite (&n, sizeof (int), 1, f);
    95. fwrite (&v, sizeof (float), 1, f);
    96. }
    97. }
    98. fclose (f);
    99. }
    100. }
    102. // returns INVALID_CACHE_VALUE if not found
    103. float getCachedValue (const int m, const int n)
    104. {
    105. // is m contained?
    106. const_iterator cit = find (m);
    107. if (cit != end ())
    108. {
    109. // yes -> is n contained?
    110. innercont_t* pCont = (*cit).second;
    111. innercont_t::const_iterator cit2 = pCont->find (n);
    112. if (cit2 != pCont->end ())
    113. {
    114. ++m_nHits;
    115. return (*cit2).second;
    116. }
    117. }
    118. ++m_nMisses;
    119. return INVALID_CACHE_VALUE;
    120. }
    122. void addToCache (const int m, const int n, const float aValue)
    123. {
    124. // get container mapping of m
    125. innercont_t* pCont;
    126. const_iterator cit = find (m);
    127. if (cit != end ())
    128. pCont = (*cit).second;
    129. else
    130. {
    131. pCont = new innercont_t ();
    132. insert (make_pair (m, pCont));
    133. }
    135. // add to inner cont
    136. pCont->insert (make_pair (n, aValue));
    137. m_bAltered = true;
    138. }
    140. unsigned long getHits () const
    141. {
    142. return m_nHits;
    143. }
    145. unsigned long getMisses () const
    146. {
    147. return m_nMisses;
    148. }
    149. };
    151. // global variables for the cache
    152. Cache g_aCacheZeta0, g_aCacheZeta1;
    154. float zeta_0(const int m, const int n)
    155. {
    156. // check at the beginning - faster than cache lookup
    157. if (m == 0 || n == 0)
    158. return 0;
    160. // query cache
    161. float ret = g_aCacheZeta0.getCachedValue (m, n);
    162. if (ret == INVALID_CACHE_VALUE)
    163. {
    164. // calculate
    165. const float epsilon=1;
    166. const float delta=6;
    167. const float epsilonmn = epsilon * m * n;
    168. const float deltan = delta * n;
    169. ret = 1+((deltan*zeta_0(m,n-1)+epsilonmn*zeta_0(m-1,n+1))/(deltan+epsilonmn));
    170. // add to cache
    171. g_aCacheZeta0.addToCache (m, n, ret);
    172. }
    173. return ret;
    174. }
    177. float zeta_1 (const int m, const int n)
    178. {
    179. // check at the beginning - faster than cache lookup
    180. if(m == 0 || n == 0)
    181. return 0;
    183. // query cache
    184. float ret = g_aCacheZeta1.getCachedValue (m, n);
    185. if (ret == INVALID_CACHE_VALUE)
    186. {
    187. // calculate
    188. const float M=6;
    189. const float rho=6;
    190. const float Mn = M * n;
    191. const float mn = m * n;
    192. ret = ((M/rho)+Mn+mn+M*zeta_0(m+1,n)+Mn*zeta_1(m,n-1)+mn*zeta_1(m-1,n+1)-M*zeta_0(m,n))/(Mn+mn);
    193. // add to cache
    194. g_aCacheZeta1.addToCache (m, n, ret);
    195. }
    196. return ret;
    197. }
    199. int main()
    200. {
    201. printf ("Reading cache\n");
    202. g_aCacheZeta0.read ("zeta0");
    203. g_aCacheZeta1.read ("zeta1");
    205. printf ("Calculating\n");
    206. int m = 1000;
    207. int n = 1000;
    208. printf("%f\n",zeta_0(m,n));
    209. printf("%f\n",zeta_1(m,n));
    211. // print cache stats
    212. printf ("Cache hits zeta_0: %lu\n", g_aCacheZeta0.getHits ());
    213. printf ("Cache misses zeta_0: %lu\n", g_aCacheZeta0.getMisses ());
    214. printf ("Cache hits zeta_1: %lu\n", g_aCacheZeta1.getHits ());
    215. printf ("Cache misses zeta_1: %lu\n", g_aCacheZeta1.getMisses ());
    217. printf ("Writing cache\n");
    218. g_aCacheZeta0.write ("zeta0");
    219. g_aCacheZeta1.write ("zeta1");
    220. printf ("Cleaning up\n");
    221. return 0;
    222. }
    Alles anzeigen


    Mehr fällt mir diesbzgl. nicht ein.
    Viel Spaß :)