Plus python efficace pour boucle (3 boucles redondantes) à de grandes valeurs d'itérations

Question

Je suis en train de mettre en œuvre le code suivant:

def foo(n, p): 
    for i in range(1,n): 
     for j in range(1,n): 
      for k in range(1,n): 
       if ((n-j)*i*k)==(j*(n-i)*(n-k)): 
        p=p-11 

Mais n va approcher les valeurs de 10^10, ce qui en grossièrement inefficace. En fait, c'est lent même quand n = 1000.

Existe-t-il un moyen d'accélérer cela en condensant les boucles for, ou peut-être un moyen de le faire sans pour les boucles du tout?

Answer 1

Je vais prendre une approche mathématique par rapport à une approche informatique. Il y a évidemment des problèmes intéressants avec la réduction de ceux pour les boucles, mais l'approche mathématique pourrait vous faire à peu près la même chose avec une petite erreur. Je me demandais s'il y avait une formule fermée pour cette séquence, car elle sera toujours plus rapide que n'importe quelle boucle! Dans le lien OEIS que vous avez fourni, sous la formule, quelqu'un a fourni une partie fonction génératrice « empirique » de

x*(1+5*x+11*x^2+x^3+6*x^4)/(1-x)^3/(1+x)^2 

Je vais à la « empirique » un peu. Mais comme il s'agit d'un rapport de polynômes, il est assez facile d'obtenir une solution fermée si vous lisez comment fonctionnent les fonctions génératrices. Je peux ajouter l'algèbre à ma réponse si cette approche finit par être quelque chose que vous aimez, mais pour l'instant, nous allons couper tout droit à la formule:

def empirical(n): 
    return ((-1)**n * (-1.5*n + 2.5)) + \ 
       (3.0*n**2 - 4.5*n + 3.5) 

Il est très propre et simple. Est-ce exact? Eh bien, j'ai vérifié les 500 premières valeurs. Les deux fonctions alignent généralement parfaitement, mais il y a des moments occasionnels quand empirical surestime la vraie séquence:

correct empirical pct_diff 
1   1  1.0 0.000000 
2   6  6.0 0.000000 
3  19  19.0 0.000000 
4  30  30.0 0.000000 
5  61  61.0 0.000000 
6  78  78.0 0.000000 
7  127  127.0 0.000000 
8  150  150.0 0.000000 
9  217  217.0 0.000000 
10  246  246.0 0.000000 
11  331  331.0 0.000000 
12  366  366.0 0.000000 
13  469  469.0 0.000000 
14  510  510.0 0.000000 
15  625  631.0 0.009600* 
16  678  678.0 0.000000 
17  817  817.0 0.000000 
18  870  870.0 0.000000 
19  1027  1027.0 0.000000 
20  1080  1086.0 0.005556* 
21  1261  1261.0 0.000000 
22  1326  1326.0 0.000000 

Cette différence de temps en temps est presque toujours inférieure à 1%. Maintenant, je ne peux pas garantir que ce modèle va tenir pour n = 10**10 (c.-à-empirique où est presque toujours raison, avec de légères exagérations si souvent) tous, mais il faut vérifier un autre commentaire sur la page OEIS:

Le théorème de Ceva est utilisé pour déduire les régions disparues du nombre naïf. La première déduction est à n = 15 pour n impair et n = 20 pour n pair.

15 et 20 sont les premiers désaccords avec empirical! Donc, il semble que la fonction génératrice empirique est la plupart du temps correcte (le "nombre naïf"?), Mais c'est une limite supérieure dans certains endroits où une déduction doit être faite. Cela entre dans le domaine spécifique du domaine, et je ne connais pas assez le théorème de Ceva pour voir exactement quand et comment faire ces déductions - donc je crains de ne pas pouvoir améliorer cette limite supérieure de forme fermée comme je l'ai au dessus.

Votre question d'origine voulait tester 10 ** 10.Alors maintenant faire int(empirical(10**10)) instantanément:

299999999939999956992 

C'est soit tout à fait correct, ou une limite supérieure qui est très, très proche de la vraie réponse.

Je sais que c'est un peu une solution "alternative", mais j'espère que c'est une diversion informative. C'est comme quand quelqu'un vous demande de trouver le (10 ** 10) numéro de Fibonacci. Vous pouvez faire des boucles, mais si une formule fermée existe, utilisez-la!

Answer 2

Manipulation (n-j)*i*k=j*(n-i)*(n-k). Nous avons que j=n/(((n-i)*(n-k))/(i*k) + 1) et j doit être un entier compris entre 1 et n-1, donc:

def foo(n, p): 
    for i in range(1,n): 
     for k in range(1,n): 
      j=n/(((n-i)*(n-k))/(i*k) + 1) 
      if n%(((n-i)*(n-k))/(i*k) + 1) == 0 and j > 0 and j < n: 
       p=p-11 

Ceci réduit la complexité de O (n³) à O (n²)