在特定区域内的多维阵列中求和

Question

我正在创建一个游戏，其中机器人遍历2D数组的地图。2D阵列中的每个位置都有许多硬币的"宝藏"。我希望能够将所有元素添加到机器人当前位置的上，向下，右和向左的4个位置(制作"加号"符号(。因此，如果我们有一个数组：

a = [[1, 2, 3, 4]
      [5, 6, 7 ,8]
      [9, 10, 11, 12]
      [13, 14, 15, 16]

如果机器人站在a[0][0](在1位置(上，则总和将返回1+2+3+4+5+9+13。如果他站在a[1][2](7个位置(上，它将返回(7+3)+(8)+(5+6)+(11+15)。但是我希望它只能返回多达4个地方。最后，我想找到机器人的最佳地点。

这是我拥有的代码：

def the_place_to_be(a):
    maximum = 0
    for i in range(len(a)):
        # Looping through columns
        for j in range(len(a[i])):
            # Looping through rows
            sum_at_ij = a[i][j]
            for x in range(i - max_steps_in_direction(a, i, "up"), i):
                sum_at_ij += a[x][j]
            for x in range(j - max_steps_in_direction(a[i], j, "left"), j):
                sum_at_ij += a[i][x]
            for x in range(i, i + max_steps_in_direction(a, i, "down")):
                sum_at_ij += a[x+1][j]
            for x in range(j, j + max_steps_in_direction(a[i], j, "right")):
                sum_at_ij += a[i][x+1]
            if sum_at_ij >= maximum:
                maximum = sum_at_ij
                coordinates = "(" + str(i) + ", " + str(j) + ")"
    return maximum, coordinates

def max_steps_in_direction(a, idx, direction):
    if direction == "up" or direction == "left":
        return min(idx, 4)
    elif direction == "down" or direction == "right":
        return min(len(a) - idx - 1, 4)

这可能具有最严重的时间复杂性。我正在浏览整个数组，然后遍历所有元素，距机器人站在顶部，底部，右侧和左侧的坐标四个位置。

在每个步骤中，我都比我必须计算的值更多。有没有办法减轻这种情况？我当时认为我的变量sum_at_ij可以保存。我基本上是在多列表中的每个列表中移动。在列表中的每个点上，我实际上仅计算一些与先前坐标不同的一些值。因此，再次，说我在坐标a[2][2]或坐标11，当我移至a[2][3]或坐标12时，差异在：

中

sum_at_22：11 7 3 3 15 12 12 10 9

sum_at_23：12 8 4 4 16 11 10 9

我正在计算总共3个新值(顶部和底部的值不同(。如果这是一个8x8矩阵，则新值将是右侧的最高值，底部值和一个新值，左侧值较小。而且，如果我保存了所有值(可能是在某些hashmap中(，那么也许我可以找到一些公式。老实说，我不知道。也许这是一个数学。Stackexchange问题。

有什么想法我如何在(是的，可以(节省计算时间的内存费用？

Answer 1

在求和过程中所做的事情实际上是 形滤波器的卷积。如果您用一个调用Scipy的convolve2d函数替换明确的循环，则可以更快地获得此功能，这将为您提供所有必要的循环，但在python中不做任何必要的循环。

import numpy as np
from scipy.signal import convolve2d
# Your original array:
a = np.asarray([[1, 2, 3, 4],
                [5, 6, 7 ,8],
                [9, 10, 11, 12],
                [13, 14, 15, 16]])
# Building a filter that is essentially a + with arms of length 4
mask = np.zeros((2*4+1, 2*4+1))
mask[4, :] = 1
mask[:, 4] = 1
# Apply that filter to your array
sums = convolve2d(a, mask, mode="same")
# Find the maximum and its position in the sums array:
np.max(sums), np.unravel_index(np.argmax(sums), sums.shape)

最终，总和是给出原始数组中每个位置的求和过程值的数组。您只能找到最大位置及其位置。

虽然复杂性可能并不比您的解决方案更好，但它仍然会快得多，因为Python循环非常慢，而Numpy和Scipy中的许多机械都用C/Fortran编写，从而加快了计算的加速。

将解决方案与100x100阵列的解决方案计时，可加速因子。40在我的机器上(78.7ms vs 2.06mms(。

Answer 2

我建议让与输入矩阵完全相同的 2个辅助矩阵。

现在让第一个为行，第二个为列。行矩阵填充为：

row[i][j] = sum of(a[i][0] + a[i][1] +....a[i][j-1])

您可以随时轻松地进行 o(n*n(，通过行重量顺序遍历输入数组。列矩阵填充为：

column[i][j] = sum of(a[0][j] + a[1][j] +....a[i-1][j])

您也可以通过列以专栏的主要顺序遍历输入数组。

现在，通过一次遍历输入阵列来获得您的位置，总复杂性为：

时间复杂度= o(n*n(

空间复杂性= o(n*n(

Answer 3

使用numpy切片的解决方案 -

import numpy as np

def get_sum(matrix, row, col):
    # Get the sum of 4 numbers to the left
    sum_left_4_numbers = matrix[row, max(col - 4, 0):col].sum()
    # Get the sum of 4 numbers to the right
    sum_right_4_numbers = matrix[row, col:col + 4].sum()
    # Get the sum of 4 numbers above
    sum_top_4_numbers = matrix[max(row - 4, 0):row, col].sum()
    # Get the sum of 4 numbers below
    sum_bottom_4_numbers = matrix[row + 1: row + 4, col].sum()
    return sum_left_4_numbers + sum_right_4_numbers + sum_top_4_numbers + sum_bottom_4_numbers
matrix = np.array([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]])
print get_sum(matrix, 1, 2)
# Output - 55