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]

我们的想法是,我们检查的第一个i元素b(b[:i]与去年)i的元素a(a[-i:]).我们采用i递减顺序,从长度开始b直到1(xrange(len(b), 0, -1)),因为我们希望尽可能匹配.我们i通过使用第一个这样的next,如果我们没有找到它,我们使用零值(next(..., 0)).从我们发现的那一刻起i,我们就添加a了b索引元素i.

Answer 2

有几种简单的优化是可能的.

1. 你不需要从master [1]开始,因为最长的重叠从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

Answer 3

一个简单的优化不是遍历整个master列表.即,替换while n < len(master)为for n in range(min(len(addition), len(master)))(并且不要n在循环中增加).如果没有匹配,您的当前代码将遍历整个master列表,即使被比较的切片甚至不是相同的长度.

另一个问题是你正在拍摄片段master并addition进行比较,每次创建两个新列表,并不是必需的.此解决方案(受Boyer-Moore启发)不使用切片:

def merge(master, addition):
    overlap_lens = (i + 1 for i, e in enumerate(addition) if e == master[-1])
    for overlap_len in overlap_lens:
        for i in range(overlap_len):
            if master[-overlap_len + i] != addition[i]:
                break
        else:
            return master + addition[overlap_len:]
    return master + addition

这里的想法是生成masterin 的最后一个元素的所有索引addition,并添加1到每个元素.由于有效重叠必须以最后一个元素结尾,因此master只有那些值是可能重叠的长度.然后我们可以检查它们中的每个元素是否也排成一行.

该功能目前假定master长于addition(你可能会得到一个IndexError在master[-overlap_len + i]如果不是).overlap_lens如果您无法保证,请向生成器添加条件.

它也是非贪婪的,即它寻找最小的非空重叠(merge([1, 2, 2], [2, 2, 3])将返回[1, 2, 2, 2, 3]).我认为这就是"在最后可能的有效位置合并"的意思.如果你想要一个贪婪的版本,请反转overlap_lens发电机.

Answer 4

我不提供优化,而是另一种查看问题的方法.对我来说,这似乎是http://en.wikipedia.org/wiki/Longest_common_substring_problem的特例,其中子字符串始终位于列表/字符串的末尾.以下算法是动态编程版本.

def longest_common_substring(s1, s2):
    m = [[0] * (1 + len(s2)) for i in xrange(1 + len(s1))]
    longest, x_longest = 0, 0
    for x in xrange(1, 1 + len(s1)):
        for y in xrange(1, 1 + len(s2)):
            if s1[x - 1] == s2[y - 1]:
                m[x][y] = m[x - 1][y - 1] + 1
                if m[x][y] > longest:
                    longest = m[x][y]
                    x_longest = x
            else:
                m[x][y] = 0
    return x_longest - longest, x_longest

master = [1,3,9,8,3,4,5]
addition = [3,4,5,7,8]
s, e = longest_common_substring(master, addition)
if e - s > 1:
    print master[:s] + addition

master = [9, 1, 1, 8, 7]
addition = [8, 6, 7]
s, e = longest_common_substring(master, addition)
if e - s > 1:
    print master[:s] + addition
else:
    print master + addition

[1, 3, 9, 8, 3, 4, 5, 7, 8]
[9, 1, 1, 8, 7, 8, 6, 7]

Answer 5

这实际上并不是非常困难.毕竟,基本上你所做的只是检查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)

哪个应该起作用,因为合并最长的重叠应该在所有情况下产生最短的结果.