在 numpy 中向量化贪婪赋值

Question

下面的算法以贪婪的方式从多对多关系中提取一对一关系，逐步排除用过的项目。有没有办法用 numpy 向量化这个算法？

# The relation [(x0, y0), (x1, y1), ...] is parametrized as
# left_items = [x0, x1, ...]
# right_items = [y0, y1, ...]
def compute_greedy_assignment(
    left_items: List[int], 
    right_items: List[int],
) -> Tuple[List[int], List[int]]:
    left_selected = []
    right_selected = []
    for left, right in zip(left_items, right_items):
        if not left in left_selected and not right in right_selected:
            left_selected.append(left)
            right_selected.append(right)
    return left_selected, right_selected

Answer 1

In [313]: compute_greedy_assignment([1,2,3],[4,5])
Out[313]: ([1, 2], [4, 5])

zip

已经停在最短列表长度

In [314]: list(zip([1,2,3],[4,5]))
Out[314]: [(1, 4), (2, 5)]

你希望它是“转置”，所以：

In [317]: list(zip(*zip([1,2,3],[4,5])))
Out[317]: [(1, 2), (4, 5)]

另一种方法是切片（对于数组和列表同样有效）：

In [319]: def foo(alist, blist):
     ...:     l = min(len(alist), len(blist))
     ...:     return alist[:l], blist[:l]
     ...:     

In [320]: foo([1,2,3],[4,5])
Out[320]: ([1, 2], [4, 5])

Answer 2

我认为

np.unique(.., return_idx=True)

在这里可能会有帮助。通过将左右索引与奇特的索引相结合，您可以实现在循环中编码的布尔“与”操作：

import numpy as np

left_items = np.array([0, 2, 4, 2, 5])
right_items = np.array([3, 4, 3, 5, 5])

values_left, idx_left = np.unique(left_items, return_index=True)
values_right, idx_right = np.unique(right_items[idx_left], return_index=True)

selected = idx_left[idx_right]
left_selected = left_items[selected]
right_selected = right_items[selected]

print(left_selected, right_selected)

哪个打印

[0 2 5] [3 4 5]

我希望这有帮助！