Python: простое слияние списков на основе пересечений

Question

Учтите, что есть несколько списков целых чисел:

#--------------------------------------
0 [0,1,3]
1 [1,0,3,4,5,10,...]
2 [2,8]
3 [3,1,0,...]
...
n []
#--------------------------------------

Вопрос состоит в том, чтобы объединить списки, имеющие хотя бы один общий элемент.Таким образом, результаты только для данной части будут следующими:

#--------------------------------------
0 [0,1,3,4,5,10,...]
2 [2,8]
#--------------------------------------

Какой самый эффективный способ сделать это для больших данных (элементы - просто числа)? Является ли tree структурировать что-то для размышления?Я делаю работу сейчас, преобразовывая списки в sets и повторяя для пересечений, но это медленно!Кроме того, у меня такое ощущение, что это так элементарно!Кроме того, в реализации чего-то не хватает (неизвестно), потому что некоторые списки иногда остаются не объединенными!Сказав это, если вы предлагаете самореализацию, пожалуйста, будьте щедрыми и предоставьте простой пример кода [очевидно, Python - мой фаворит :)] или псевдокод.
Обновление 1: Вот код, который я использовал:

#--------------------------------------
lsts = [[0,1,3],
        [1,0,3,4,5,10,11],
        [2,8],
        [3,1,0,16]];
#--------------------------------------

Функция ( глючит !! ):

#--------------------------------------
def merge(lsts):
    sts = [set(l) for l in lsts]
    i = 0
    while i < len(sts):
        j = i+1
        while j < len(sts):
            if len(sts[i].intersection(sts[j])) > 0:
                sts[i] = sts[i].union(sts[j])
                sts.pop(j)
            else: j += 1                        #---corrected
        i += 1
    lst = [list(s) for s in sts]
    return lst
#--------------------------------------

Результат:

#--------------------------------------
>>> merge(lsts)
>>> [0, 1, 3, 4, 5, 10, 11, 16], [8, 2]]
#--------------------------------------

Обновление 2: По моему опыту код, приведенный ниже Niklas Baumstark , показался немного быстрее для простых случаев.Еще не проверен метод, данный «Крючком», поскольку это совершенно другой подход (кстати, он кажется интересным).Процедура тестирования для всего этого может быть очень трудной или невозможной для обеспечения результатов.Реальный набор данных, который я буду использовать, настолько велик и сложен, что невозможно отследить любую ошибку, просто повторив.То есть я должен быть на 100% удовлетворен надежностью метода, прежде чем поместить его на место в большом коде в качестве модуля.Просто пока Niklas метод быстрее, и ответ для простых наборов, конечно, правильный.
Однако как я могу быть уверен, что он работает хорошо для действительно большого набора данных? Поскольку я не смогу визуально отследить ошибки!

Обновление 3: Обратите внимание, что надежность метода гораздо важнее, чем скорость для этой проблемы.Я надеюсь, что смогу наконец-то перевести код Python в Fortran для максимальной производительности.

Обновление 4:
В этом посте есть много интересных моментов и щедро предоставленных ответов, конструктивныхКомментарии.Я бы рекомендовал прочитать все внимательно.Пожалуйста, примите мою благодарность за разработку вопроса, удивительные ответы и конструктивные комментарии и обсуждение.

Answer 1

Вот функция (Python 3.1), чтобы проверить, в порядке ли результат функции слияния.Он проверяет:

• Являются ли результирующие наборы непересекающимися?(количество элементов объединения == сумма чисел элементов)
• Являются ли элементы результирующих наборов такими же, как в списках ввода?
• Является ли каждый список ввода подмножеством результатаset?
• Является ли каждый набор результатов минимальным, т. е. невозможно ли разбить его на два меньших набора?
• Он не проверяет наличие пустых наборов результатов - Iне знаю, хотите вы их или нет ...

.

from itertools import chain

def check(lsts, result):
    lsts = [set(s) for s in lsts]
    all_items = set(chain(*lsts))
    all_result_items = set(chain(*result))
    num_result_items = sum(len(s) for s in result)
    if num_result_items != len(all_result_items):
        print("Error: result sets overlap!")
        print(num_result_items, len(all_result_items))
        print(sorted(map(len, result)), sorted(map(len, lsts)))
    if all_items != all_result_items:
        print("Error: result doesn't match input lists!")
    if not all(any(set(s).issubset(t) for t in result) for s in lst):
        print("Error: not all input lists are contained in a result set!")

    seen = set()
    todo = list(filter(bool, lsts))
    done = False
    while not done:
        deletes = []
        for i, s in enumerate(todo): # intersection with seen, or with unseen result set, is OK
            if not s.isdisjoint(seen) or any(t.isdisjoint(seen) for t in result if not s.isdisjoint(t)):
                seen.update(s)
                deletes.append(i)
        for i in reversed(deletes):
            del todo[i]
        done = not deletes
    if todo:
        print("Error: A result set should be split into two or more parts!")
        print(todo)

Answer 2

Это медленнее, чем решение, предлагаемое Никласом (я получил 3,9 с на test.txt вместо 0,5 с для его решения), но дает тот же результат и может быть легче реализовать, например, в Fortran, так как оно не '• использование наборов, только сортировка общего количества элементов, а затем один проход по всем из них.

Возвращает список с идентификаторами объединенных списков, поэтому также отслеживает пустые списки, они остаютсябез погружения.

def merge(lsts):
        # this is an index list that stores the joined id for each list
        joined = range(len(lsts))
        # create an ordered list with indices
        indexed_list = sorted((el,index) for index,lst in enumerate(lsts) for el in lst)
        # loop throught the ordered list, and if two elements are the same and
        # the lists are not yet joined, alter the list with joined id
        el_0,idx_0 = None,None
        for el,idx in indexed_list:
                if el == el_0 and joined[idx] != joined[idx_0]:
                        old = joined[idx]
                        rep = joined[idx_0]
                        joined = [rep if id == old else id for id in joined]
                el_0, idx_0 = el, idx
        return joined

Answer 3

Это будет мой обновленный подход:

def merge(data):
    sets = (set(e) for e in data if e)
    results = [next(sets)]
    for e_set in sets:
        to_update = []
        for i,res in enumerate(results):
            if not e_set.isdisjoint(res):
                to_update.insert(0,i)

        if not to_update:
            results.append(e_set)
        else:
            last = results[to_update.pop(-1)]
            for i in to_update:
                last |= results[i]
                del results[i]
            last |= e_set

    return results

Примечание: Во время объединения пустые списки будут удалены.

Обновление: Надежность.

Вам нужны два теста для 100% надежности успеха:

• Убедитесь, что все полученные наборы взаимно не связаны:

  merged = [{0, 1, 3, 4, 5, 10, 11, 16}, {8, 2}, {8}]
  
  from itertools import combinations
  for a,b in combinations(merged,2):
      if not a.isdisjoint(b):
          raise Exception(a,b)    # just an example
  

• Убедитесь, что объединенный набор охватывает исходные данные. (согласно предложению katrielalex)

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

Answer 4

Это можно решить в O (n) с помощью алгоритма поиска объединения.Учитывая первые две строки ваших данных, ребра для использования в объединении найти следующие пары: (0,1), (1,3), (1,0), (0,3), (3,4), (4,5), (5,10)

Answer 5

Мое решение хорошо работает с небольшими списками и вполне читабельно без зависимостей.

def merge_list(starting_list):
    final_list = []
    for i,v in enumerate(starting_list[:-1]):
        if set(v)&set(starting_list[i+1]):
            starting_list[i+1].extend(list(set(v) - set(starting_list[i+1])))
        else:
            final_list.append(v)
    final_list.append(starting_list[-1])
    return final_list

Сравнительный анализ:

lists = [[1,2,3], [3,5,6], [8,9,10], [11,12,13]]

% timeit merge_list (списки)

100000 циклов, лучшее из 3: 4,9 мкс на цикл