如何高效地左外连接两个已排序的列表

Question

如何高效地左外连接两个已排序的列表

4

我有两个已经排序的列表，我需要进行左外连接。以下代码可以完成此任务：

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

然而，我不确定这种方法是否非常高效。是否有更高效的方式利用右侧列表已经排序的事实，而不需要编写循环?

编辑: 我要连接的键在左右两个列表中都是唯一的。

- A-K

right_dict = dict(right_sorted_list) 也可以起作用... - mgilson

另外，在Python2.x中，“if l in right_dict.keys()”效率相当低下。而“if l in right_dict”则更好。在Python3.x中，除了后者更符合惯用法之外，两者之间可能没有太大的区别。 - mgilson

3

实际上，仔细想想，[[l, right_dict.get(l)] for l in left_sorted_list] 更加清晰明了。 - mgilson

1

就效率而言，假设您采纳了我的建议，您的算法将是O(N) + O(M)（其中N是left_sorted_list的长度，M是right_sorted_list的长度）。无论如何，您都需要遍历两个列表（至少要到达max(left_sorted_list)），因此您不会比现有的情况好多少... - mgilson

2

@StevenRumbalski -- 没问题。我没做，所以应该有人做。最好是得到一个“盗用”的被接受的答案，而不是在这里留下未回答的东西 :-) - mgilson

显示剩余4条评论

3个回答

5

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

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()函数产生的），分别对应于键和键值对。

- jfs

1

+1 只要左右列表中我们连接的键是唯一的，这个方法就可以正常工作。而事实上它们确实是唯一的。我已经编辑了我的问题以明确说明这一点。谢谢！ - A-K

@A-K：我假设问题中的字典是唯一的。itertools.groupby()或其类似函数可以处理重复项。 - jfs

@J.F.Sebastian 对不起...我丢失了第一行...再次道歉。好的，我的解决方案很难阅读。我会把它和错误的评论都删除掉。 - Michele d'Amico

1

我使用元组来表示结果，因此方括号数量较少;)

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

d  = dict(right_sorted_list) # if you have a list of pairs, just pass it to dict()
print [(x, d[x] if x in d else None) for x in left_sorted_list]

## -- End pasted text --
[(1, None), (2, 21), (3, None), (4, 45), (5, None)]

- m.wasowski

1

如果值缺失，默认情况下会返回None，您可以在最后一行中使用.get()，如下所示：print [(x, d.get(x)) for x in left_sorted_list]。 - Akavall

是的，或者 d.setdefault(x, None)；但是这已经在 @Steven Rumbalski 的答案中了，所以不需要重复。 - m.wasowski

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Steven Rumbalski · Accepted Answer

这个答案直接取决于mgilson对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)。你的时间复杂度不会比现在更好。