0

我在 Python 中计算总面积表（ https://en.wikipedia.org/wiki/Summed_area_table ）时遇到问题。最明显的算法涉及在引用已经编写的元素的同时更新列表元素......但是关于就地更新的某些内容似乎让 Python 感到困惑。

这是一些示例代码：

def compute_summed_area_table(image):
    # image is a 2-dimensional array containing ints or floats, with at least 1 element.
    height = len(image)
    width = len(image[0])
    new_image = [([0.0] * width)] * height # Create an empty summed area table
    for row in range(0, height):
        for col in range(0, width):
            if (row > 0) and (col > 0):
                new_image[row][col] = image[row][col] + \
                    new_image[row][col - 1] + new_image[row - 1][col] - \
                    new_image[row - 1][col - 1]
            elif row > 0:
                new_image[row][col] = image[row][col] + new_image[row - 1][col]
            elif col > 0:
                new_image[row][col] = image[row][col] + new_image[row][col - 1]
            else:
                new_image[row][col] = image[row][col]
    # Note that two-pass code gives the same kind of results, e.g.:
    #    for row in range(0, height):
    #        for col in range(0, width):
    #            if col > 0:
    #                new_image[row][col] = image[row][col] + new_image[row][col - 1]
    #            else:
    #                new_image[row][col] = image[row][col]
    #    for row in range(0, height):
    #        for col in range(0, height):
    #            if row > 0:
    #                new_image[row][col] += new_image[row - 1][col]
    return new_image


small_image = [[1, 2, 3, 4, 5], [6, 7, 8, 9, 10], [11, 12, 13, 14, 15], [16, 17, 18, 19, 20], [21, 22, 23, 24, 25]]
small_sat = compute_summed_area_table(small_image)
print(small_sat)

根据我自己的手动计算（可能会出现错误），此测试代码应给出如下内容： [[1, 3, 6, 10, 15], [7, 16, 27, 40, 55], [18, 39, 63, 90, 120], [34, 72, 114, 160, 210], [55, 115, 180, 250, 325]]

相反，它给出： [[55, 61, 68, 76, 85], [55, 61, 68, 76, 85], [55, 61, 68, 76, 85], [55, 61, 68, 76 , 85], [55, 61, 68, 76, 85]]

它显然在每次行迭代期间更新每一行，但我不确定为什么或如何。有谁确切地知道出了什么问题？还有其他方法可以进行就地更新吗？如果没有，您将如何处理？

4

1 回答 1

2

这是因为

new_image = [([0.0] * width)] * height

您不是在创建维度宽度和高度的二维列表，而是在创建高度项列表，并且该列表中的所有元素都指向大小宽度列表（它们都指向同一个列表）。解决这个问题

new_image = [[0.0] * width for _ in range(height)]

考虑这个例子，

a = [[0] * 3] * 2
a[0][0] = 1
print a

a = [[0] * 3 for _ in range(2)]
a[0][0] = 1
print a

输出

[[1, 0, 0], [1, 0, 0]]
[[1, 0, 0], [0, 0, 0]]

在第一种情况下，a[0]并a[1]指向同一个列表。因此，在 0 处更改元素，也会在 1 处更改元素。

于 2013-11-18T13:21:30.240 回答