Le coefficient binomial C ++ est trop lent

Vous calculez plusieurs fois des valeurs binomiales. Une solution rapide est la mémorisation.

Non testé:

int binom(int n, int k);

int binom_mem(int n, int k)
{
    static std::map<std::pair<int, int>, std::optional<int>> lookup_table;
    auto const input = std::pair{n,k};
    if (lookup_table[input].has_value() == false) {
        lookup_table[input] = binom(n, k);
    }
    return lookup_table[input];
}

int binom(int n, int k)
{
    double sum;

    if (n == 0 || k == 0){
        sum = 1;
    } else {
        sum = binom_mem(n-1,k-1) + binom_mem(n-1,k);
    }

    if ((n== 1 && k== 0) || (n== 1 && k== 1))
    {
        sum = 1;
    }
    if(k > n)
    {
        sum = 0;
    }

    return sum;
}

Une meilleure solution serait de tourner la récursion tailrec (pas facile avec les doubles récursions) ou mieux encore, de ne pas utiliser la récursivité du tout;)

Je mettrais en cache les résultats de chaque calcul dans une carte. Vous ne pouvez pas créer une carte avec une clé complexe, mais vous pouvez transformer la clé en chaîne.

if(k > n)
{
    return 0;
}

Ensuite, ayez une carte globale:

map<string, double> cachedValues;

Je suppose que le programme perd beaucoup de temps à calculer les résultats qu'il a déjà calculés.

C'est certainement vrai.

À ce sujet, je vous suggère de jeter un œil à Sujet de programmation dynamique .

Il existe une classe de problèmes qui nécessite une complexité d'exécution exponentielle, mais ils peuvent être résolus avec des techniques de programmation dynamique . Cela réduirait la complexité d'exécution à une complexité polynomiale (la plupart du temps, au détriment de la complexité croissante de l'espace).

---

Les approches courantes de la programmation dynamique sont:

• Top-Down (exploitant la mémorisation et la récursivité).
• De bas en haut (itératif).

Ci-dessous, ma solution bottom-up (rapide et compacte):

(n, k) = (n - 1, k - 1) * n / k

Cet algorithme a une complexité d'exécution O (k) et complexité spatiale O (k) . En effet, c'est une solution linéaire.

De plus, cette solution est plus simple et plus rapide que l'approche récursive. Il est très compatible avec le cache du processeur .

Notez également qu'il n'y a pas de dépendance sur n.

J'ai atteint ce résultat exploitation d'opérations mathématiques simples et obtention de la formule suivante:

int BinomialCoefficient(const int n, const int k) {
  std::vector<int> aSolutions(k);
  aSolutions[0] = n - k + 1;

  for (int i = 1; i < k; ++i) {
    aSolutions[i] = aSolutions[i - 1] * (n - k + 1 + i) / (i + 1);
  }

  return aSolutions[k - 1];
}

Quelques références mathématiques sur le coefficient binomial .

---

Remarque

L'algorithme n'a pas vraiment besoin d'une complexité spatiale de O (k) . En effet, la solution à la i-ème étape ne dépend que de (i-1) -th . Par conséquent, il n'est pas nécessaire de stocker toutes les solutions intermédiaires, mais uniquement celle de l'étape précédente. Cela rendrait l'algorithme O (1) en termes de complexité spatiale.

Cependant, je préférerais garder toutes les solutions intermédiaires dans le code de la solution pour mieux montrer le principe derrière le Méthodologie de programmation dynamique .

Voici mon référentiel avec l'algorithme optimisé .