如何匹配两个长度不等的numpy数组？

Question

我有两个一维的numpy数组，它们的长度不一样。我想把那些彼此接近的元素配对，比如说配成（array1的元素，array2的元素）。我们来看一个例子：

    a = [1,2,3,8,20,23]
    b = [1,2,3,5,7,21,35]

期望的结果是：

    [(1,1), 
    (2,2), 
    (3,3), 
    (8,7),
    (20,21),
    (23,25)]

需要注意的是，数字5是单独留下的。虽然用循环可以很容易地做到这一点，但我的数组非常大。我考虑过使用最近邻算法，但觉得这就像用大炮打麻雀一样。

有没有人能给我推荐一个优雅的解决方案呢？

非常感谢。

Answer 1

我觉得可以这样做：

1. 创建两个新的结构化数组，里面有一个第二个索引，用0或1来表示这个值属于哪个数组，也就是它的“键”。
2. 把这两个数组合并在一起。
3. 按照第一个字段（也就是值）对合并后的数组进行排序。
4. 使用两个栈：遍历这个数组，把键为1的元素放到左边的栈里，当遇到键为0的元素时，就把它们放到右边的栈里。当你遇到第二个键为0的元素时，检查第一个键为0的元素，看看左边和右边的栈的顶部和底部，取出离它最近的值（可能是距离最小的），然后交换栈，继续这个过程。

排序应该是最慢的步骤，而两个栈的最大总空间是n或m。

Answer 2

你觉得用 Needleman-Wunsch 算法怎么样呢？ :)

这里的评分矩阵会很简单，因为两个数字之间的“距离”就是它们的差值。

不过，这样做可能就像用坦克去打麻雀一样……

Answer 3

你可以使用内置的map函数来把一个执行特定操作的函数变得更高效。比如说：

ar1 = np.array([1,2,3,8,20,23])
ar2 = np.array([1,2,3,5,7,21,35])
def closest(ar1, ar2, iter):
    x = np.abs(ar1[iter] - ar2)
    index = np.where(x==x.min())
    value = ar2[index]
    return value

def find(x):
    return closest(ar1, ar2, x)
c = np.array(map(find, range(ar1.shape[0])))

在上面的例子中，看起来你想在配对后排除某些值。如果是这样的话，你可以在第一个函数里加入一个移除的过程，但要非常小心数组1的排序方式：

 def closest(ar1, ar2, iter):
    x = np.abs(ar1[iter] - ar2)
    index = np.where(x==x.min())
    value = ar2[index]
    ar2[ar2==value] = -10000000
    return value