J'apprends python en résolvant CodeWars Katas. L'exercice est: "Ecrire une fonction qui calcule le nombre de points dans le cercle". Mon code:
from math import sqrt
import time
start = time.time()
def points(n):
count=0
for i in range (-n,n+1):
for j in range(-n,n+1):
if abs(i)+abs(j)<=n:
count=count+1
continue
if (sqrt(i**2+j**2))<=n:
count=count+1
return count
print (points(1000))
end = time.time()
print(end - start)
Il semble que le temps d'exécution soit trop long (7 secondes pour les points (1000), 21 secondes pour les points (2000)). Comment rendre cela plus efficace (se débarrasser des boucles?).
3 Réponses :
Je n'ai pas pu résister à lui donner une chance. Voici donc une méthode qui divise le cercle en un carré central et quatre "majuscules" égales:
def brute_force(N, show=True):
sq = np.arange(-N, N+1)**2
mask = sum(np.ix_(sq, sq)) <= N*N
if show and (N <= 10):
print(mask.view(np.uint8))
return np.count_nonzero(mask)
Comme suggéré dans les commentaires, nous ne vérifions pas les points individuels; à la place, nous trouvons le ou les points les plus à l'extérieur de chaque rangée du top cap.
À cette fin, nous calculons d'abord à peu de frais tous les carrés entre 0 et N ^ 2 en additionnant les nombres impairs.
Ensuite, nous parcourons les carrés 0, 1, 4, 9, ... (correspondant aux coordonnées x) en détectant tous les points où N ^ 2 - y ^ 2 est croisé. Les y ^ 2 sont pris à partir des carrés précalculés de droite à gauche jusqu'à ce que x et y se rencontrent.
Enfin, nous additionnons quatre casquettes et le carré central.
Code:
import numpy as np
def pic_np(N):
odd = np.arange(-1, 2*N+1, 2)
odd[0] = 0
squares = odd.cumsum()
N2 = squares[-1]
cut = squares.searchsorted((N2 + 1) // 2)
cap = 2 * squares[:cut].searchsorted(N2 - squares[cut:], 'right').sum() - (N-cut+1)
return 4*cap + (2*cut-1)*(2*cut-1)
Une version numpy du même algorithme:
from itertools import accumulate
def pic(N):
squares = 0, *accumulate(range(1, 2*N+1, 2))
N2 = squares[-1]
i, j = 0, N
cap = 0
while 2 * squares[j] > N2:
max_x2 = N2 - squares[j]
while squares[i] <= max_x2:
i += 1
cap += 2*i - 1
j -= 1
return 4*cap + (2*j+1)*(2*j+1)
Et une méthode de comparaison par force brute:
[[0 0 0 0 0 0 1 0 0 0 0 0 0] [0 0 0 1 1 1 1 1 1 1 0 0 0] [0 0 1 1 1 1 1 1 1 1 1 0 0] [0 1 1 1 1 1 1 1 1 1 1 1 0] [0 1 1 1 1 1 1 1 1 1 1 1 0] [0 1 1 1 1 1 1 1 1 1 1 1 0] [1 1 1 1 1 1 1 1 1 1 1 1 1] [0 1 1 1 1 1 1 1 1 1 1 1 0] [0 1 1 1 1 1 1 1 1 1 1 1 0] [0 1 1 1 1 1 1 1 1 1 1 1 0] [0 0 1 1 1 1 1 1 1 1 1 0 0] [0 0 0 1 1 1 1 1 1 1 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0]]
Que diriez-vous:
def points(n):
return n * n * PI
Ou n'est-ce pas assez «précis». Regardons-nous des points ronds, des pixels carrés - à l'intérieur de la ligne (et sur quels pixels se trouve cette ligne exactement?), ..? (peut n-1 être utiliser n-1 ?).
son explicite
public static int pointsNumber(int radius) {
int quater_updown = radius;
//xxxxx
for (int i = 1; i <= radius; i++) {
quater_updown += sqrt(radius * radius - i * i);
}
//xxxx.
//xxx..
//xx...
//x....
//4 side and a center
return 1 + (quater_updown) * 4;
}
Ceci est plus approprié pour codereview.stackexchange.com
Supprimez la boucle for la plus interne et utilisez à la place une recherche binaire (ou une recherche par interpolation) pour trouver les bords du cercle sur cette ligne, puis comptez les points entre eux.
Pour chaque entier
y, vous pouvez calculer directement la valeur correspondante dexpour un point du cercle. Cela vous donne le nombre de points sur cette ligne. Et un cercle est très symétrique, utilisez-le aussi!Concentrez-vous sur l'accélération du code dans la boucle la plus interne là où cela compte le plus. Vous n'avez pas besoin de ces deux
ifs, éliminez le premier. Lesqrt()dans le second pourrait être éliminé en comparant(i**2 + j**2) <= n*nbien quen*ndoive être calculé une fois et stocké dans une variable locale au début de la fonction car son la valeur ne change jamais.