圆圈中的点 - 性能

Question

我正在通过解决 CodeWars Katas 来学习 Python。练习是：“编写一个计算圆中点数的函数”。我的代码：

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)

看起来执行时间太长（点（1000）为 7 秒，点（2000）为 21 秒）。如何提高效率（摆脱循环？）。

Answer 1

怎么样：def&nbsp;points(n): &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;n&nbsp;*&nbsp;n&nbsp;*&nbsp;PI或者这还不够“精确”。我们是否正在查看圆点、方形像素 - 线内（以及该线究竟是什么像素？），..？（也许使用n-1？）。

Answer 2

不言自明public static int pointsNumber(int radius) {&nbsp; &nbsp; int quater_updown = radius;&nbsp; &nbsp; //xxxxx&nbsp; &nbsp; for (int i = 1; i <= radius; i++) {&nbsp; &nbsp; &nbsp; &nbsp; quater_updown += sqrt(radius * radius - i * i);&nbsp; &nbsp; }&nbsp; &nbsp; //xxxx.&nbsp; &nbsp; //xxx..&nbsp; &nbsp; //xx...&nbsp; &nbsp; //x....&nbsp; &nbsp; //4 side and a center&nbsp; &nbsp; return 1 + (quater_updown) * 4;}

Answer 3

我忍不住试一试。所以这里有一个方法将圆分成一个中心正方形和四个相等的“大写”：[[0 0&nbsp; &nbsp;0 0 0 0 1 0 0 0 0&nbsp; &nbsp;0 0]&nbsp;[0 0&nbsp; &nbsp;0 1 1 1 1 1 1 1 0&nbsp; &nbsp;0 0]&nbsp;[0 0&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;0 0]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[1 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 1]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[0 1&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;1 0]&nbsp;[0 0&nbsp; &nbsp;1 1 1 1 1 1 1 1 1&nbsp; &nbsp;0 0]&nbsp;[0 0&nbsp; &nbsp;0 1 1 1 1 1 1 1 0&nbsp; &nbsp;0 0]&nbsp;[0 0&nbsp; &nbsp;0 0 0 0 1 0 0 0 0&nbsp; &nbsp;0 0]]正如评论中所建议的，我们不检查个别点；相反，我们在顶盖的每一行中找到最外面的点。为此，我们首先通过对奇数求和来廉价地计算 0 到 N^2 之间的所有平方。然后我们遍历正方形 0, 1, 4, 9, ...（对应于 x 坐标），同时检测 N^2 - y^2 相交的所有点。y^2's 取自从右到左的预先计算的正方形，直到 x 和 y 相遇。最后，我们将四个大写字母和中心正方形相加。代码：from itertools import accumulatedef pic(N):&nbsp; &nbsp; squares = 0, *accumulate(range(1, 2*N+1, 2))&nbsp; &nbsp; N2 = squares[-1]&nbsp; &nbsp; i, j = 0, N&nbsp; &nbsp; cap = 0&nbsp; &nbsp; while 2 * squares[j] > N2:&nbsp; &nbsp; &nbsp; &nbsp; max_x2 = N2 - squares[j]&nbsp; &nbsp; &nbsp; &nbsp; while squares[i] <= max_x2:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i += 1&nbsp; &nbsp; &nbsp; &nbsp; cap += 2*i - 1&nbsp; &nbsp; &nbsp; &nbsp; j -= 1&nbsp; &nbsp; return 4*cap + (2*j+1)*(2*j+1)本质上相同算法的 numpy 版本：import numpy as npdef pic_np(N):&nbsp; &nbsp; odd = np.arange(-1, 2*N+1, 2)&nbsp; &nbsp; odd[0] = 0&nbsp; &nbsp; squares = odd.cumsum()&nbsp; &nbsp; N2 = squares[-1]&nbsp; &nbsp; cut = squares.searchsorted((N2 + 1) // 2)&nbsp; &nbsp; cap = 2 * squares[:cut].searchsorted(N2 - squares[cut:], 'right').sum() - (N-cut+1)&nbsp; &nbsp; return 4*cap + (2*cut-1)*(2*cut-1)和比较的蛮力方法：def brute_force(N, show=True):&nbsp; &nbsp;sq = np.arange(-N, N+1)**2&nbsp; &nbsp;mask = sum(np.ix_(sq, sq)) <= N*N&nbsp; &nbsp;if show and (N <= 10):&nbsp; &nbsp; &nbsp; &nbsp;print(mask.view(np.uint8))&nbsp; &nbsp;return np.count_nonzero(mask)