什么是半径为 x 的圆中整数坐标的更快解决方案 [英] What is a faster solution for integer coordinates in circle of radius x

问题描述

我正在尝试创建一种方法，该方法返回半径为 rad 的圆内的整数坐标计数，但我认为我当前的解决方案太慢了.你会推荐什么来更好地实施?我想自己编写解决方案，因为我仍然是初学者.

I'm trying to create a method that returns the count of integer coordinates within a circle of radius rad but I believe my current solution is too slow. What would you recommend for a better implementation? I'd like to code the solution myself as I'm still a beginner.

这是我目前的解决方案:

This is my current solution:

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

推荐答案

与使用大量不必要的循环相比，绝对可以更快地完成任务.
为什么不在同一个循环中构建"和检查"?
此外，您可以在 itertools 的 product 的帮助下将其(几乎)设为单行:

Things can definitely be made faster than using lots of unnecessary loops.
Why not "build" and "check" in the same loop?
Also, you can make this (almost) a one-liner with the help of product from 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

如果有任何用处，列表推导式给出了实际点数.祝你好运！

The list comprehension gives the actual points, if that's of any use. Good luck!

一些必要的解释:
x 只是一个介于(包括)-rad 和 rad 之间的整数列表.
product(x, x) 是 x 与其自身的笛卡尔积，因此由两个坐标定义的正方形中的所有点都在 -rad 和 rad.
列表推导式仅返回与原点的距离小于或等于 rad 的点.
该函数返回此列表的长度.

Some explanations in case needed:
x is just a list of integers between (and including) -rad and rad.
product(x, x) is the Cartesian product of x and itself, thus all the points in the square defined by both coordinates being between -rad and rad.
The list comprehension returns only points with a distance from the origin smaller or equal to rad.
The function returns the length of this list.

这篇关于什么是半径为 x 的圆中整数坐标的更快解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！