时间戳

首页 > 解决方案 > 我怎样才能加快这种远程计算算法？

python - 我怎样才能加快这种远程计算算法？

问题描述

我正在用 Python 构建一个程序，该程序加载我所在国家/地区所有地址的地理位置，然后通过考虑每个地址与所有其他地址的距离来计算每个地址的“远程”值。由于我国有 3-5 百万个地址，我最终需要运行 3-5 百万次计算索引的算法迭代。

我已经采取了一些措施来缩短运行时间，包括：

通过 5000 个地址的列表仍然需要 23 秒，这意味着我预计 3-5 百万的完整数据集需要 24 小时以上的运行时间。

所以我的问题是：为了节省时间，我的算法的哪些部分应该改进？对您来说，什么是缓慢、冗余或低效的代码？例如，我对 JSON 和 numPy 的使用是否有意义？简化“距离”函数会有很大帮助吗？或者我会通过全力以赴并使用 Python 之外的另一种语言来获得显着优势吗？

任何建议将不胜感激。我是一个新手程序员，所以很容易出现我不知道的问题。

这是代码。它目前正在处理一个有限的数据集（一个小岛），约占整个数据集的 0.1%。该算法从第 30 行开始（#Main 循环）：

import json
import math
import numpy as np

RADII = [888, 1480, 2368, 3848, 6216, 10064, 16280]
R = 6371000
remoteness = []

db = SQL("sqlite:///samsozones.db")

def main():
    with open("samso.json", "r") as json_data:
        data = json.load(json_data)
        
    rows = db.execute("SELECT * FROM zones")
    
    #Establish amount of zones with addresses in them
    ZONES = len(rows)
    
    #Initialize matrix with location of the center of each zone and the population of the zone 
    zonematrix = np.zeros((ZONES, 3), dtype="float")
    for i, row in enumerate(rows):
        zonematrix[i,:] = row["x"], row["y"], row["population"]

    #Initialize matrix with distance from current address to centers of each zone and the population of the zone (will be filled out for each address in the main loop)
    distances = np.zeros((ZONES, 2), dtype="float")

    #Main loop (calculate remoteness index for each address)
    for address in data:
        #Reset remoteness index for new address
        index = 0
        
        #Calculate distance from address to each zone center and insert the distances into the distances matrix along with population
        for j in range(ZONES):
            distances[j, 0] = distance(address["x"], address["y"], zonematrix[j, 0], zonematrix[j, 1])
            distances[j, 1] = zonematrix[j, 2]
            
        #Calculate remoteness index
        for radius in RADII:
            #Calculate amount of zone centers within each radius and add up their population
            allwithincircle = distances[distances[:,0] < radius]
            count = len(allwithincircle)
            pop = allwithincircle[:,1].sum()
            
            #Calculate average within-radius zone population
            try:
                factor = pop / count
            except:
                factor = 0

            #Increment remoteness index:
            index += (1 / radius) * factor
            
        remoteness.append((address["betegnelse"], index))


# Haversine function by Deduplicator, adapted from https://stackoverflow.com/questions/27928/calculate-distance-between-two-latitude-longitude-points-haversine-formula
def distance(lat1,lon1,lat2,lon2):
    dLat = deg2rad(lat2-lat1)
    dLon = deg2rad(lon2-lon1)
    a = math.sin(dLat/2) * math.sin(dLat/2) + math.cos(deg2rad(lat1)) * math.cos(deg2rad(lat2)) * math.sin(dLon/2) * math.sin(dLon/2)
    c = 2 * math.atan2(math.sqrt(a), math.sqrt(1-a))
    d = R * c
    return d;

def deg2rad(deg):
    return deg * (math.pi / 180)

if __name__ == "__main__":
    main()
    
    
# Running time (N = 5070): 23 seconds
# Results quite reasonable
# Scales more or less linearly```

标签： pythonalgorithmnumpyperformancegeospatial

解决方案

我可以推荐一些潜在的加速：

  1. 不要使用 Haversine 来计算您的距离。为您所在的国家/地区找到一个好的本地投影（您没有说您在哪里，所以我不能）并将您的数据重新投影到该 CRS 中，这将允许您使用计算速度更快的简单欧几里得距离（尤其是如果您在距离的平方工作以节省一堆平方根）。

  2. 我会避免计算与所有可能区域的距离，方法是将计算转换为人口的栅格表面，然后计算每个像元的距离，然后查看该栅格上的地址点。如果我街道上的一所房子很偏僻，那么我不需要查找其余的房子！例如，我会看看我的前同事 Carver、Evan 和 Fritz在英国的 Wilderness 属性映射，以作为很好的例子。

推荐阅读