合并两个重叠列表的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，3，9，8，3，5，4，5，8，3，4，5，8合并为: 1,3,9,8，3,4,5,7,8。为了清晰起见，我突出了重叠部分。

9、1、1、8、7、8、6、7应合并为9、1、1、8、7、8、8、6、7

Answer 1

这其实并不太难。毕竟，从本质上说，您所做的只是检查A的末尾的哪个子字符串与B的哪个子字符串。

def merge(a, b):
    max_offset = len(b)  # can't overlap with greater size than len(b)
    for i in reversed(range(max_offset+1)):
        # checks for equivalence of decreasing sized slices
        if a[-i:] == b[:i]:
            break
    return a + b[i:]

我们可以通过以下操作对您的测试数据进行测试：

test_data = [{'a': [1,3,9,8,3,4,5], 'b': [3,4,5,7,8], 'result': [1,3,9,8,3,4,5,7,8]},
             {'a': [9, 1, 1, 8, 7], 'b': [8, 6, 7], 'result': [9, 1, 1, 8, 7, 8, 6, 7]}]

all(merge(test['a'], test['b']) == test['result'] for test in test_data)

这会贯穿所有可能导致重叠的切片组合，如果找到重叠，则会记住重叠的结果。如果什么都没有找到，它将使用i的最后一个结果，它将始终是0。无论哪种方式，它都返回所有的a加上过去的b[i] (在重叠的情况下，这是不重叠的部分)。在不重叠的情况下，这是一切)

注意，我们可以在角点情况下进行一些优化。例如，这里最糟糕的情况是，它贯穿整个列表，而没有找到任何解决方案。您可以在开始时添加一个快速检查，以便在最坏的情况下短路。

def merge(a, b):
    if a[-1] not in b:
        return a + b
    ...

事实上，您可以将该解决方案再向前推进一步，并且可能会使您的算法更快。

def merge(a, b):
    while True:
        try:
            idx = b.index(a[-1]) + 1  # leftmost occurrence of a[-1] in b
        except ValueError:  # a[-1] not in b
            return a + b
        if a[-idx:] == b[:idx]:
            return a + b[:idx]

但是，在以下情况下，这可能找不到最长的重叠：

a = [1,2,3,4,1,2,3,4]
b = [3,4,1,2,3,4,5,6]
# result should be [1,2,3,4,1,2,3,4,5,6], but
# this algo produces [1,2,3,4,1,2,3,4,1,2,3,4,5,6]

您可以使用rindex而不是index来匹配最长的切片而不是最短的片段，但我不知道这对您的速度有什么影响。这当然是缓慢的，但可能是无关紧要的。你也可以回忆录结果，并返回最短的结果，这可能是一个更好的想法。

def merge(a, b):
    results = []
    while True:
        try:
            idx = b.index(a[-1]) + 1  # leftmost occurrence of a[-1] in b
        except ValueError:  # a[-1] not in b
            results.append(a + b)
            break
        if a[-idx:] == b[:idx]:
            results.append(a + b[:idx])
    return min(results, key=len)

这应该是可行的，因为合并最长的重叠应该产生最短的结果在所有情况下。

Answer 2

您可以尝试以下方法：

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

其思想是，我们检查第一个i元素的b (b[:i])和最后的i元素的a (a[-i:])。我们从i的长度开始到1 (xrange(len(b), 0, -1))，我们以递减的顺序取它，因为我们希望尽可能匹配。我们使用第一个这样的i，使用next，如果找不到它，就使用零值(next(..., 0))。从我们找到i的那一刻起，我们就在a中添加了索引i中的b元素。

Answer 3

有几个简单的优化是可能的。

1. 您不需要从master1开始，因为最长的重叠从master-len开始(加法)
2. 如果向list.index添加调用，则可以避免为每个索引创建子列表和比较列表：

这种方法也使代码非常容易理解(并且更容易通过使用cython或pypy进行优化)：

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

def merge(master, addition):
    first = addition[0]
    n = max(len(master) - len(addition), 1)  # (1)
    while 1:
        try:
            n = master.index(first, n)       # (2)
        except ValueError:
            return master + addition

        if master[-n:] == addition[:n]:
            return master + addition[n:]
        n += 1