圆圈中的点 - 性能

Question

我正在通过解决 CodeWars Katas 来学习 Python。练习是：“编写一个计算圆中点数的函数”。我的代码：from math import sqrtimport timestart = 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 countprint (points(1000))end = time.time()print(end - start)看起来执行时间太长（点（1000）为 7 秒，点（2000）为 21 秒）。如何提高效率（摆脱循环？）。

Answer 1

怎么样：

def points(n):
    return n * n * PI

或者这还不够“精确”。我们是否正在查看圆点、方形像素 - 线内（以及该线究竟是什么像素？），..？（也许使用n-1？）。

Answer 2

不言自明

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;

}

Answer 3

我忍不住试一试。所以这里有一个方法将圆分成一个中心正方形和四个相等的“大写”：

[[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]]

正如评论中所建议的，我们不检查个别点；相反，我们在顶盖的每一行中找到最外面的点。

为此，我们首先通过对奇数求和来廉价地计算 0 到 N^2 之间的所有平方。

然后我们遍历正方形 0, 1, 4, 9, ...（对应于 x 坐标），同时检测 N^2 - y^2 相交的所有点。y^2's 取自从右到左的预先计算的正方形，直到 x 和 y 相遇。

最后，我们将四个大写字母和中心正方形相加。

代码：

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)

本质上相同算法的 numpy 版本：

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)

和比较的蛮力方法：

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)