合并两个重叠列表的Pythonic方法，保留顺序

Question

好的，所以我有两个列表，如下所示:

• 它们可以并且将会有重叠的项目，例如，[1, 2, 3, 4, 5], [4, 5, 6, 7]。
• 重叠中不会有额外的项目，例如，这不会发生:[1, 2, 3, 4, 5], [3.5, 4, 5, 6, 7]
• 这些列表不一定是有序的，也不一定是唯一的。 [9, 1, 1, 8, 7], [8, 6, 7].

我想合并列表以保留现有顺序，并在最后一个可能的有效位置进行合并，并且不会丢失任何数据。此外，第一个列表可能很大。我目前的工作代码是这样的:

master = [1,3,9,8,3,4,5]
addition = [3,4,5,7,8]

def merge(master, addition):
    n = 1
    while n < len(master):
        if master[-n:] == addition[:n]:
            return master + addition[n:]
        n += 1
    return master + addition

我想知道的是 - 有没有更有效的方法来做到这一点？它可以工作，但我对此有点怀疑，因为它可能会在我的应用程序中运行到大型运行时 - 我正在合并大量字符串。

编辑:我希望 [1,3,9,8,3,4,5]，[3,4,5,7,8] 的合并为:[1,3,9,8 ,3,4,5,7,8]。为清楚起见，我突出显示了重叠部分。

[9, 1, 1, 8, 7], [8, 6, 7] 应该合并到 [9, 1, 1, 8, 7, 8, 6, 7]

Answer 1

您可以尝试以下方法:

>>> a = [1, 3, 9, 8, 3, 4, 5]
>>> b = [3, 4, 5, 7, 8]

>>> matches = (i for i in xrange(len(b), 0, -1) if b[:i] == a[-i:])
>>> i = next(matches, 0)
>>> a + b[i:]
[1, 3, 9, 8, 3, 4, 5, 7, 8]

我们的想法是我们检查 b (b[:i]) 的第一个 i 元素和最后一个 i<a (a[-i:]) 的/code> 元素。我们以 i 的降序排列，从 b 的长度开始直到 1 (xrange(len(b), 0, -1))因为我们想尽可能地匹配。我们使用 next 获取第一个这样的 i，如果找不到，我们使用零值 (next(..., 0))。从我们找到 i 的那一刻起，我们将索引 i 中的 b 元素添加到 a。 p>