如何有效地离开外部联接两个排序列表

Question

我有两个已经排序的列表。我需要离开外面加入他们。以下代码可完成工作：

left_sorted_list = [1, 2, 3, 4, 5]
right_sorted_list = [[2, 21], [4, 45], [6, 67]]
right_dict = {r[0]: r[1] for r in right_sorted_list}
left_outer_join = [[l, right_dict[l] if l in right_dict.keys() else None]
                   for l in left_sorted_list]
print(left_outer_join)
[[1, None], [2, 21], [3, None], [4, 45], [5, None]]

但是，我不确定这种方法是否非常有效。有没有一种更有效的方法来利用正确的列表已经排序的事实，而无需编写循环？

编辑：我加入的键在左右列表中都是唯一的。

Answer 1

这个答案直接取决于米吉尔森对OP问题所做的两条评论。

这并不比你所拥有的更高效，但它更Pythonic。

left_sorted_list = [1, 2, 3, 4, 5]
right_sorted_list = [[2, 21], [4, 45]]

right_dict = dict(right_sorted_list)
left_outer_join = [[l, right_dict.get(l)] for l in left_sorted_list] 

就时间复杂度而言，left_sorted_list和right_sorted_list都迭代一次，因此它们都是 O(N)。对于字典查找，平均查找时间为 O(1)，因此查找所有键也是 O(N) 。你的时间复杂度不会比你已经拥有的好很多。

Answer 2

这是一种高效内存的版本，可一次生成一个键/值对：

def left_outer_join(keys, pairs, default=None):
    right = iter(pairs)
    right_key = float('-inf') # sentinel: any left key must be larger than it
    for left_key in keys:
        if left_key == right_key: # *keys* and *right* are in sync
            value = right_value  # from previous iteration
        elif left_key < right_key: # *keys* is behind *right*
            value = default
        else: # left_key > right_key: *keys* is ahead of *right*
            for right_key, right_value in right: # catch up with *keys*
                if left_key <= right_key: # drop while left_key > right_key
                    break
            value = right_value if left_key == right_key else default
        yield left_key, value

它是O(n+m)单遍算法。

例：

left_sorted_list = [1, 2, 3, 4, 5]
right_sorted_list = [[2, 21], [4, 45], [6, 67]]
print(list(left_outer_join(left_sorted_list, right_sorted_list)))
# -> [(1, None), (2, 21), (3, None), (4, 45), (5, None)]

keys并且pairs可以分别heapq.merge()是键和键/值对的无限排序的迭代器（例如由函数产生的迭代器）。