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

- Firnagzen

---

你展示的案例预期输出是什么？ - thefourtheye

@thefourtheye，我已经编辑了期望的输出。 - Firnagzen

列表中只有数字是确保的吗？ :) - Shashank

@ShaShank 不，实际上我在这里使用数字是为了清晰明了。它是字符串和数字的混合体。 - Firnagzen

考虑到重叠部分是主列表的整个尾段，这不应该发生吧？ - Firnagzen

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 的前 i 个元素（b[:i]）与列表 a 的后 i 个元素（a[-i:]）是否匹配。我们按照递减顺序取 i，从 b 的长度开始一直到 1（xrange(len(b), 0, -1)），因为我们想要匹配尽可能多的元素。我们使用 next 来取得第一个这样的 i，如果找不到则使用零值 (next(..., 0))。从找到 i 的时刻起，我们将从索引 i 开始的元素添加到列表 a 中。

- JuniorCompressor

---

@TankorSmash 我不懂Python，但如果你能添加注释，那么它就可以变得可读 :P。 - John Odom

糟糕，这是一团乱麻！不知不觉中，我显然在我的答案中重新实现了这个解决方案，使其更易读。似乎高人们想法相似，JuniorCompressor 也是如此 :) - Adam Smith

@TankorSmash，添加一些中间变量（我的修改）可以通过减少语法树的最大高度来改进它。在我看来，这是最干净的，虽然不是最优算法。 - Paul Draper

Answer 2

有一些简单的优化方法可供选择。

1. 你不需要从master[1]开始，因为最长的重叠部分从master[-len(addition)]开始。

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

- thebjorn

---

他不使用master[1]。 - Neil G

他的迭代从 n = 1 开始，所以除非我弄错了，他开始尝试在 master[1] 找到匹配... - thebjorn

n是从另一侧开始计数的。 - Neil G

Answer 3

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

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

- Adam Smith

---

我选择这个作为答案，因为它提供了额外的清晰度，但是如果要寻找一个非常紧凑而聪明（尽管更难读）的解决方案，请看这里。 - Firnagzen

Answer 4

一项微小的优化是不必遍历整个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

这里的想法是生成master中最后一个元素在addition中的所有索引，并将每个索引加上1。由于有效的重叠必须以master的最后一个元素结束，因此只有这些值才是可能重叠的长度。然后我们可以检查每个长度是否与其前面的元素对齐。

该函数目前假设master比addition长（如果不是，则可能会在master[-overlap_len + i]处得到IndexError）。如果无法保证，请向overlap_lens生成器添加条件。

它也是非贪婪的，即它寻找最小的非空重叠（merge([1, 2, 2], [2, 2, 3])将返回[1, 2, 2, 2, 3]）。我认为这就是你所说的“在最后可能的有效位置合并”的意思。如果您想要贪婪版本，请反转overlap_lens生成器。

- dddsnn

Answer 5

我不提供优化，但可以提供另一种解决问题的方式。在我看来，这似乎是最长公共子串问题的一个特殊情况，其中子串总是在列表/字符串的末尾。以下算法是动态规划版本。

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]

- Ale

---

但他正在寻找最短的，而不是最长的。 - Neil G

@NeilG 看起来实际上是最长的。请参见https://dev59.com/1l0a5IYBdhLWcg3wsKUK?noredirect=1#comment48260683_30055830。 - Veedrac

@Veedrac然后他自相矛盾：“我想合并这些列表，以便保留现有的顺序，并在最后可能的有效位置进行合并”... - Neil G

Answer 6

首先，为了更加清晰明了，您可以用for循环来替换while循环：

def merge(master, addition):
    for n in xrange(1, len(master)):
        if master[-n:] == addition[:n]:
            return master + addition[n:]
    return master + addition

然后，您不必比较所有可能的片段，而只需比较那些master切片以addition的第一个元素开头的片段：

def merge(master, addition):
    indices = [len(master) - i for i, x in enumerate(master) if x == addition[0]]
    for n in indices:
        if master[-n:] == addition[:n]:
            return master + addition[n:]
    return master + addition

因此，不要像这样比较切片：

1234123141234
            3579
           3579
          3579
         3579
        3579
       3579
      3579
     3579
    3579
   3579
  3579
 3579
3579

你只是在进行这些比较：

1234123141234
  |   |    |
  |   |    3579
  |   3579
  3579

这会加速程序的程度取决于数据的特性：列表中重复元素越少，效果越好。

你还可以为addition生成一个索引列表，使其自身的切片总是以master的最后一个元素结束，从而进一步限制比较次数。

- Roberto Bonvallet

---

切片比较无论如何都会提前退出，因此这不是一种优化。 - Neil G

@NeilG，你仍然需要进行一次切片操作，这是O(n)的。 - Veedrac

如果您使用numpy数组而不是列表，则可以获得对现有数组的视图。 - Roberto Bonvallet

Answer 7

基于https://dev59.com/1l0a5IYBdhLWcg3wsKUK#30056066：

def join_two_lists(a, b):
  index = 0
  for i in xrange(len(b), 0, -1):
    #if everything from start to ith of b is the 
    #same from the end of a at ith append the result
    if b[:i] == a[-i:]:
        index = i
        break

  return a + b[index:]

- TankorSmash

Answer 8

你需要的是像 Needleman-Wunsch 这样的序列比对算法。

Needleman-Wunsch 是一种基于动态规划的全局序列比对算法： 我在 Python 中找到了这个很好的实现，可以合并任意对象序列： https://github.com/ajnisbet/paired

import paired

seq_1 = 'The quick brown fox jumped over the lazy dog'.split(' ')
seq_2 = 'The brown fox leaped over the lazy dog'.split(' ')
alignment = paired.align(seq_1, seq_2)

print(alignment)
# [(0, 0), (1, None), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5), (7, 6), (8, 7)]

for i_1, i_2 in alignment:
    print((seq_1[i_1] if i_1 is not None else '').ljust(15), end='')
    print(seq_2[i_2] if i_2 is not None else '')

# The            The
# quick          
# brown          brown
# fox            fox
# jumped         leaped
# over           over
# the            the
# lazy           lazy
# dog            dog

- Hoeze

Answer 9

所有上述解决方案在合并任务中使用for / while循环方面非常相似。我首先尝试了@JuniorCompressor和@TankorSmash的解决方案，但这些解决方案对于合并两个大规模列表（例如具有数百万个元素的列表）来说速度太慢了。

我发现使用pandas连接具有大尺寸的列表更加高效：

import pandas as pd, numpy as np

trainCompIdMaps = pd.DataFrame( { "compoundId": np.random.permutation( range(800) )[0:80], "partition": np.repeat( "train", 80).tolist()} )

testCompIdMaps = pd.DataFrame( {"compoundId": np.random.permutation( range(800) )[0:20], "partition": np.repeat( "test", 20).tolist()} )

# row-wise concatenation for two pandas
compoundIdMaps = pd.concat([trainCompIdMaps, testCompIdMaps], axis=0)

mergedCompIds = np.array(compoundIdMaps["compoundId"])

- Good Will