圈内点 - 表现

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秒（2000））。如何提高效率（摆脱循环？）。

Answer 1

我忍不住试了一下。所以这里有一个方法将圆圈分成一个中心方块和四个相等的“帽子”：

[[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是从预先计算的正方形从右到左取得，直到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)

Answer 2

怎么样：

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

或者那不够“精确”。我们是在观察圆点，方形像素 - 在线内（以及该线的确切像素是什么？），...？ （也许使用n-1？）。