Очки в круге - производительность

Question

Я изучаю Python, решая CodeWars Katas.Упражнение: «Напишите функцию, которая вычисляет количество точек в круге».Мой код:

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)

Похоже, время выполнения слишком велико (7 секунд для очков (1000), 21 секунда для очков (2000)).Как сделать это более эффективным (избавиться от петель?).

Answer 1

Как насчет:

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

Или не настолько «точен».Смотрим ли мы на круглые точки, квадратные пиксели - внутри линии (и на каких пикселях точно эта линия?), ..?(возможно, используйте n-1?).

Answer 2

Я не мог удержаться, чтобы дать ему шанс.Итак, вот метод, который разбивает круг на центральный квадрат и четыре равных «шапки»:

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

Свернутая версия по сути того же алгоритма:

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)