python - 高效计算数千个坐标对之间的距离

Question

我有一个用 python 打开的目录，其中包含各种对象的大约 70,000 行数据(ra、dec 坐标和对象名称)。我还有另一个 list ，其中包含大约 15,000 个感兴趣的对象，它们也出现在前面提到的目录中。对于这 15,000 个对象中的每一个，我想查看 70,000 个大型列表中是否有任何 other 对象的 ra、dec 坐标在该对象的 10 弧秒内。如果发现这是真的，我只想标记该对象并继续进行下一个。然而，这个过程需要很长时间，因为计算当前感兴趣对象(总共 15,000 个)之间的距离有 70,000 次不同的时间。这需要几天时间!我怎样才能更有效地完成同样的任务？下面是我当前的代码，其中 all_objects 是所有 15,000 个感兴趣的对象名称的列表，catalog 是前面提到的 70,000 个对象的表数据。

from astropy.coordinates import SkyCoord
from astropy import units as u

for obj_name in all_objects:
    obj_ind = list(catalog['NAME']).index(obj_name)
    c1 = SkyCoord(ra=catalog['RA'][obj_ind]*u.deg, dec=catalog['DEC'][obj_ind]*u.deg, frame='fk5')
    for i in range(len(catalog['NAME'])):
        if i != obj_ind:
            # Compute distance between object and other source
            c2 = SkyCoord(ra=catalog['RA'][i]*u.deg, dec=catalog['DEC'][i]*u.deg, frame='fk5')
            sep = c1.separation(c2)
            contamination_flag = False
            if sep.arcsecond <= 10:
                contamination_flag = True
                print('CONTAMINATION FOUND')
                break

Answer 1

1 创建自己的分离函数

一旦您查看了实现并问自己:“我怎样才能让它更快”，这一步就非常容易了

def separation(self, other):
    from . import Angle
    from .angle_utilities import angular_separation # I've put that in the code bellow so it is clearer

    if not self.is_equivalent_frame(other):
        try:
            other = other.transform_to(self, merge_attributes=False)
        except TypeError:
            raise TypeError('Can only get separation to another SkyCoord '
                            'or a coordinate frame with data')

    lon1 = self.spherical.lon
    lat1 = self.spherical.lat
    lon2 = other.spherical.lon
    lat2 = other.spherical.lat

    sdlon = np.sin(lon2 - lon1)
    cdlon = np.cos(lon2 - lon1)
    slat1 = np.sin(lat1)
    slat2 = np.sin(lat2)
    clat1 = np.cos(lat1)
    clat2 = np.cos(lat2)

    num1 = clat2 * sdlon
    num2 = clat1 * slat2 - slat1 * clat2 * cdlon
    denominator = slat1 * slat2 + clat1 * clat2 * cdlon

    return Angle(np.arctan2(np.hypot(num1, num2), denominator), unit=u.degree)

它计算大量余弦和正弦，然后创建一个 Angle 实例并转换为度数，然后再转换为角秒。

你可能不想使用 Angle，也不想一开始的测试和转换，也不想在函数中做导入，如果你需要性能，也不想做那么多变量赋值。

分离函数对我来说感觉有点重，它应该只是取数字并返回一个数字。

2 使用四叉树(需要完全重写代码)

也就是说，让我们看看您的算法的复杂性，它会检查每个元素与其他所有元素，复杂度为 O(n**2)(大 O 表示法)。我们能做得更好吗...

YES 您可以使用四叉树，四叉树的最坏情况复杂度为 O(N)。如果您不熟悉 Big O，那基本上意味着对于 15 000 元素，查找将是 15 000 倍于 1 元素而不是 225 000 000 次(15 000 的平方)...相当不错的改进...Scipy 有一个很棒的四叉树库(我已经一直用我自己的)。