python - 有加速暴力 'tally' 算法的替代方法吗？

Question

如果这是发布此问题的错误位置，请提前道歉。如果有更好的堆栈交换站点，请告诉我。

因此，目前正在开发一种犯罪预测算法，该算法本质上是在城市上铺设一个网格，并预测每个网格条目在未来 30 天内是否会成为热点(至少发生一起袭击犯罪)。

我当前使用的是纳什维尔市，其网格覆盖有 3446 个网格。我有一个网格数据集，其中包含显示网格所需的所有数据、每个网格的 map 坐标以及其周围的相邻网格(底部的邻居、右侧的邻居等)

以下是预测的示例:

在本例中，绿色表示正确的预测。红色表示假阴性，紫色表示机器学习算法的假阳性。

为了训练我的神经网络，我使用了如下所示的功能集:

这里的 Hotspot 是目标值(1 和 0 之一)。周、月、年是从去年提取的犯罪事件的犯罪统计(犯罪发生在上周、上个月和去年)。我的问题是创建这些功能集需要大量时间(脚本需要 6 个小时以上)

#Loop through each grid in the dataset
for grid_index, grid_row in grid.iterrows():
    print("On grid number: ", grid_row['id'])
    near=0
    #Loop through all of the crimes 
    for crime_index, crime_row in crime.iterrows():

        #Parse out the month, day, and year
        date = crime_row['Incident Occurred']
        date_pars = date.split('/')
        month = int(date_pars[0])
        day= int(date_pars[1])
        year =int(date_pars[2].split(' ')[0])

        if grid_row['top '] == crime_row['grid']:
            near +=1
        if grid_row['bottom '] == crime_row['grid']:
            near +=1
        if grid_row['left '] == crime_row['grid']:
            near +=1
        if grid_row['right '] == crime_row['grid']:
            near +=1
        if grid_row['topleft'] == crime_row['grid']:
            near +=1
        if grid_row['topright'] == crime_row['grid']:
            near +=1
        if grid_row['bottomright'] == crime_row['grid']:
            near +=1
        if grid_row['bottomleft'] == crime_row['grid']:
            near +=1

        if month == 12 and grid_row['id'] == crime_row['grid']:
            countMonth = countMonth+1
        if day >= 25 and month == 12 and grid_row['id'] == crime_row['grid']:
            countWeek = countWeek + 1

        if  year == 2017 and grid_row['id'] == crime_row['grid']:
            countYear=countYear+1

    #Update the output for the specific grid
    output = output.append({'Grid': grid_row['id'], 'Hotspot': 0, 'week': countWeek, 'month': 
    countMonth, 'year': countYear,'near': near}, ignore_index=True)
    countMonth = 0
    countYear = 0
    countWeek = 0

现在，这段代码循环遍历每个网格(总共 3446 个)，并在每个网格内循环遍历每个犯罪(大约 18,000 个)，计算计数并将其附加到 pandas 数据帧中...3446*18000 约为 6200 万次计算创建此数据集。我觉得这不会花太长时间，但比理想情况要花更长的时间。

关于如何有效加快速度有什么想法吗？我需要在过去三年的每个月运行这个算法，所以每次运行 36 次超过 5 小时对于我的时间限制来说太长了。

提前感谢您提供任何见解。

编辑:为了澄清“grid_row”是网格 CSV 文件中的每条记录，我在上面的列中发布了该文件(每个网格和相邻网格的位置)，“crime_row”是去年发生的每个犯罪事件:

Answer 1

你做事的方式可以简化为

forall grid
  forall crimes
    if crime.cell == grid.cell
      do something

复杂度为O(|grid| * |crimes|)

如果你有 3k 犯罪和 5k 网格，则需要 15e6 次迭代

更好的方法是迭代犯罪并将其中任何犯罪推送到其关联的网格，将具有相同 grid_index 的所有犯罪堆叠到...相同的位置

gridIdxToCrimes = {} // to a grid_index you associate all the crimes

for crime_row in crime.iterrows():
  grid_index = crime_row['grid']
  if grid_index not in gridIdxToCrimes:
    gridIdxToCrimes[grid_index] = []
  gridIdxToCrimes[grid_index].push(crime_row)

forall grid_index, grid_row in grid.iterrows():
  topIndex = grid_row['top ']
  if topIndex in gridIdxToCrimes:
    # you get all the crimes above your current grid
    near += count(gridIdxToCrimes[topIndex])

这样你就完成了 O(|crimes|+|grid|) = 5k 次迭代