Pythonic способ объединить два перекрывающихся списка, сохраняя порядок

Ответ 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)

который должен работать после слияния самого длинного перекрытия, должен давать самый короткий результат во всех случаях.

Ответ 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 в порядке убывания, начиная с длины b до 1 (xrange(len(b), 0, -1)), потому что мы хотим как можно больше сопоставить. Возьмем первый такой i, используя next, и если мы его не найдем, мы используем нулевое значение (next(..., 0)). С момента, когда мы нашли i, добавим к a элементы b из индекса i.

Ответ 3

Есть несколько простых оптимизаций, которые возможны.

• Вам не нужно начинать с мастера [1], так как самое длинное перекрытие начинается с мастера [-len (дополнение)]

• Если вы добавите вызов 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

Ответ 4

Одна тривиальная оптимизация не повторяется во всем списке master. I.e., замените 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 (вы, вероятно, получите IndexError в master[-overlap_len + i], если это не так). Добавьте условие к генератору overlap_lens, если вы не можете гарантировать его.

Он также не жадный, т.е. ищет наименьшее непустое перекрытие (merge([1, 2, 2], [2, 2, 3]) вернет [1, 2, 2, 2, 3]). Я думаю, это то, что вы имели в виду под "слиться в последней возможной действительной позиции". Если вы хотите жадную версию, отмените генератор overlap_lens.

Ответ 5

Я не предлагаю оптимизацию, а другой способ взглянуть на проблему. Для меня это похоже на частный случай 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]

Ответ 6

Прежде всего, и для ясности вы можете заменить цикл 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 последний элемент, что дополнительно ограничивает количество сравнений.

Ответ 7

На основе fooobar.com/questions/211329/...:

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

Ответ 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"])