如何在R中高效实现跨门店列表的距离计算与筛选？

针对你提到的5万行×3万行全量计算效率极低的问题，推荐以下三种高效实现方案，均能大幅减少不必要的计算量：

方案1：Geopandas空间索引（直观且高效） #

利用Geopandas的RTree空间索引，先通过范围查询筛选出候选门店，再精确计算距离，避免全量遍历。

代码示例 #

import geopandas as gpd
import pandas as pd
from shapely.geometry import Point

# 转换为GeoDataFrame（WGS84坐标系）
gdf_a = gpd.GeoDataFrame(
    STORE_LIST_A,
    geometry=gpd.points_from_xy(STORE_LIST_A.LONGITUDE, STORE_LIST_A.LATITUDE),
    crs="EPSG:4326"
)
gdf_b = gpd.GeoDataFrame(
    STORE_LIST_B,
    geometry=gpd.points_from_xy(STORE_LIST_B.LONGITUDE, STORE_LIST_B.LATITUDE),
    crs="EPSG:4326"
)

# 转换为米制坐标系（Web墨卡托，通用且精度满足需求）
gdf_a = gdf_a.to_crs("EPSG:3857")
gdf_b = gdf_b.to_crs("EPSG:3857")

# 为B构建空间索引
b_sindex = gdf_b.sindex

# 存储结果
result = []

for idx, row in gdf_a.iterrows():
    # 生成1000米缓冲区，用空间索引筛选候选门店
    buffer = row.geometry.buffer(1000)
    candidate_indices = list(b_sindex.intersection(buffer.bounds))
    candidates = gdf_b.iloc[candidate_indices]
    
    # 精确计算距离并筛选符合条件的门店
    distances = candidates.distance(row.geometry)
    valid_pairs = candidates[distances <= 1000]
    
    # 整理结果
    for _, b_row in valid_pairs.iterrows():
        result.append({
            "STORE_ID_A": row["STORE_ID"],
            "STORE_ID_B": b_row["STORE_ID"],
            "DISTANCE_M": distances.loc[b_row.name]
        })

final_result = pd.DataFrame(result)

优势 #

空间索引直接缩小计算范围，仅对可能在1000米内的门店对计算距离，实际计算量远低于全量遍历，效率提升显著。

方案2：Scipy KDTree快速近邻搜索 #

通过KDTree实现高维数据的近邻查询，将经纬度转换为球面笛卡尔坐标后，快速找出1000米内的门店。

代码示例 #

import numpy as np
import pandas as pd
from scipy.spatial import KDTree

# 经纬度转弧度
a_lat_rad = np.radians(STORE_LIST_A["LATITUDE"].values)
a_lon_rad = np.radians(STORE_LIST_A["LONGITUDE"].values)
b_lat_rad = np.radians(STORE_LIST_B["LATITUDE"].values)
b_lon_rad = np.radians(STORE_LIST_B["LONGITUDE"].values)

# 转换为球面笛卡尔坐标（地球半径6371000米）
R = 6371000
a_coords = np.column_stack([
    R * np.cos(a_lat_rad) * np.cos(a_lon_rad),
    R * np.cos(a_lat_rad) * np.sin(a_lon_rad),
    R * np.sin(a_lat_rad)
])
b_coords = np.column_stack([
    R * np.cos(b_lat_rad) * np.cos(b_lon_rad),
    R * np.cos(b_lat_rad) * np.sin(b_lon_rad),
    R * np.sin(b_lat_rad)
])

# 构建KDTree并查询
tree = KDTree(b_coords)
distances, indices = tree.query(a_coords, k=None, distance_upper_bound=1000)

# 整理结果
result = []
for i, (dist_list, idx_list) in enumerate(zip(distances, indices)):
    store_a = STORE_LIST_A.iloc[i]["STORE_ID"]
    # 过滤超出范围的结果（距离为inf）
    valid_mask = dist_list != np.inf
    valid_dists = dist_list[valid_mask]
    valid_indices = idx_list[valid_mask]
    
    for dist, idx in zip(valid_dists, valid_indices):
        result.append({
            "STORE_ID_A": store_a,
            "STORE_ID_B": STORE_LIST_B.iloc[idx]["STORE_ID"],
            "DISTANCE_M": dist
        })

final_result = pd.DataFrame(result)

优势 #

KDTree的查询时间复杂度为O(n log m)，远低于嵌套循环的O(n*m)，适合超大规模数据集的近邻搜索。

方案3：向量化Haversine分块计算 #

如果无法使用空间库，可通过Numpy向量化实现Haversine公式，分块处理避免内存溢出。

代码示例 #

import numpy as np
import pandas as pd

def haversine(lat1, lon1, lat2, lon2):
    # 计算两点间Haversine距离（单位：米）
    R = 6371000
    lat1_rad = np.radians(lat1)
    lon1_rad = np.radians(lon1)
    lat2_rad = np.radians(lat2)
    lon2_rad = np.radians(lon2)
    
    dlat = lat2_rad - lat1_rad
    dlon = lon2_rad - lon1_rad
    
    a = np.sin(dlat/2)**2 + np.cos(lat1_rad) * np.cos(lat2_rad) * np.sin(dlon/2)**2
    c = 2 * np.arctan2(np.sqrt(a), np.sqrt(1-a))
    return R * c

# 分块处理（每次处理1000行A数据，避免内存溢出）
block_size = 1000
result = []

for i in range(0, len(STORE_LIST_A), block_size):
    a_block = STORE_LIST_A.iloc[i:i+block_size]
    # 向量化计算当前块与所有B门店的距离矩阵
    lat1 = a_block["LATITUDE"].values[:, np.newaxis]
    lon1 = a_block["LONGITUDE"].values[:, np.newaxis]
    lat2 = STORE_LIST_B["LATITUDE"].values
    lon2 = STORE_LIST_B["LONGITUDE"].values
    
    dist_matrix = haversine(lat1, lon1, lat2, lon2)
    # 找出距离<=1000米的门店对位置
    rows, cols = np.where(dist_matrix <= 1000)
    
    # 整理结果
    for row, col in zip(rows, cols):
        result.append({
            "STORE_ID_A": a_block.iloc[row]["STORE_ID"],
            "STORE_ID_B": STORE_LIST_B.iloc[col]["STORE_ID"],
            "DISTANCE_M": dist_matrix[row, col]
        })

final_result = pd.DataFrame(result)

优势 #

向量化计算比循环快数倍，分块处理解决了全量距离矩阵的内存占用问题，适合无空间库的场景。

内容的提问来源于stack exchange，提问作者avishkar683