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

Question

好的，所以我有两个列表，例如：

它们可以并且将会有重叠的项目，例如，[1, 2, 3, 4, 5]、[4, 5, 6, 7]。
会有not重叠的额外项目，例如，这not会发生：[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 个元素和 a ([=16] 的最后 i 个元素=]).我们以降序排列 i，从 b 的长度开始，直到 1 (xrange(len(b), 0, -1))，因为我们希望尽可能匹配。我们通过使用 next 获取第一个这样的 i，如果我们没有找到它，我们使用零值 (next(..., 0))。从我们找到 i 的那一刻起，我们将索引 i.

的 b 的元素添加到 a

Answer 2

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

不需要从master[1]开始，因为最长重叠从master[-len(addition)]
如果添加对 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

这里的思路是生成addition中master的最后一个元素的所有索引，并在每个索引上加上1。由于有效重叠必须以 master 的最后一个元素结束，因此只有那些值是可能重叠的长度。然后我们可以检查它们中的每一个，如果它之前的元素也排成一行。

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

它也是非贪婪的，即它寻找最小的非空重叠（merge([1, 2, 2], [2, 2, 3]) 将 return [1, 2, 2, 2, 3]）。我认为这就是您所说的 "to merge at the last possible valid position" 的意思。如果你想要一个贪婪的版本，反转 overlap_lens 生成器。

Answer 4

我提供的不是优化，而是另一种看待问题的方式。对我来说，这似乎是 http://en.wikipedia.org/wiki/Longest_common_substring_problem 的一个特例，其中子字符串总是在 list/string 的末尾。以下算法是动态规划版本。

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

首先，为了清楚起见，您可以将 while 循环替换为 for 循环：

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 的最后一个元素结束，进一步限制比较的次数。

Answer 6

基于：

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

Answer 7

这其实并不太难。毕竟，基本上您所做的就是检查 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。无论哪种方式，它 return 都是 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 来匹配最长切片而不是最短切片的问题，但我不确定这对您的速度有何影响。它肯定更慢，但可能无关紧要。您还可以记住结果和 return 最短的结果，这可能是个更好的主意。

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 8

上述所有解决方案在合并任务中使用 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"])

Answer 9

你需要的是像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

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

Pythonic way to merge two overlapping lists, preserving order

python

merge

list

python-3.x