优化二维数组

Question

我正在用Python 2.7编码。我有两个坐标元组的 2D 数组。

array1 = [[[00_RA,00_DEC] [01_RA,01_DEC] ... [0N_RA,0N_DEC]]
          [[10_RA,10_DEC] [11_RA,11_DEC] ... [1N_RA,1N_DEC]]
          ...
          [[M0_RA,M0_DEC] [M1_RA,M1_DEC] ... [MN_RA,MN_DEC]]]
array2 = [[[00_ra,00_dec] [01_ra,01_dec] ... [0n_ra,0n_dec]]
          [[10_ra,10_dec] [11_ra,11_dec] ... [1n_ra,1n_dec]]
          ...
          [[m0_ra,m0_dec] [m1_ra,m1_dec] ... [mn_ra,mn_dec]]]

我想找到出现在另一个数组中的两个数组条目的坐标。以下代码有效，但运行时间很长，尤其是 M，N，m，n 通常介于 100-1000 之间。

indices = []
for M in xrange(len(array1)):
    array1_row = array1[M]
    for N in xrange(len(array1_row)):
        array1_coord = array1_row[N]
        RA = array1_coord[0]
        DEC = array1_coord[1]
        for m in xrange(len(array2)):
            array2_row = array2[m]
            for n in xrange(len(array2_row)):
                array2_coord = array2_row[n]
                ra = array2_coord[0]
                dec = array2_coord[1]
                if ra == RA and dec == DEC:
                    indices.append((M,N,m,n))

我正在尝试使用列表推导来优化这一点。我认为以下内容应该有效：

indices = [(M,N,m,n) for M in xrange(len(array1)) for N in xrange(len(array1[M])) for m in xrange(len(array2)) for n in xrange(len(array2[m])) if array1[M,N,0] == array2[m,n,0] and array1[M,N,1] == array2[m,n,1]]

不过，即使对于单行，这也需要更长的时间来运行。（我在运行几个小时后停止了它，但在那段时间里它没有抛出错误）。我是否以最佳方式对其进行优化？我该怎么做才能使它更快？

Answer 1

提供的代码的运行时兼容性为 θ（M * N * m * n）。它可以通过使用集合简化为 θ（M * N + m * n）。这可以通过首先散列集合中第一个数组的值，然后检查其他数组的值是否已经存在于集合中来完成。

需要注意的一件事是，您不能在集合中添加列表（？？它们是可变的），因此您必须在添加到集合之前将它们转换为元组。

Answer 2

您需要不同的数据结构才能进行快速查找：dict而不是list。下面是一个示例：

array1 = [
    [[1,2], [1,5]],
    [[3,2], [7,5]],
]
array2 = [
    [[3,2], [9,9]],
    [[1,2], [1,5]],
]
lookup = {}
for r, row in enumerate(array1):
    for c, val in enumerate(row):
        pair = tuple(val)
        lookup[pair] = (r, c)
for r, row in enumerate(array2):
    for c, val in enumerate(row):
        pair = tuple(val)
        if pair in lookup:
            print dict(
                pair = pair, 
                array2_indexes = (r, c),
                array1_indexes = lookup[pair],
            )

输出：

{'array1_indexes': (1, 0), 'pair': (3, 2), 'array2_indexes': (0, 0)}
{'array1_indexes': (0, 0), 'pair': (1, 2), 'array2_indexes': (1, 0)}
{'array1_indexes': (0, 1), 'pair': (1, 5), 'array2_indexes': (1, 1)}