我怎樣才能加速這種遠程計算演算法？-有解無憂

我正在用 Python 構建一個程式，該程式加載我所在國家/地區所有地址的地理位置，然后通過考慮每個地址與所有其他地址的距離來計算每個地址的“遠程度”值。由于我的國家有 3-5 百萬個地址，我最終需要運行 3-5 百萬次計算索引的演算法迭代。

我已經采取了一些措施來減少運行時間，包括：

嘗試使用 numPy 有效地處理資料
我不是每個地址都著眼于彼此之間的距離，而是將國家劃分為多個區域，每個區域都已經分配了一個人口，然后每個地址只知道這些區域中心中有多少位于每個距離內“RADII”中列舉的值

通過 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```

uj5u.com熱心網友回復：

我可以推薦一些潛在的加速：

不要使用Haversine 來計算你的距離。找到一個很好的區域投影為你的國家（你不說你在哪里，所以我不能），并重新投影資料成CRS，這將允許您使用簡單的歐式距離它們多快計算（特別是如果你在距離的平方中作業以節省一堆平方根）。
我將通過將計算轉換為人口的柵格表面，然后計算每個單元格的遠程度，然后查看該柵格上的地址點來避免計算所有可能區域的距離。如果我街上的一棟房子偏遠，那么我就不需要查找其余的了！例如，我會查看我的前同事 Carver、Evan 和 Fritz在英國的Wilderness 屬性映射作為很好的例子。

uj5u.com熱心網友回復：

我的回答側重于您可以在這些情況下嘗試和實施的計算技巧，而不是特定領域的優化（您絕對應該優先考慮，因為它們通常會給您帶來最大的加速）。為此，我使用cython，它將靜態型別添加到 python 并嘗試將盡可能多的代碼轉換為 c。

calc_dist將一個Nx2numpyN緯度和經度陣列作為輸入，并使用它來計算一個NxN距離陣列，其中坐標對角線上的每個值i,j表示位置i和之間的距離j：

# To test, I recommend using a notebook with the %%cython cell magic
# %load_ext cython
# %%cython
import numpy as np
cimport numpy as np
from libc.math cimport sin, cos, asin, sqrt, pi
import cython

ctypedef np.float64_t dtype_t

@cython.boundscheck(False)
@cython.wraparound(False)
def calc_dist(dtype_t[:, :] coords):

    result = np.zeros((coords.shape[0], coords.shape[0]), dtype=np.float64)
    cdef dtype_t[:, :] result_view = result
    
    cdef int d1, d2
    
    for d1 in range(coords.shape[0]):
        for d2 in range(d1, coords.shape[0]):
            result_view[d1][d2] = haversine(coords[d1][0], coords[d1][1], coords[d2][0], coords[d2][1])
    
    return result


@cython.cdivision(True)
cdef dtype_t haversine(dtype_t lat1, dtype_t lon1, dtype_t lat2, dtype_t lon2):
    """Pure C haversine. Based on https://stackoverflow.com/a/29546836/13145954"""
    cdef dtype_t deg_to_rad = pi/180
    lon1 = lon1 * deg_to_rad
    lon2 = lon2 * deg_to_rad
    lat1 = lat1 * deg_to_rad
    lat2 = lat2 * deg_to_rad
    
    cdef dtype_t dlon = lon2 - lon1
    cdef dtype_t dlat = lat2 - lat1
    
    a = sin(dlat/2.0)**2   cos(lat1) * cos(lat2) * sin(dlon/2.0)**2
    c = 2 * asin(sqrt(a))
    km = 6367 * c
    return km

calc_dist在我的筆記本電腦上，在以下隨機坐標上運行僅需要 780 毫秒，這意味著 500 萬行的運行時間約為 13 分鐘。

coords = np.random.random((5000,2))
coords[:,0] = (coords[:,0]*2-1)*90
coords[:,1] = (coords[:,1]*2-1)*180

注意：代碼必須以塊的形式調整和處理資料，以避免 OOM 錯誤。在完整資料庫上。

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/346074.html

標籤：Python 算法麻木的表现地理空间

上一篇：組concat查詢性能

下一篇：帶有多個iframe的慢速頁面