Effizienz von Rekursion

Beginner

Friday, July 28th 2006, 1:37pm

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.

C Quellcode

#include<stdio.h>
 
float zeta_0(int m, int n)
{float epsilon=1;
float delta=6
if(m==0) return 0;
if(n==0) return 0;
else return 1+((delta*n*zeta_0(m,n-1)+epsilon*m*n*zeta_0(m-1,n+1))/(delta*n+epsilon*m*n));
} 
 
 
float zeta_1(int m, int n)
{
float M=6;
float rho=6;
if(m==0) return 0;
if(n==0) return 0;
else 
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); 
}
 
main()
{int m;
int n;
 
m=20;n=20;
 
printf("%f\n",zeta_0(m,n));
printf("%f\n",zeta_1(m,n));
}

Maria

af-fe

Trainee

Posts: 22

2

Sunday, July 30th 2006, 12:05pm

Der Algorithmus scheint extrem ineffizient zu sein, vielleicht gibt es eine andere Möglichkeit das Problem zu lösen, was willst du eigentlich damit berechnen?

phax

Professional

Posts: 763

3

Monday, July 31st 2006, 7:32am

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

C Quellcode

#include <stdio.h>
#include <float.h>
#include <map>
#include <set>
using namespace std;
 
const float INVALID_CACHE_VALUE = FLT_MAX;
 
class Cache : private map <int, map <int, float>* >
{
private:
  typedef map<int, float> innercont_t;
public:
  virtual ~Cache ()
  {
    // free memory
    const_iterator cit = begin ();
    for (; cit != end (); ++cit)
      delete (*cit).second;
  }
 
  // returns INVALID_CACHE_VALUE if not found
  float getCachedValue (const int m, const int n)
  {
    // is m contained?
    const_iterator cit = find (m);
    if (cit != end ())
    {
      // yes -> is n contained?
      innercont_t* pCont = (*cit).second;
      innercont_t::const_iterator cit2 = pCont->find (n);
      if (cit2 != pCont->end ())
        return (*cit2).second;
    }
    return INVALID_CACHE_VALUE;
  }
 
  void addToCache (const int m, const int n, const float aValue)
  {
    // get container mapping of m
    innercont_t* pCont;
    const_iterator cit = find (m);
    if (cit != end ())
      pCont = (*cit).second;
    else
    {
      pCont = new map<int, float> ();
      insert (make_pair (m, pCont));
    }
 
    // add to inner cont
    pCont->insert (make_pair (n, aValue));
  }
};
 
// global variables for the cache
Cache g_aCacheZeta0, g_aCacheZeta1;
 
float zeta_0(const int m, const int n)
{
  // check at the beginning - faster than cache lookup
  if (m == 0 || n == 0)
    return 0;
 
  // query cache
  float ret = g_aCacheZeta0.getCachedValue (m, n);
  if (ret == INVALID_CACHE_VALUE)
  {
    // calculate
    const float epsilon=1;
    const float delta=6;
    ret = 1+((delta*n*zeta_0(m,n-1)+epsilon*m*n*zeta_0(m-1,n+1))/(delta*n+epsilon*m*n));
    // add to cache
    g_aCacheZeta0.addToCache (m, n, ret);
  }
  return ret;
}
 
 
float zeta_1 (const int m, const int n)
{
  // check at the beginning - faster than cache lookup
  if(m == 0 || n == 0)
    return 0;
 
  // query cache
  float ret = g_aCacheZeta1.getCachedValue (m, n);
  if (ret == INVALID_CACHE_VALUE)
  {
    // calculate
    const float M=6;
    const float rho=6;
    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);
    // add to cache
    g_aCacheZeta1.addToCache (m, n, ret);
  }
  return ret;
}
 
int main()
{
  int m = 100;
  int n = 100;
  printf("%f\n",zeta_0(m,n));
  printf("%f\n",zeta_1(m,n));
  return 0;
}

hth

Latest blogs: Yahoo! Search BOSS, Groovy 1.5 ist da, Visual Studio 2008 ist da

phax

Professional

Posts: 763

4

Monday, July 31st 2006, 8:10am

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:

C Quellcode

// compile with:
// cl -EHsc -Ox zeta.cxx
 
#if _MSC_VER >= 1400
#define _CRT_SECURE_NO_DEPRECATE
#endif
 
#include <stdio.h>
#include <float.h>
#include <map>
#include <set>
using namespace std;
 
const float INVALID_CACHE_VALUE = FLT_MAX;
 
class Cache : private map <int, map <int, float>* >
{
private:
  typedef map<int, float> innercont_t;
  unsigned long m_nHits;
  unsigned long m_nMisses;
  bool m_bAltered;
public:
  Cache ()
    : m_nHits    (0),
      m_nMisses  (0),
      m_bAltered (false)
  {}
 
  virtual ~Cache ()
  {
    // free memory
    const_iterator cit = begin ();
    for (; cit != end (); ++cit)
      delete (*cit).second;
  }
 
  // read cache file
  void read (const char *pFilename)
  {
    FILE* f = fopen (pFilename, "rb");
    if (f)
    {
      int m, n;
      unsigned long nSize;
      float v;
      innercont_t* pCont;
      while (fread (&m, sizeof (int), 1, f) == 1)
      {
        // read number of mappings
        fread (&nSize, sizeof (unsigned long), 1, f);
 
        // create new map for current m
        pCont = new innercont_t ();
        insert (make_pair (m, pCont));
 
        // read all mappings
        for (unsigned long i = 0; i < nSize; ++i)
        {
          fread (&n, sizeof (int), 1, f);
          fread (&v, sizeof (float), 1, f);
 
          // add mapping
          pCont->insert (make_pair (n, v));
        }
      }
      fclose (f);
    }
  }
 
  // write cache file
  void write (const char *pFilename)
  {
    // save cache only if something was changed
    if (m_bAltered)
    {
      FILE* f = fopen (pFilename, "wb");
      if (f == NULL)
      {
        fprintf (stderr, "Failed to open cache file %s for writing\n", pFilename);
        return;
      }
      for (const_iterator cit = begin (); cit != end (); ++cit)
      {
        const int m = (*cit).first;
        innercont_t* pCont = (*cit).second;
        const unsigned long nSize = pCont->size ();
        fwrite (&m, sizeof (int), 1, f);
        fwrite (&nSize, sizeof (unsigned long), 1, f);
        for (innercont_t::const_iterator cit2 = pCont->begin (); cit2 != pCont->end (); ++cit2)
        {
          const int n = (*cit2).first;
          const float v = (*cit2).second;
          fwrite (&n, sizeof (int), 1, f);
          fwrite (&v, sizeof (float), 1, f);
        }
      }
      fclose (f);
    }
  }
 
  // returns INVALID_CACHE_VALUE if not found
  float getCachedValue (const int m, const int n)
  {
    // is m contained?
    const_iterator cit = find (m);
    if (cit != end ())
    {
      // yes -> is n contained?
      innercont_t* pCont = (*cit).second;
      innercont_t::const_iterator cit2 = pCont->find (n);
      if (cit2 != pCont->end ())
      {
        ++m_nHits;
        return (*cit2).second;
      }
    }
    ++m_nMisses;
    return INVALID_CACHE_VALUE;
  }
 
  void addToCache (const int m, const int n, const float aValue)
  {
    // get container mapping of m
    innercont_t* pCont;
    const_iterator cit = find (m);
    if (cit != end ())
      pCont = (*cit).second;
    else
    {
      pCont = new innercont_t ();
      insert (make_pair (m, pCont));
    }
 
    // add to inner cont
    pCont->insert (make_pair (n, aValue));
    m_bAltered = true;
  }
 
  unsigned long getHits () const
  {
    return m_nHits;
  }
 
  unsigned long getMisses () const
  {
    return m_nMisses;
  }
};
 
// global variables for the cache
Cache g_aCacheZeta0, g_aCacheZeta1;
 
float zeta_0(const int m, const int n)
{
  // check at the beginning - faster than cache lookup
  if (m == 0 || n == 0)
    return 0;
 
  // query cache
  float ret = g_aCacheZeta0.getCachedValue (m, n);
  if (ret == INVALID_CACHE_VALUE)
  {
    // calculate
    const float epsilon=1;
    const float delta=6;
    const float epsilonmn = epsilon * m * n;
    const float deltan = delta * n;
    ret = 1+((deltan*zeta_0(m,n-1)+epsilonmn*zeta_0(m-1,n+1))/(deltan+epsilonmn));
    // add to cache
    g_aCacheZeta0.addToCache (m, n, ret);
  }
  return ret;
}
 
 
float zeta_1 (const int m, const int n)
{
  // check at the beginning - faster than cache lookup
  if(m == 0 || n == 0)
    return 0;
 
  // query cache
  float ret = g_aCacheZeta1.getCachedValue (m, n);
  if (ret == INVALID_CACHE_VALUE)
  {
    // calculate
    const float M=6;
    const float rho=6;
    const float Mn = M * n;
    const float mn = m * n;
    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);
    // add to cache
    g_aCacheZeta1.addToCache (m, n, ret);
  }
  return ret;
}
 
int main()
{
  printf ("Reading cache\n");
  g_aCacheZeta0.read ("zeta0");
  g_aCacheZeta1.read ("zeta1");
 
  printf ("Calculating\n");
  int m = 1000;
  int n = 1000;
  printf("%f\n",zeta_0(m,n));
  printf("%f\n",zeta_1(m,n));
 
  // print cache stats
  printf ("Cache hits zeta_0:   %lu\n", g_aCacheZeta0.getHits ());
  printf ("Cache misses zeta_0: %lu\n", g_aCacheZeta0.getMisses ());
  printf ("Cache hits zeta_1:   %lu\n", g_aCacheZeta1.getHits ());
  printf ("Cache misses zeta_1: %lu\n", g_aCacheZeta1.getMisses ());
 
  printf ("Writing cache\n");
  g_aCacheZeta0.write ("zeta0");
  g_aCacheZeta1.write ("zeta1");
  printf ("Cleaning up\n");
  return 0;
}