Что является более быстрым решением для целочисленных координат в окружности радиуса х

Question

Я пытаюсь создать метод, который возвращает количество целочисленных координат внутри круга радиуса rad, но я считаю, что мое текущее решение слишком медленное.Что бы вы порекомендовали для лучшей реализации?Я бы хотел написать решение самостоятельно, так как я еще новичок.

Это мое текущее решение:

def points(rad):
    possiblePoints = []
    negX = -rad
    negY = -rad
     #creating a list of all possible points from -rad,-rad to rad, rad
    while(negX <= rad):
        while(negY <= rad):
            possiblePoints.append((negX,negY))
            negY += 1
        negY = -rad
        negX += 1

    count = 0
    index=0
    negX = -rad
    negY = -rad
    distance = 0
     #counting the possible points for distances within rad
    for i in possiblePoints:
        for j in range(0,2):
            distance += (possiblePoints[index][j])**2
        distance = distance**(0.5)
        if(distance<=rad):
            count+=1
        distance = 0
        index += 1
    return count

Answer 1

Точка (x, y) находится в радиусе, указанном x ² + y ² ≤r ² .Мы можем вычислить количество координат для фиксированного y -значения как:

n _y = 1 + 2 × ⌊√ (r ² -y ² ) ⌋

Если мы затем нарежем y между 0 и r , и мы считаем каждый n _y для y> 0 дважды, мы получаем общее число, поэтому мы можем вычислить это как:

import numpy as np
from math import floor

def total(radius):
    r0 = floor(radius)
    ys = np.arange(1, r0+1)
    halves = 2 * np.sum(2*np.floor(np.sqrt(radius * radius - ys * ys)) + 1)
    return halves + 1 + 2 * r0

Таким образом, мы рассчитываем для каждого «слоя» количество интегральных координат и удваиваем каждый слой, так как существует «слой» с таким же количеством интегральных координат в противоположном направлении.,Затем мы добавляем число координат с y = 0 , которое равно 1 + 2 × ⌋r⌋ .

Таким образом, вышеприведенное работает в O (r) с r радиусом круга.

Пример вывода:

>>> total(0)
1.0
>>> total(0.1)
1.0
>>> total(1)
5.0
>>> total(1.1)
5.0
>>> total(1.42)
9.0
>>> total(2)
13.0
>>> total(3)
29.0

Более медленная альтернатива в O (r ²) - это создание сетки, а затем массовое сравнение с ней, например:

import numpy as np
from math import floor

def total_slow(radius):
    r0 = floor(radius)
    xs = np.arange(-r0, r0+1)
    ys = xs[:, None]
    return np.sum(xs*xs+ys*ys <= radius*radius)

Вышеприведенное, однако, полезно, если мы хотим убедиться, что наше решение работает.Например:

>>> total_slow(0)
1
>>> total_slow(1)
5
>>> total_slow(2)
13
>>> total_slow(3)
29

дает те же результаты, но мы можем использовать это, чтобы убедиться, что он всегда дает один и тот же результат для большого числа радиусов, например:

>>> [total(r) == total_slow(r) for r in np.arange(0, 10, 0.03)]
[True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True, True]

Таким образом, это означает, что мы убедились, что оба сгенерировали один и тот же результат для 0, 0.03, 0.06 и т. Д. До 10.Вышеприведенное, конечно, не является формальным доказательством правильности, но оно дает нам некоторые эмпирических свидетельств.

Производительность

Мы можем проверить производительность с помощью timeitмодуль, и мы проверили алгоритмы с тремя радиусами, каждый эксперимент был повторен 10'000 раз:

>>> timeit(partial(total, 1.23), number=10000)
0.11901686200144468
>>> timeit(partial(total, 12.3), number=10000)
0.1255619800031127
>>> timeit(partial(total, 123), number=10000)
0.1318465179974737

>>> timeit(partial(total_slow, 1.23), number=10000)
0.11859546599953319
>>> timeit(partial(total_slow, 12.3), number=10000)
0.15540562200112618
>>> timeit(partial(total_slow, 123), number=10000)
1.3335393390007084

>>> timeit(partial(total_slow, 1.23), number=10000)
0.11859546599953319
>>> timeit(partial(total_slow, 12.3), number=10000)
0.15540562200112618
>>> timeit(partial(total_slow, 123), number=10000)
1.3335393390007084

>>> timeit(partial(points, 1), number=10000)
0.1152820099996461
>>> timeit(partial(points, 12), number=10000)
3.7115225509987795
>>> timeit(partial(points, 123), number=10000)
433.3227958699972

С points метод @ ShlomiF , мы здесь используем целые числа, поскольку для радиуса с числом с плавающей запятой, этот метод будет давать неверные результаты.

Таким образом, мы получаем следующую таблицу:

radius   total    total_slow    points
1.23     0.119         0.119     0.115*
12.3     0.125         0.155     3.711*
123.     0.131         1.334   433.323*

* with integral radiuses

Это ожидаемое поведение, если принять сложность временисчет: в конечном итоге линейный подход превзойдет квадратичный подход.

Answer 2

• Для более быстрой, та же логика, но быстрое решение с клочками:

  def count_in (radius): r = радиус + 1 X, Y = np.mgrid [-r: r, -r: r] return (X 2 + Y 2 <= радиус ** 2) .sum () </p>

Вы ускорите свой алгоритм на ~ x30в общем-то.Подробное объяснение позже.

• Для алгоритма я предлагаю вам лучший способ:

Просто следуйте синей линии, оценивая розовую область,Веселитесь.

Пояснения к радиусу = 3:

In [203]: X
Out[203]: 
array([[-4, -4, -4, -4, -4, -4, -4, -4],
       [-3, -3, -3, -3, -3, -3, -3, -3],
       [-2, -2, -2, -2, -2, -2, -2, -2],
       [-1, -1, -1, -1, -1, -1, -1, -1],
       [ 0,  0,  0,  0,  0,  0,  0,  0],
       [ 1,  1,  1,  1,  1,  1,  1,  1],
       [ 2,  2,  2,  2,  2,  2,  2,  2],
       [ 3,  3,  3,  3,  3,  3,  3,  3]])

In [204]: Y
Out[204]: 
array([[-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3],
       [-4, -3, -2, -1,  0,  1,  2,  3]])

In [205]: X*X+Y*Y
Out[205]: 
array([[32, 25, 20, 17, 16, 17, 20, 25],
       [25, 18, 13, 10,  9, 10, 13, 18],
       [20, 13,  8,  5,  4,  5,  8, 13],
       [17, 10,  5,  2,  1,  2,  5, 10],
       [16,  9,  4,  1,  0,  1,  4,  9],
       [17, 10,  5,  2,  1,  2,  5, 10],
       [20, 13,  8,  5,  4,  5,  8, 13],
       [25, 18, 13, 10,  9, 10, 13, 18]])

И наконец:

In [207]: (X**2 + Y**2 <= 3**2)
Out[207]: 
array([[False, False, False, False, False, False, False, False],
       [False, False, False, False,  True, False, False, False],
       [False, False,  True,  True,  True,  True,  True, False],
       [False, False,  True,  True,  True,  True,  True, False],
       [False,  True,  True,  True,  True,  True,  True,  True],
       [False, False,  True,  True,  True,  True,  True, False],
       [False, False,  True,  True,  True,  True,  True, False],
       [False, False, False, False,  True, False, False, False]], dtype=bool)

In [208]: (X**2 + Y**2 <= 3**2).sum() # True is one
Out[208]: 29

Answer 3

Вещи, безусловно, можно сделать быстрее, чем с помощью большого количества ненужных циклов.
Почему бы не "собрать" и "проверить" в одном цикле?
Кроме того, вы можете сделать это (почти) однострочным с помощьюсправка product от itertools:

import numpy as np
from itertools import product

def points(rad):
    x = np.arange(-rad, rad + 1)
    return len([(p1, p2) for p1, p2 in product(x, x) if p1 ** 2 + p2 ** 2 <= rad ** 2])

# Examples    
print(points(5))
>> 81
print(points(1))
>> 5
print(points(2))
>> 13

Понимание списка дает фактические баллы, если они используются.Удачи!

---

Некоторые пояснения в случае необходимости:
x - это просто список целых чисел между (и включающими) -rad и rad.
product(x, x)декартово произведение х и самого себя, таким образом, все точки в квадрате, определяемые обеими координатами, находятся между -rad и rad.
Понимание списка возвращает только точки с расстоянием от начала координат, меньшим или равным rad.
Функция возвращает длину этого списка.