优化二维数组

Question

我在 Python 2.7 中编码。我有两个坐标元组的二维数组。

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]]

不过运行这需要更长的时间，即使是单行也是如此。（我在运行ning 几个小时后停止了它，但当时它没有抛出错误）。我是否以最好的方式优化它？我该怎么做才能加快速度？

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)}

优化二维数组

Optimizing two-dimensional arrays

python

arrays

optimization

list-comprehension

multidimensional-array